プログラミング
記事内に商品プロモーションを含む場合があります

【Python】BITを2本使って区間加算と区間和をO(log n)で処理する方法

Aru

動的に要素の値が変更される場合に区間話を求めたい場合、Fenwick木(BIT)というデータ構造が便利です。ただ、BITでは、[l:r)の範囲に1を加えるといった、区間加算を効率よく行うことができません。この記事では、BITを2本使って区間加算と区間和をどちらも O(log n) で処理する仕組みを、差分の考え方から数式を追いながら解説します。また、そのまま使えるPythonのクラスのテンプレートも用意しました。

はじめに

競技プログラミングでは「配列のある範囲にまとめて値を足す」処理と「ある範囲の合計を求める」処理が、どちらも大量のクエリとして降ってくることがあります。片方だけなら単純な配列や累積和で何とかなりますが、両方を同時に、しかも高速にとなると工夫が必要です。

この記事は、BIT(Binary Indexed Tree、Fenwick木)を用いて「区間加算と区間和を両立させる」方法について解説します。なお、前提として、BITは知っているものとして話を進めます。

あわせて読みたい
Binary Indexed Tree(Fenwick Tree)を実装する|Python
Binary Indexed Tree(Fenwick Tree)を実装する|Python

区間加算と区間和

配列 $A[0..n-1]$ に対して、次の2つの操作を高速に行いたい、というのが今回の問題です。

  • 区間加算
    $[l, r]$ の各要素に $v$ を加える
  • 区間和
    $\sum_{i=l}^{r} A[i]$ を求める

まずは素直な方法を考えます。配列をそのまま持つ場合、区間加算は範囲の要素を1つずつ書き換えるので O(n)、区間和も1つずつ足すので O(n) です。クエリが $Q$ 個来ると $O(nQ)$ となり、$n, Q$ が $2 \times 10^5$ 程度になると間に合いません。

累積和の配列を前計算しておけば区間和は O(1) になりますが、今度は区間加算のたびに累積和を作り直す必要があり、そちらが O(n) に戻ってしまいます。片方を速くするともう片方が遅くなる、というのが素直な方法の限界です。

BIT(Fenwick木)とは

配列の「1点更新」と「prefix和(先頭からの累積和)」を、どちらも O(log n) で行えるデータ構造。内部では添字のビット演算(i += i & -i など)を使って、必要な区間だけを足し合わせる。

あわせて読みたい
Binary Indexed Tree(Fenwick Tree)を実装する|Python
Binary Indexed Tree(Fenwick Tree)を実装する|Python

BITを使えば更新も和も O(log n) になります。ここからは、このBITをどう組み合わせて区間加算・区間和を作るかを考えていきます。

区間加算をBITで実現する

まずBITでできることを確認します。ポイントは差分です。

配列 $A$ の差分 $D$ を次のように定義します。

$$
D[0] = A[0], \qquad D[i] = A[i] – A[i-1]\quad (i \ge 1)
$$

隣り合う要素の差を取っただけです。このとき、$D$ を先頭から足し合わせると元の $A$ に戻ります。

$$
A[i] = D[0] + D[1] + \cdots + D[i]
$$

つまり、$D$ をBITに載せておけば、点の値は prefix和 で求まります。

$$
A[p] = \mathrm{BIT.prefix}(p)
$$

さらに嬉しいことに、区間加算 $[l, r] \mathrel{+}= v$ は、差分の世界では2点の更新だけで表せます。

$$
D[l] \mathrel{+}= v, \qquad D[r+1] \mathrel{-}= v
$$

なぜこれで全体が $v$ だけ増えるのかを直感的に言うと、$l$ から増え始め、$r+1$ で元に戻る、という「段差」を作っているイメージです。$l$ から $r$ までの各 $A[i]$ は $D[l]$ を含むので $v$ 増え、$r+1$ 以降は $+v$ と $-v$ が打ち消し合って変化しません。

($r+1 \ge n$ のときの $D[n]$ は配列の外なので無視して構いません。)

「区間加算」は、差分をBITに載せた1本で完結します。BITの点更新2回・prefix和1回、いずれも O(log n) です。

区間和を求めるためのテクニック(BITをもう1つ追加)

次に、区間和を求めたいと考えます。区間和は「先頭からの累積和 $S(p)$」が分かれば、$S(r) – S(l-1)$ で計算できます。そこで $S(p)$ を差分 $D$ で書き直してみます。

