1. はじめに
N個の整数が与えられるとする。この時、特定の区間（left から right 番目）の合計値を求めるクエリを高速に処理する方法として、累積和が知られている。事前計算にO(N)のコストを払うことで、一つのクエリに対して時間計算量O(1)で求めることができるようになる。
この方法は、静的な配列のみに有効である。配列の値が動的に変化する場合、再度累積和を計算し直すため、更新クエリの際に時間計算量O(N)を払うことになる。
これを高速に行う方法として、セグメント木、BIT、平方分割などがある。
今回この記事では、BITについて解説をする。
2. BITの仕組み
2.1. BITのカバー範囲の考え方と初期化
BITは、配列 a の各要素を完全に個別に持つのではなく、ある範囲の部分和をまとめて持つことでクエリを高速化するデータ構造である。
累積和では、i 番目の値が配列の先頭から i までの全ての要素をまとめて持っている。したがって、インデックスが大きくなるほど、カバーする範囲も線型的に増加していく。
一方、BITはそうではない。各ノードが担当する範囲は、i の最下位ビットの値（表 low_bit ）の値によって決まり、範囲の大きさは2のべき乗ごとに変化する。そのため、i が大きくなるにつれて範囲が単調に増加するのではなくて、1, 2, 1, 4, 1, 2, 1, 8 のように、ビット構造に応じて周期的に広がったり狭まったりする。
各ノードが担当する範囲を次に示す。
ここで left = i - low_bit(i)、right = i（半開区間 [left, right)）とした。また、カバー範囲は元となる配列を示しており、1-indexed で表記されている。
| i | 2進数表記 | low_bit | left | right | カバー範囲 |
|---|---|---|---|---|---|
| 1 | 01 | 1 | 0 | 1 | a[1] |
| 2 | 10 | 2 | 0 | 2 | a[1], a[2] |
| 3 | 11 | 1 | 2 | 3 | a[3] |
| 4 | 100 | 4 | 0 | 4 | a[1], a[2], a[3], a[4] |
| 5 | 101 | 1 | 4 | 5 | a[5] |
| 6 | 110 | 2 | 4 | 6 | a[5], a[6] |
| 7 | 111 | 1 | 6 | 7 | a[7] |
| 8 | 1000 | 8 | 0 | 8 | a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8] |
| 9 | 1001 | 1 | 8 | 9 | a[9] |
| 10 | 1010 | 2 | 8 | 10 | a[9], a[10] |
実装コードは次のようになる。事前計算は O(NlogN) で実行できる。
class BIT:
def __init__(self, n):
self.n = n
self.arr = list(range(1, self.n + 1))
self.bits = [0] * (self.n + 1)
# BIT配列の構築
for i in range(1, self.n + 1):
low_bit = i & -i
left = i - low_bit
right = i
for j in range(left, right):
self.bits[i] += self.arr[j]
例として、n = 10 で実行すると bits 配列は次のようになる。
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
bits = [0, 1, 3, 3, 10, 5, 11, 7, 36, 9, 19]
2.2. BITの事前計算の高速化
先ほどの実装例では事前計算はO(NlogN)であった。これはO(N)に高速化することができる。O(N)の実装例は次のようになる。
class BIT:
def __init__(self, arr):
self.n = len(arr)
self.bits = [0] * (self.n + 1)
# O(n) の事前計算
for i in range(1, self.n + 1):
self.bits[i] += arr[i - 1]
j = i + (i & -i)
if j <= self.n:
self.bits[j] += self.bits[i]
3. BITの更新と総和
2章では、BITの内部構造と初期化の仕組みを見た。BITの大きな利点は、値の更新（update） と 部分和の計算（sum） をともに O(logN) で行える点にある。ここでは、その動作の仕組みを説明する。なお、以後の更新クエリと総和クエリは 1-indexed で行う。
3.1. 更新操作（update）
配列 a の特定の位置 index に値を加算したい場合、BITでは次のようにして処理を行う。
- まず該当するノード
bit[index]に値を加算する。 - 次に、
indexの最下位ビット（index & -index）を含む親ノードに順番に伝搬していく。
これにより、更新の影響を受けるすべての部分和ノードをもれなく反映することができる。
実装は次のようになる。
def update(self, index, add):
while index <= self.n:
self.bits[index] += add
index += index & -index
例として n = 10 で初期化したBIT配列の各インデックスを更新した際の、更新が伝播していくインデックスの遷移を次に示す。
index= 1 を更新: 1, 2, 4, 8
index= 2 を更新: 2, 4, 8
index= 3 を更新: 3, 4, 8
index= 4 を更新: 4, 8
index= 5 を更新: 5, 6, 8
index= 6 を更新: 6, 8
index= 7 を更新: 7, 8
index= 8 を更新: 8
index= 9 を更新: 9, 10
index=10 を更新: 10
これを見ると、各インデクスが担当するカバー範囲の上位インデックスへ順に伝播していることがわかる。例えば、index = 5 の更新は、bits[5] のみではなく、bits[6]、bits[8] にも反映されている。これは、カバー範囲で、a[5] が bits[5]、bits[6]、bits[8]の3つに含まれていたことと一致する。
3.2. 部分和計算（sum）
a[1] から a[k] までの前計算和（prefix sum）をBITで求めるときは、更新のときとは逆方向にたどる。具体的には、index を最下位ビット（index & -index）だけ減らしながら、対応する bits の値を加算していく。
実装は次の通り。
def prefix_sum(self, index): # a[1]..a[index] の和
result = 0
while index > 0:
result += self.bits[index]
index -= index & -index
return result
このループは、index の2のべき単位区切りで遡るため、操作回数は高々 O(logN) となる。区間和 [l, r] は、累積の差分で求めることができる。
$$
\text{sum}(l, r) = \text{prefix_sum}(r) - \text{prefix_sum}(l - 1)
$$
実装は次の通り。
def range_sum(self, l, r): # [l, r]（1-indexed）
return self.prefix_sum(r) - self.prefix_sum(l - 1)
4. Range Sum Query （区間和クエリ）問題
4.1. 問題とその解法
BITを使った問題として、Range Sum Query 問題がある。これは次の2つのクエリを高速に処理する必要がある。
-
add(i, x): 要素a[i]にxを加算する -
getSum(s, t): 区間[s, t]の合計値（a[s] + a[s+1] + ... + a[t]）を求める
このとき、BITを用いればいずれのクエリも O(logN) で実行することができる。問題文の詳細は以下のサイトから閲覧できる。
BITによる実装例（Python）は次の通り。今回の問題は、初期の数列はすべて0で初期化されているため、BITの事前計算は必要ない。
class BIT:
def __init__(self, n):
self.n = n
self.bits = [0] * (n + 1)
def update(self, i, x):
while i <= self.n:
self.bits[i] += x
i += i & -i
def prefix_sum(self, i):
s = 0
while i > 0:
s += self.bits[i]
i -= i & -i
return s
def range_sum(self, l, r):
return self.prefix_sum(r) - self.prefix_sum(l - 1)
n, q = map(int, input().split())
bit = BIT(n)
for _ in range(q):
com, x, y = map(int, input().split())
if com == 0: # addクエリ(x, y)
bit.update(x, y)
else: # getSumクエリ(x, y)
print(bit.range_sum(x, y))
4.2. 計算量と特徴まとめ
BITを用いることで、Range Sum Query 問題を次の計算量で処理することができる。
| 操作 | 内容 | 計算量 |
|---|---|---|
update(i, x) |
要素 a[i] に x を加算 |
O(log N) |
range_sum(l, r) |
区間 [l, r] の総和を求める |
O(log N) |
このように、BITはインデックス更新と区間和取得を効率的に行うデータ構造である。一方で、区間和更新と区間和の取得であったり、区間最小値（最大値）などを扱う場合は、より汎用的なセグメント木を用いるほうがよい。