スパーステーブルを用いたC++の範囲合計クエリ（Range Sum Query）の実装方法

スパーステーブル（Sparse Table）は、範囲クエリ（Range Query）の結果を高速に取得するために用いられるデータ構造です。ほとんどの範囲クエリに対してO(logN)の計算量で答えを返すことができ、さらに最大値クエリのように演算の性質が許す場合には、O(1)で結果を求めることさえ可能です。

本チュートリアルでは、スパーステーブルを活用した「範囲合計クエリ」の問題を取り上げます。配列が与えられたとき、指定された区間 [L, R] に含まれる全要素の合計を求めるのが目標です。以下に入力例と出力例を示します。

Input: arr[ ] = { 2, 4, 1, 5, 6, 3 }
query(1, 3),
query(0, 2),
query(1, 5).

Output: 10
7
19

Input: arr[ ] = { 1, 2, 3, 4, 1, 4 }
query(0, 2),
query(2, 4),
query(3, 5).

Output: 6
8
9

解法のアプローチ

まず、クエリへの回答を高速化するためにスパーステーブルを構築します。構築には2次元配列を使用し、SPARSE[j][i] には「インデックス j から始まる長さ 2^i の区間の合計」を格納します。つまり、各区間の情報を長さ2の冪乗ごとに分割して前計算しておくのです。

クエリ処理の際には、「Left_index + 2^n − 1 ≤ Right_index」（n は2次元配列の列サイズ）という条件を満たす限り、現在位置から始まる区間の合計値を答えとなる変数に加算し続けます。これにより、任意の区間を複数の「長さが2の冪乗」の区間へ分解し、それらを足し合わせることで合計を求められます。

実装例

上記アプローチのC++コード

#include <bits/stdc++.h>
using namespace std;
// スパーステーブルの行数の最大値
const int m = 1e5;
const int n = 16;
long long SPARSE[m][n + 1];
// スパーステーブルを使ってクエリを処理する関数
long long query(int l, int r){
    long long sum = 0;
    for (int i = n; i >= 0; i--) {
        if (l + (1 << i) - 1 <= r) {
            sum = sum + SPARSE[l][i];
            l += 1 << i;
        }
    }
    return sum;
}
int main(){
    int arr[] = { 1, 2, 3, 4, 1, 4 };
    int z = sizeof(arr) / sizeof(arr[0]);
    // スパーステーブルの構築
    for (int i = 0; i < z; i++)
        SPARSE[i][0] = arr[i];
    for (int i = 1; i <= n; i++)
        for (int j = 0; j + (1 << i) <= z; j++)
            SPARSE[j][i] = SPARSE[j][i - 1] + SPARSE[j + (1 << (i - 1))][i - 1];
    cout << "Sum: " << query(0, 2) << endl;
    cout << "Sum: " << query(2, 4) << endl;
    cout << "Sum: " << query(3, 5) << endl;
    return 0;
}

出力

Sum: 6
Sum: 8
Sum: 9

まとめ

本チュートリアルでは、範囲クエリの処理に非常に役立つスパーステーブルの構築方法について解説しました。テーブルを事前に計算しておくことで、その後のクエリに対してO(logN)という高速な応答が可能になります。紹介したC++プログラムは、C、Java、Pythonなどの他のプログラミング言語でも同様の考え方で実装できます。本チュートリアルが皆さんの学習の一助となれば幸いです。