Skip to content

Instantly share code, notes, and snippets.

@crakaC
Last active February 1, 2021 16:55
Show Gist options
  • Save crakaC/a08902873b276dc6c08cecabf9fe877c to your computer and use it in GitHub Desktop.
Save crakaC/a08902873b276dc6c08cecabf9fe877c to your computer and use it in GitHub Desktop.
FenwickTreeまたはBinaryIndexedTree
//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)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment