部分和の計算と要素の更新の両方を効率的に行える木構造 フェニック木 - Wikipedia
- 蟻本ではBinary lndexed Treeと呼ばれてる
- BITと略される
- fenwick tree
-
保坂 和宏 (東京大学理学部数学科)
-
第 13 回 JOI 春合宿
-
2014/03/19
k 番目の値を高速に取り出せるデータ構造として使うことができる
-
集合への追加削除とkth取得
python
N = 1000
bit = [0] * (N + 1) # 1-origin
def bit_add(pos, val):
x = pos
while x <= N:
bit[x] += val
x += x & -x # (x & -x) = rightmost 1 = block width
def bit_sum(pos):
ret = 0
x = pos
while x > 0:
ret += bit[x]
x -= x & -x
return ret
def bit_bisect(lower):
"find a s.t. v1 + v2 + ... + va >= lower"
x = 0
k = 1 << (N.bit_length() - 1) # largest 2^m <= N
while k > 0:
if (x + k <= N and bit[x + k] < lower):
lower -= bit[x + k]
x += k
k //= 2
return x + 1
bit_add(12, 1)
bit_add(34, 1)
bit_add(56, 1)
print(bit_sum(20)) # => 1
print(bit_sum(40)) # => 2
print(bit_sum(60)) # => 3
print(bit_bisect(2)) # => 34