バイナリインデックスツリー（BIT）で解く！C++における範囲更新・範囲合計クエリの効率的な実装

サイズ n の整数配列があり、初期状態ではすべての要素が 0 になっているとします。この配列に対して、次の2種類のクエリを処理することを考えます。

• update(l, r, value) ― インデックス l から r までの範囲に含まれるすべての要素に value を加算します。たとえば update(2, 4, 5) なら、インデックス 2〜4 の各要素に 5 を足す操作を意味します。

• getRangeSum(l, r) ― インデックス l から r までの範囲に含まれる要素の合計を求めます。たとえば getRangeSum(4, 7) なら、インデックス 4、5、6、7 の要素の総和を計算します。

具体例で問題を確認してみましょう。

入力例

n = 7 , arr[7] = {0,0,0,0,0,0,0}
Q1 = update(3, 6, 4)
Q2 = update(0, 4, 2)
Q3 = Sum(2, 5)

出力

10

解説

Q1：update(3, 6, 4) を適用 → {0, 0, 0, 4, 4, 4, 4}
Q2：update(0, 4, 2) を適用 → {2, 2, 2, 2, 2, 4, 4}
Q3：sum(2, 5) を計算 → 2+2+2+4 = 10

素朴なアプローチの課題

最も単純な解法は、update クエリのたびに配列の該当範囲を直接書き換え、sum クエリのたびに範囲内を走査して合計を求めるものです。しかしこの方法では1回の操作に最大 O(n) の時間がかかるため、クエリ数が多い場合には実用的とは言えません。そこで、より効率的なアプローチを導入します。

効率化の鍵：範囲和を接頭辞和へ分解する

範囲和クエリ sum[l, r] は、先頭からの累積和（接頭辞和）を用いて次のように表すことができます。

sum[l, r] = sum[0, r] − sum[0, l−1]

つまり、sum[0, k] の変化を正しく追跡できれば、任意の区間の合計も求められることになります。ここで update(l, r, value) が与えられたとき、位置 k が更新区間 [l, r] に対してどこに位置するかによって、sum[0, k] への影響は次の3つの領域に分類されます。

領域1：0 ≤ k < l の場合
更新クエリは sum[0, k] に一切影響を与えません。

領域2：l ≤ k ≤ r の場合
sum[0, k] には、l から k までの範囲分だけ value が加算された影響が現れます。

領域3：k > r の場合
sum[0, k] には、l から r までの全区間分（value × (r − l + 1)）の影響が現れます。

これらの影響を高速に処理するために、バイナリインデックスツリー（Binary Indexed Tree／Fenwick Tree）を2本用意します。1本目のBITには差分（区間の始点に +value、終点の次に −value）を記録し、2本目のBITには位置に応じた補正項（value×(l−1) や −value×r など）を記録します。こうすることで、prefixSum(x) = getSum(BIT1, x) × x − getSum(BIT2, x) という式で接頭辞和を復元でき、範囲更新も範囲和の取得もそれぞれ O(log n) で実行できます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
int getSum(int BITree[], int i){
    int sum = 0;
    i++;
    while (i>0) {
        sum += BITree[i];
        i -= i & (-i);
    }
    return sum;
}
void updateBITree(int BITree[], int n, int i, int val) {
    i = i + 1;
    while (i <= n) {
        BITree[i] += val;
        i += i & (-i);
    }
}
void update(int BITTree1[], int BITTree2[], int n, int l, int r, int value) {
    updateBITree(BITTree1,n,l,value);
    updateBITree(BITTree1,n,r+1,-value);
    updateBITree(BITTree2,n,l,value*(l-1));
    updateBITree(BITTree2,n,r+1,-value*r);
}
int sum(int x, int BITTree1[], int BITTree2[]) {
    return (getSum(BITTree1, x) * x) - getSum(BITTree2, x);
}
int getRangeSum(int l, int r, int BITTree1[], int BITTree2[]) {
    return sum(r, BITTree1, BITTree2) - sum(l-1, BITTree1, BITTree2);
}
int *createBITree(int n) {
    int *BITree = new int[n+1];
    for (int i=1; i<=n; i++)
    BITree[i] = 0;
    return BITree;
}
int main(){
    int n = 7;
    int *BITTree1, *BITTree2;
    BITTree1 = createBITree(n);
    BITTree2 = createBITree(n);
    update(BITTree1,BITTree2,n,3,6,9);
    update(BITTree1,BITTree2,n, 0, 4, 5);
    cout<<"The output of sum query after applying all update queries is \t"          <<getRangeSum(1,5,BITTree1,BITTree2);
    return 0;
}

出力

The output of sum query after applying all update queries is 47

このプログラムでは、まずインデックス 3〜6 に 9 を加算し、続いてインデックス 0〜4 に 5 を加算しています。その結果、配列は {5, 5, 5, 14, 14, 9, 9} となり、getRangeSum(1, 5) の答えは 5+5+14+14+9 = 47 となります。

計算量

本手法では、update および getRangeSum の各クエリを O(log n) で処理でき、必要な追加メモリは O(n) です。1クエリあたり O(n) かかる素朴な手法と比較すると、クエリが大量に発生する場面で大幅な性能向上が期待できます。