Truy vấn tổng khoảng dùng Sparse Table bằng C++

Sparse Table là cấu trúc dữ liệu trả lời truy vấn khoảng (range query) O(log N) hoặc O(1) cho một số phép toán (min, max, gcd...). Bài này áp dụng cho truy vấn tổng (Range Sum Query).

Xây dựng Sparse Table

ST[i][j] = tổng 2^j phần tử bắt đầu từ chỉ số i. Xây dựng: ST[i][0] = arr[i], ST[i][j] = ST[i][j-1] + ST[i + 2^(j-1)][j-1].

Trả lời truy vấn [L, R]

Duyệt j từ lớn đến nhỏ: nếu L + 2^j - 1 <= R thì cộng ST[L][j] vào kết quả, L += 2^j. Lặp cho đến L > R.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
const int LOG = 16;
long long ST[MAXN][LOG + 1];

long long query(int l, int r) {
    long long sum = 0;
    for (int i = LOG; i >= 0; i--) {
        if (l + (1 << i) - 1 <= r) {
            sum += ST[l][i];
            l += 1 << i;
        }
    }
    return sum;
}

int main() {
    int arr[] = {1, 2, 3, 4, 1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < n; i++) ST[i][0] = arr[i];
    for (int j = 1; j <= LOG; j++)
        for (int i = 0; i + (1 << j) <= n; i++)
            ST[i][j] = ST[i][j-1] + ST[i + (1 << (j-1))][j-1];
    cout << "Sum: " << query(0, 2) << endl;
    cout << "Sum: " << query(2, 4) << endl;
    cout << "Sum: " << query(3, 5) << endl;
    return 0;
}

Kết quả

Sum: 6 Sum: 8 Sum: 9

Kết luận

Range Sum Query bằng Sparse Table: tiền xử lý O(N log N), truy vấn O(log N). Code C++.