スパーステーブルを使用したC++範囲合計クエリ

Sparsh Tableはデータ構造であり、範囲クエリの結果を提供するために使用されます。これは、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次元配列を使用します。スパーステーブルでは、2の累乗でクエリを分割します。スパーステーブルを作成した後、そのテーブルでクエリを検索し、（Left_index + 2 ^ n --1 <=Right_indexの条件で変数に値を追加し続けます）ここで、nは2次元配列の列のサイズです。

例

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

#include <bits/stdc++.h>
using namespace std;
// Maximum value of row of sparse table.
const int m = 1e5;
const int n = 16;
long long SPARSE[m][n + 1];
// query to be found with the help of a sparse table.
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]);
    // Building sparse table.
    for (int i = 0; i < z; i++)
        SPARSE[i][0] = arr[i];
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= z - (1 << j); 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: 4

結論

このチュートリアルでは、さまざまなクエリに非常に役立つスパーステーブルの作成について説明しました。スパーステーブルを作成し、そのテーブルからクエリを取得することで、この問題を解決する簡単なアプローチについて説明しました。また、C、Java、Pythonなどのプログラミング言語で実行できるこの問題のC++プログラムについても説明しました。このチュートリアルがお役に立てば幸いです。