目次
文書の過去の版を表示しています。
Binary Indexed Tree
概要
Binary Indexed Tree のはなし - hos.ac[pdf]
Range Sum Query（区間の和）に対する効率的なデータ構造。
- 数列 $a_1,a_2,...,a_N$ がある
- 以下の2つの要求を処理する
- $a_i$ に $x$ を加算（$1 \le i \le N$）
- $a_s～a_t$ の合計を得る（$1 \le s \le t \le N$）
Binary Indexed Treeは、この2つを高速に行える。
これだけ見ると「そんなのが何の役に立つの？」って感じだが、頭のいい人だと全然関係ないように見える問題を変換して効率的に解いたりしちゃうらしい。
実装
詳しい説明は上のpdfで懇切丁寧に行われているので、Pythonコードだけメモ。
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
注意点として、配列のindex等と異なり、添え字は1から始まる。その方が効率的に上下の要素を特定できるため。
⇤←←←←←←８ ⇤←←４ ⇤２ ⇤６ ⇤10 １ ３ ５ ７ ９ ...
添え字を2進数にしたもの。
⇤─←─←─←─←─←─←─1000 ⇤─←─←─0100 ⇤─0010 ⇤─0110 ⇤─1010 0001 0011 0101 0111 1001 ...
「$a_1 ～ a_7$ の和」を求めるときに足される箇所。7を表す “0111” から始めて、“1” が立っている箇所を下から1つずつ “0” にした添え字を辿っていく。
⇤─←─←─←─←─←─←─1000 ⇤─←─←【0100】 ⇤─0010 ⇤【0110】 ⇤─1010 0001 0011 0101 【0111】 1001 ...
区間に対する更新
上記のBit.add()は、点に対する更新しか行えない。では「$a_3～a_7$ に一律に5を加算」などが必要な場合にどうするか。
区間の和が必要ない場合
区間の和は必要なく、ある指定した位置の値だけわかれば良い場合。つまり、
- $a_s$ から $a_t$ までに一律 $x$ を加算（$1 \le s \le t \le n$）
- $a_i$ の値を得る（$1 \le i \le n$）
この場合は、差分に着目することで、BITをそのまま利用できる。（上記pdf参照）
- $a_s～a_t$ に一律 $x$ を加算→「$s$ に $x$、$t+1$ に $-x$ を加算」
- $a_i$ の値を取得→「$1～i$ の合計を取得」
なお、見ての通り添え字が $n+1$ まで参照される可能性があるので、便宜上、BITのサイズは1大きい値で作っておく
区間の和も欲しい場合
- $a_s～a_t$ に一律 $x$ を加算（$1 \le s \le t \le n$）
- $a_s～a_t$ の合計を得る（$1 \le s \le t \le n$）
よくわからんけど、上記の応用で、BITを2個使うことでできる。
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
区間の最大値・最小値
Segment Treeほどの柔軟性は無いが、いくらかの制約された条件下で、区間最大値・最小値の管理にも使える（以下は最大値の例）
- $update(i, x)$: $a_i$ を $x$ で更新する。この際、$x$ は必ず元の $a_i$ 以上でなければならない
- $getmax(i)$: $a_1～a_i$ の最大値を取得する。必ず1からの最大値であり、途中からの $a_s～a_t$ は取得できない。
単純に、上記のコードの加算を、MAXを取る操作に置きかえればよい。
class Bit:
def __init__(self, n):
self.size = n
self.tree = [0] * (n + 1)
def sum(self, i):
s = -(10 ** 18) # -INF
while i > 0:
s = max(s, self.tree[i])
i -= i & -i
return s
def add(self, i, x):
while i <= self.size:
self.tree[i] = max(x, self.tree[i])
i += i & -i
少し理解は難しくなるが、BITを2本使って管理することで、上記の制約を無くした区間最大値・最小値も得られる。
累積和の二分探索
二分探索により、累積和が $x$ のindexや、$x$ を越えない最大のindexとその時の累積和などを得ることができる。
（※以下、sum, add は既述のコードと共通。init内でdepthを定義しておき、lower_boundで探索する）
class Bit:
def __init__(self, n):
self.size = n
self.tree = [0] * (n + 1)
self.depth = n.bit_length()
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
def lower_bound(self, x):
""" 累積和がx以上になる最小のindexと、その直前までの累積和 """
sum_ = 0
pos = 0
for i in range(self.depth, -1, -1):
k = pos + (1 << i)
if k <= self.size and sum_ + self.tree[k] < x:
sum_ += self.tree[k]
pos += 1 << i
return pos + 1, sum_
