Binary Indexed Tree

概要

Range Sum Query（区間の和）に対する効率的なデータ構造

数列$a_1,a_2,\ldots,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から始まる。そうしないと効率的に上下の要素を特定できないため。

              ８
      ４
  ２      ６
１  ３  ５  ７  ９ ...

区間に対する更新

上記のBit.add()は、点に対する更新しか行えない。では「a3～a7に一律に5を加算」などが必要な場合にどうするか。

区間の和が必要ない場合

区間の和は必要なく、ある指定した位置の値だけわかれば良い場合。つまり、

$a_s$から$a_t$までに一律$x$を加算（$1 \le s \le t \le n$）
$a_i$の値を得る（$1 \le i \le n$）

この場合は、差分に着目することで、BITをそのまま利用できる。（上記pdf参照）

$s$～$t$に一律$x$を加算→「$s$に$x$、$t+1$に$-x$を加算」
位置$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とその時の累積和などを得ることができる。

[Tutorial] Searching Binary Indexed Tree in O(log(N)) using Binary Lifting - Codeforces

class Bit:
    def __init__(self, n): (略)
    def sum(self, i): (略)
    def add(self, i, x): (略)

    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

目次