−目次
文書の過去の版を表示しています。
Binary Indexed Tree
Binary Indexed Tree のはなし - hos.ac[pdf]
Range Sum Query(区間の和)に対する効率的なデータ構造
- 数列a1,a2,...,anがある
- 以下の2つの要求を処理する
- aiにxを加算(1≤i≤n)
- asからatまでの合計を得る(1≤s≤t≤n)
Binary Indexed Treeは、この2つを高速に行える。
これだけ見ると「そんなシチュエーションあるの?」って感じだが、頭のいい人だと全然関係ないように見える問題をRSQに変換して効率的に解いたりしちゃうらしい。
詳しい説明は上のpdfで懇切丁寧に行われているので、Pythonコードだけメモ。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Bit: def __init__( self , n): self .size = n self .tree = [ 0 ] * (n + 1 ) def sum ( self , i): s = 0 while i > 0 : s + = self .tree[i] i - = i & - i return s def add( self , i, x): while i < = self .size: self .tree[i] + = x i + = i & - i # 使用例 bit = Bit( 10 ) # 要素数を与えてインスタンス化 bit.add( 2 , 10 ) # a2に10を加える bit.add( 5 , 5 ) # a5に 5を加える print (bit. sum ( 3 )) # a1~a3の合計を返す => 10 print (bit. sum ( 6 )) # a1~a6の合計を返す => 15 bit.add( 3 , - 6 ) # a3に-6を加える print (bit. sum ( 6 )) # a1~a6の合計を返す => 9 print (bit. sum ( 6 ) - bit. sum ( 3 )) # a4~a6の合計 => 5 |
区間に対する更新
上記のBit.add()は、点に対する更新しか行えない。では「a3~a7に一律に5を加算」などが必要な場合にどうするか。
区間の和が必要ない場合
区間の和は必要なく、ある指定した位置の値だけわかれば良い場合。つまり、
- asからatまでに一律xを加算(1≤s≤t≤n)
- aiの値を得る(1≤i≤n)
この場合は、差分に着目することで、BITをそのまま利用できる。(上記pdf参照)
- s~tに一律xを加算→「sにx、t+1に−xを加算」
- 位置iの値を取得→「1~iの合計を取得」
なお、見ての通り添え字がn+1まで参照される可能性があるので、便宜上、Bitのサイズは1大きい値で作っておく
区間の和も欲しい場合
- asからatまでに一律xを加算(1≤s≤t≤n)
- asからatまでの合計を得る(1≤s≤t≤n)
よくわからんけど、上記の応用で、BITを2個使うことでできる。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class RangeUpdate: def __init__( self , n): self .p = Bit(n + 1 ) self .q = Bit(n + 1 ) def add( self , s, t, x): t + = 1 self .p.add(s, - x * s) self .p.add(t, x * t) self .q.add(s, x) self .q.add(t, - x) def sum ( self , s, t) t + = 1 return self .p. sum (t) + self .q. sum (t) * t - \ self .p. sum (s) - self .q. sum (s) * s |