Sparse Table (RMQ)

Wiki › Cấu trúc dữ liệu

huunguyen · Last updated 8, Tháng 4, 2026, 15:55

Sparse Table là cấu trúc dữ liệu trả lời truy vấn Range Minimum/Maximum Query (RMQ) trong $O (1)$ sau $O (N \log N)$ tiền xử lý — hiệu quả hơn Segment Tree khi không có cập nhật.

Điều kiện áp dụng: Hàm kết hợp phải là idempotent — tức là $f (a, a) = a$ (ví dụ: min, max, GCD). Không áp dụng cho tổng (vì tổng không idempotent).

Ý tưởng

st[i][j] = giá trị hàm $f$ trên đoạn $[i, i + 2^{j} - 1]$ .

Xây dựng: $st [i] [j] = f (st [i] [j - 1], st [i + 2^{j - 1}] [j - 1])$ .

Truy vấn $[l, r]$ : chọn $k = ⌊ \log_{2} (r - l + 1) ⌋$ , kết hợp hai đoạn chồng nhau $[l, l + 2^{k} - 1]$ và $[r - 2^{k} + 1, r]$ . Vì idempotent, phần chồng nhau không ảnh hưởng kết quả.

Cài đặt

const int MAXN = 2e5 + 5;
const int LOG  = 18;

int st[MAXN][LOG];
int lg[MAXN];   // lg[i] = floor(log2(i))

void build(vector<int>& a, int n) {
    // Tiền tính log
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i/2] + 1;

    // Điền cột đầu
    for (int i = 0; i < n; i++) st[i][0] = a[i];

    // Điền các cột tiếp theo
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 0; i + (1 << j) <= n; i++)
            st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1]);
}

// Truy vấn min trên [l, r] (0-based, inclusive)
int query(int l, int r) {
    int k = lg[r - l + 1];
    return min(st[l][k], st[r - (1 << k) + 1][k]);
}

Ứng dụng: LCA trong $O (1)$

Kết hợp Euler tour + Sparse Table để trả lời LCA trong $O (1)$ :

// Euler tour: dfs ghi vào mảng euler[] mỗi khi vào/ra đỉnh
// first[u]: lần đầu xuất hiện của u trong euler tour
// LCA(u,v) = đỉnh có depth nhỏ nhất trong euler[first[u]..first[v]]

vector<int> euler, depth_euler;
int first[MAXN];
int dep[MAXN];

void dfs(int u, int p, int d) {
    dep[u] = d;
    first[u] = euler.size();
    euler.push_back(u);
    depth_euler.push_back(d);
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u, d+1);
        euler.push_back(u);
        depth_euler.push_back(d);
    }
}

// Sau khi build Sparse Table trên depth_euler:
int lca(int u, int v) {
    int l = first[u], r = first[v];
    if (l > r) swap(l, r);
    // Tìm vị trí min trong depth_euler[l..r]
    int k = lg[r - l + 1];
    int pos = (depth_euler[l + (1<<k) - 1] < depth_euler[r - (1<<k) + 1])
              ? l : r - (1<<k) + 1;
    // Thực ra cần lưu chỉ số, không chỉ giá trị
    return euler[/* pos của min */];
}

Lưu ý: Với RMQ trả về vị trí (không chỉ giá trị), lưu pair<int,int>{value, index} trong Sparse Table.

Sparse Table cho tổng — Prefix Sum

Với tổng (không idempotent), dùng prefix sum $O (N)$ build, $O (1)$ query:

vector<long long> prefix(n+1, 0);
for (int i = 0; i < n; i++) prefix[i+1] = prefix[i] + a[i];

// Sum [l, r] (0-based):
long long range_sum(int l, int r) { return prefix[r+1] - prefix[l]; }

So sánh

Cấu trúc	Build	Query	Cập nhật	Hàm hỗ trợ
Sparse Table	$O (N \log N)$	$O (1)$	Không	Idempotent (min, max, GCD)
Segment Tree	$O (N)$	$O (\log N)$	$O (\log N)$	Mọi hàm kết hợp
Fenwick Tree	$O (N)$	$O (\log N)$	$O (\log N)$	Hàm có nghịch (tổng, XOR)
Prefix Sum	$O (N)$	$O (1)$	Không	Tổng

Khi nào dùng Sparse Table?

RMQ tĩnh (không có cập nhật) — nhanh nhất.
LCA $O (1)$ với Euler tour.
Truy vấn GCD trên đoạn tĩnh.

Bình luận

Không có bình luận tại thời điểm này.