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はインデックス更新と区間和取得を効率的に行うデータ構造である。一方で、区間和更新と区間和の取得であったり、区間最小値（最大値）などを扱う場合は、より汎用的なセグメント木を用いるほうがよい。