$$
S(p) = A[0] + A[1] + \cdots + A[p] = \sum_{i=0}^{p} \sum_{j=0}^{i} D[j]
$$

$A[i]$ を差分の和で置き換えたので、二重和になりました。この二重和を $i$ ごとに書き下すと、次の「三角形」の形になります。

$$
\begin{aligned}
i=0:&\quad D[0] \\
i=1:&\quad D[0] + D[1] \\
i=2:&\quad D[0] + D[1] + D[2] \\
&\quad\vdots \\
i=p:&\quad D[0] + D[1] + \cdots + D[p]
\end{aligned}
$$

ここで発想を変えて、この総和を縦($j$ ごと)に足し直します。各 $D[j]$ が何回現れるかを、具体的な $j$ で数えてみます。

  • $D[0]$ … $i = 0, 1, \dots, p$ の $p+1$ 個の行に現れる
  • $D[1]$ … $i = 1, 2, \dots, p$ の $p$ 個の行に現れる
  • $D[2]$ … $i = 2, 3, \dots, p$ の $p-1$ 個の行に現れる

つまり、$j$ が1増えるごとに現れる回数が1ずつ減っていきます。一般に、$D[j]$ は $i = j, j+1, \dots, p$ の行に現れるので、その個数は $p – j + 1$ 個です。したがって、

$$
S(p) = \sum_{j=0}^{p} D[j],(p-j+1).
$$

さらに $p – j + 1 = (p+1) – j$ と分解して和を2つに分けると、次の形になります。

$$
S(p) = (p+1)\sum_{j=0}^{p} D[j] ;-; \sum_{j=0}^{p} j,D[j].
$$

右辺を見ると、必要なのは次の 2種類の prefix和だけであることが分かります。

  • $\sum_{j \le p} D[j]$ … BIT1 に入れる($D[j]$ をそのまま)
  • $\sum_{j \le p} j,D[j]$ … BIT2 に入れる($j \times D[j]$)

1本目だけでは $\sum D[j]$ しか取れず、$S(p)$ に必要な $\sum j,D[j]$ が足りません。だからBITが2本必要になる、というわけです。

数式だけだと「なぜ $j$ を掛けるのか」が分かりにくいですが、要は各要素が何行ぶん足されるかを位置で数えているだけです。下の行ほど何度も足されるので、位置 $j$ に比例した重みが付く、ということですね。

更新式とクエリ式

更新式

$[l, r]$ に $v$ を加算するとき、BIT1・BIT2 は次のように更新します。

$$
\text{BIT1}: l \mathrel{+}= v,\quad r+1 \mathrel{-}= v
$$

$$
\text{BIT2}: l \mathrel{+}= v\cdot l,\quad r+1 \mathrel{-}= v\cdot (r+1)
$$

BIT1 は差分 $D$ をそのまま持つので、先ほどの2点更新と同じです。BIT2 は $j \times D[j]$ を持つので、$D$ に位置 $j$ を掛けた値を足し引きします。BIT2 の $l$ 側が $v \cdot l$、$r+1$ 側が $v \cdot (r+1)$ になっているのは、重み $j$ がそのまま掛かっているためです。

($r+1 \ge n$ のときは $r+1$ 側の更新を省略します。)

クエリ式

累積和は、先ほどの分解式をそのまま使って次のように求まります。

$$
S(p) = (p+1)\cdot \mathrm{BIT1.prefix}(p) – \mathrm{BIT2.prefix}(p)
$$

区間和は累積和の差で求まります。

$$
\sum_{i=l}^{r} A[i] = S(r) – S(l-1)
$$

点取得は BIT1 だけで十分です($\mathrm{BIT1.prefix}(p)$)。

BIT1 が「値そのもの(差分)」、BIT2 が「位置の重み $j$ を掛けた値」を担当する、という役割分担がこの構成の要点です。

Python実装

ここまでの内容を、そのまま使えるクラスにまとめます。添字は 0-indexed、区間は閉区間 $[l, r]$ です。依存ライブラリはなく、コピペで動きます。

