フェニック木

部分和の計算と要素の更新の両方を効率的に行える木構造

保坂 和宏 (東京大学理学部数学科)

第 13 回 JOI 春合宿

2014/03/19

k 番目の値を高速に取り出せるデータ構造として使うことができる

集合への追加削除とkth取得

素朴な方法としては値域のサイズDの配列を用意して、値のあるところに1を立てる

O(1)で追加削除可能

kthの取得は端から数えていくので遅い

これをBITにする

BITは部分和がO(logD)

これに対して二分探索すれば良い

工夫するとO(logD)　see 保坂さんの資料

ただし追加削除はO(logD)

集合の中である値の次の値が知りたい時

まずその値までの和を取って、1加えて二分探索

これを繰り返せば「ある値より大きいものの取得」もできる

code:python

N = 1000

def bit_add(pos, val):

x = pos

while x <= N:

x += x & -x # (x & -x) = rightmost 1 = block width

def bit_sum(pos):

ret = 0

x = pos

while x > 0:

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:

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