FenwickTree.kt

package lib

class FenwickTree(private val n: Int = 0) {
    private val data = LongArray(n)

    fun add(p: Int, x: Long) {
        var pp = p + 1
        while (pp <= n) {
            data[pp - 1] += x
            pp += pp and -pp
        }
    }

    fun sum(l: Int, r: Int): Long = sum(r) - sum(l)

    private fun sum(r: Int): Long {
        var s = 0L
        var rr = r
        while (rr > 0) {
            s += data[rr - 1]
            rr -= rr and -rr
        }
        return s
    }
}