class RangeAddRangeSumBIT:
    """区間加算・区間和取得を O(log n) で行う BIT(2本構成)。

    添字は 0-indexed。[l, r] は閉区間。
    """

    def __init__(self, n):
        self.n = n
        self.b1 = [0] * (n + 1)  # D[j]
        self.b2 = [0] * (n + 1)  # j * D[j]

    # --- 内部: 0-indexed の点更新 / prefix 和 ---
    def _add(self, bit, i, w):
        i += 1
        while i <= self.n:
            bit[i] += w
            i += i & -i

    def _sum(self, bit, i):
        # [0, i] の和(i < 0 なら 0)
        i += 1
        s = 0
        while i > 0:
            s += bit[i]
            i -= i & -i
        return s

    def range_add(self, l, r, v):
        """A[l..r] に v を加算する(0-indexed 閉区間)。"""
        self._add(self.b1, l, v)
        self._add(self.b2, l, v * l)
        if r + 1 < self.n:
            self._add(self.b1, r + 1, -v)
            self._add(self.b2, r + 1, -v * (r + 1))

    def _prefix(self, p):
        """A[0..p] の総和。"""
        if p < 0:
            return 0
        return (p + 1) * self._sum(self.b1, p) - self._sum(self.b2, p)

    def range_sum(self, l, r):
        """A[l..r] の総和(0-indexed 閉区間)。"""
        return self._prefix(r) - self._prefix(l - 1)

    def point(self, p):
        """A[p] の値。"""
        return self._sum(self.b1, p)

内部の _add と _sum は、通常のBITを 0-indexed で使えるように i += 1 で調整したものです。公開APIは range_add(区間加算)・range_sum(区間和)・point(点取得)の3つです。

動作確認

提供されたメモの例をそのまま実行すると、次のようになります。

bit = RangeAddRangeSumBIT(5)
bit.range_add(1, 3, 1)      # A = [0, 1, 1, 1, 0]
print(bit.point(2))         # 1
print(bit.range_sum(0, 3))  # 3
bit.range_add(0, 4, 2)      # 全体に +2 → A = [2, 3, 3, 3, 2]
print(bit.range_sum(1, 3))  # 3 + 3 + 3 = 9
print(bit.point(4))         # 2

実行結果は次のとおりです。

1
3
9
2

各区間加算のあとの配列の状態と、出力が一致していることを確認できます。念のため、小さなランダムケースで愚直解(配列を直接書き換えて合計する実装)と結果が一致することも確認しました。

AtCoderの問題で使ってみる(ABC477 F問題)

この構成は、2次元のグリッドを走査しながら「ある列区間の黒マス数」を数える、といった問題でそのまま使えます。提供されたメモでは、abc477 F を次のように解いています。

列を 1-indexed で扱い、行を上から走査しながら、

  • 行 $i$(区間 $[L_i, R_i]$ が黒)を追加する = range_add(L_i, R_i, 1)(列を 1-indexed に変換して呼ぶ)
  • クエリ $(A, B, C, D)$ は $F(B, C, D) – F(A-1, C, D)$ に分解し、各行の時点で range_sum(C, D) を引く

1-indexed で使う場合は、$n = M+1$ として添字 $1..M$ を使うのが簡単です(添字 0 はダミーになります)。

bit = RangeAddRangeSumBIT(M + 1)  # 添字 1..M を使う(0 はダミー)
bit.range_add(L, R, 1)            # 行の黒区間を加算
ans = bit.range_sum(C, D)         # 列 C..D の黒マス数

このとき計算量は $O((N+Q)\log M)$ となり、$N, M, Q \le 2 \times 10^5$ でも十分高速に収まります。

ここでは、解答は提示しませんが、これを使うと、かなり簡単に解くことができます。

まとめ

この記事では、2本のBITを使って、区間加算+区間和を実現する方法について解説しました。更新もクエリも O(log n)、メモリは O(n) で、クエリが多い問題でも十分高速です。

あわせて読みたい
Binary Indexed Tree(Fenwick Tree)を実装する|Python
Binary Indexed Tree(Fenwick Tree)を実装する|Python
ABOUT ME
ある/Aru
ある/Aru
IT&機械学習エンジニア/ファイナンシャルプランナー(CFP®)
専門分野は並列処理・画像処理・機械学習・ディープラーニング。プログラミング言語はC, C++, Go, Pythonを中心として色々利用。現在は、Kaggle, 競プロなどをしながら悠々自適に活動中 保有資格:CFP, マンション管理士、管理業務主任、宅建士など
記事URLをコピーしました