FenwickTreeまたはBinaryIndexedTree

bit.kt

//0-indexed
class BIT(val n: Int){
    val bit = IntArray(n)
    fun sum(i: Int): Int {
        var i = i - 1
        var s = 0
        while(i >= 0){
            s += bit[i]
            //i+1(==1-indexedのときのi)の最も右の1が立っているbitを0にして-1する
            i = i.and(i+1) - 1
        }
        return s
    }
    fun add(i: Int, x: Int){
        var i = i
        while(i < n){
            bit[i] += x
            //最も右の0になっているbitを1にする
            i = i.or(i+1)
        }
    }
}
//1-indexed
class BIT(val n: Int){
    val bit = IntArray(n + 1)
    fun sum(i: Int): Int {
        var i = i
        var s = 0
        while(i > 0){
            s += bit[i]
            //最も右の1が立っているbitを引く
            i -= i.and(-i)
        }
        return s
    }
    fun add(i: Int, x: Int){
        var i = i
        while(i <= n){
            bit[i] += x
            //最も右の1が立っているbitを足す
            i += i.and(-i)
        }
    }
}