使用稀疏表的 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 的幂分解查询。创建一个稀疏表后，我们在该表中搜索查询，并在 ( Left_index + 2^n - 1 <= Right_index ) 条件下继续在变量中添加值) 其中 n 是二维数组的列的大小。

示例

上述方法的 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 <= 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++ 程序，我们可以使用 C、Java、Python 等编程语言来解决这个问题。我们希望本教程对您有所帮助。