Sparse Table (RMQ)

Sparse Table là cấu trúc dữ liệu trả lời truy vấn Range Minimum/Maximum Query (RMQ) — và tổng quát là mọi truy vấn đoạn với hàm idempotent — trong $O(1)$ mỗi truy vấn, sau khi tiền xử lý $O(N\log N)$. So với cách ngây thơ quét lại cả đoạn ($O(N)$ mỗi truy vấn, tổng $O(NQ)$), Sparse Table đưa tổng chi phí xuống $O(N\log N+Q)$. Đây là lựa chọn nhanh nhất cho RMQ tĩnh (mảng không thay đổi giữa các truy vấn), nhanh hơn cả Segment Tree về hằng số và độ phức tạp truy vấn.

Điều kiện áp dụng — quan trọng: để truy vấn được $O(1)$, hàm kết hợp $f$ phải idempotent, tức $f(a,a)=a$. Các hàm thỏa: $min$, $max$, $gcd$, $\text{lcm}$, AND bit, OR bit. Hàm không idempotent như tổng (+) thì không dùng được kiểu truy vấn $O(1)$ hai-đoạn-chồng (với tổng hãy dùng prefix sum hoặc Fenwick/Segment Tree).

Ý tưởng / Trực giác

Ý tưởng cốt lõi: mọi đoạn đều phủ được bằng hai đoạn có độ dài là lũy thừa của 2, chồng lên nhau.

Ta định nghĩa $$\text{st}[j][i]=f(a_i,a_{i+1},\dots ,a_{i+2^j-1}),$$ tức giá trị của $f$ trên đoạn bắt đầu tại $i$, dài đúng $2^j$ phần tử. Bảng này có $\log N$ tầng (theo $j$), mỗi tầng $N$ phần tử.

Vì sao xây được nhanh? Một đoạn dài $2^j$ chính là ghép của hai đoạn dài $2^{j-1}$ liền kề: $$\text{st}[j][i]=f(\text{st}[j-1][i],\text{st}[j-1][i+2^{j-1}]).$$ Mỗi ô tính trong $O(1)$ từ tầng dưới, nên xây toàn bộ bảng là $O(N\log N)$.

Vì sao truy vấn $O(1)$ và vì sao cần idempotent? Cho đoạn $[l,r]$ độ dài $\text{len}=r-l+1$. Đặt $k=\lfloor {\log }_2\text{len}\rfloor$, khi đó $2^k\le \text{len}<2^{k+1}$. Ta phủ $[l,r]$ bằng đúng hai đoạn dài $2^k$:

• đoạn trái: $[l,l+2^k-1]$,
• đoạn phải: $[r-2^k+1,r]$.

Vì $2^k>\text{len}/2$, hai đoạn này chồng nhau ở giữa và cùng nhau phủ kín $[l,r]$. Kết quả là $f(\text{st}[k][l],\text{st}[k][r-2^k+1])$. Phần chồng bị tính hai lần, nhưng vì $f$ idempotent ($f(x,x)=x$, và $f$ kết hợp + giao hoán), tính lặp không làm sai kết quả — đó chính là lý do cần idempotent. Với tổng thì phần chồng bị cộng đôi nên sai.

Ví dụ chạy tay

Mảng (0-based), tìm min trên đoạn:

chỉ số:  0   1   2   3   4   5   6   7
giá trị: 3   2   4   5   1   1   5   3

Bước 1 — xây bảng. Tầng $j=0$ là chính mảng. Tầng $j$ ghép hai ô tầng $j-1$:

st[0][i] = a[i]:
i:        0   1   2   3   4   5   6   7
          3   2   4   5   1   1   5   3

st[1][i] = min(st[0][i], st[0][i+1])  (đoạn dài 2):
i:        0   1   2   3   4   5   6
          2   2   4   1   1   1   3
          ^ min(3,2)=2     ^ min(5,1)=1

st[2][i] = min(st[1][i], st[1][i+2])  (đoạn dài 4):
i:        0   1   2   3   4
          2   1   1   1   1
              ^ min(st[1][1],st[1][3])=min(2,1)=1

st[3][i] = min(st[2][i], st[2][i+4])  (đoạn dài 8):
i:        0
          1
          ^ min(st[2][0],st[2][4])=min(2,1)=1

Bước 2 — truy vấn min trên $[2,4]$ (giá trị 4, 5, 1, kỳ vọng 1).

len = 4 - 2 + 1 = 3
k   = floor(log2(3)) = 1   ->  2^k = 2

đoạn trái:  [l, l+2^k-1] = [2, 3]   -> st[1][2] = min(4,5) = 4
đoạn phải:  [r-2^k+1, r] = [3, 4]   -> st[1][3] = min(5,1) = 1

phủ:   l=2   3   r=4
        [---trái---]
            [---phải---]
                ^ chỉ số 3 nằm trong cả hai (chồng), không sao vì idempotent

kết quả = min(4, 1) = 1   ✓

Chỉ 2 phép so sánh cho một truy vấn, bất kể đoạn dài bao nhiêu.

Cài đặt

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
const int LOG  = 18;          // 2^18 > 2*10^5

int st[LOG][MAXN];            // st[j][i]: f trên [i, i+2^j-1]
int lg[MAXN];                 // lg[x] = floor(log2(x)), tính sẵn

void build(const vector<int>& a, int n) {
    // bảng log dựng sẵn để truy vấn không gọi log2() (chậm + sai số float)
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;

    // tầng đáy: đoạn dài 1 chính là phần tử
    for (int i = 0; i < n; i++) st[0][i] = a[i];

    // mỗi đoạn dài 2^j = ghép hai đoạn dài 2^(j-1) liền kề
    for (int j = 1; j < LOG; j++)
        for (int i = 0; i + (1 << j) <= n; i++)
            st[j][i] = min(st[j-1][i], st[j-1][i + (1 << (j-1))]);
}

// min trên [l, r], 0-based, bao gồm hai đầu mút
int query(int l, int r) {
    int k = lg[r - l + 1];                       // 2^k là đoạn lớn nhất <= len
    return min(st[k][l], st[k][r - (1 << k) + 1]); // hai đoạn chồng nhau
}

Lưu ý cách đặt chỉ số st[j][i] (tầng trước, vị trí sau) giúp truy cập bộ nhớ liền mạch theo i khi xây — thân thiện cache hơn st[i][j].

Độ phức tạp

So sánh nhanh với các cấu trúc khác:

Quy tắc chọn: mảng tĩnh + hàm idempotent → Sparse Table; có cập nhật → Segment Tree/Fenwick.

⚠️ Lỗi thường gặp

• Dùng cho hàm không idempotent (tổng). Truy vấn hai-đoạn-chồng cộng đôi phần giữa → kết quả sai. Triệu chứng: tổng lớn hơn thực tế. Cách tránh: với tổng dùng prefix sum/Fenwick; chỉ dùng Sparse Table cho min/max/gcd/AND/OR. (Có biến thể "disjoint sparse table" cho hàm bất kỳ, nhưng truy vấn phức tạp hơn.)

• Có thao tác cập nhật mà vẫn cố dùng Sparse Table. Sparse Table không hỗ trợ cập nhật hiệu quả: đổi một phần tử có thể phải xây lại $O(N\log N)$. Nếu đề có lệnh gán/sửa giá trị xen kẽ truy vấn → chuyển sang Segment Tree. Triệu chứng: TLE vì rebuild mỗi lần sửa.

• Tính $k$ bằng log2() của float. (int)log2(r-l+1) có thể trả sai do sai số dấu phẩy động (vd ra $2$ thay vì $3$), gây truy vấn lệch đoạn → kết quả sai âm thầm. Cách tránh: dựng sẵn mảng lg[] bằng quy hoạch lg[i] = lg[i/2] + 1 như trong code.

• Tràn số khi $f$ là tổng-biến-tướng hoặc tích. Với min/max thường an toàn, nhưng nếu lưu giá trị cộng dồn/nhân hãy dùng long long. Với $a_i\le {10}^9$ mà cộng nhiều phần tử, int tràn.

• Nhầm chỉ số đoạn phải. Đoạn phải phải là $[r-2^k+1,r]$, tức st[k][r - (1<<k) + 1]. Viết thiếu +1 (thành r - (1<<k)) là off-by-one phổ biến → đọc sai đoạn. Kiểm tra: khi $\text{len}$ là lũy thừa của 2, hai chỉ số trái/phải phải trùng nhau.

• Lẫn lộn 0-based và 1-based. Code mẫu dùng 0-based, bao gồm hai đầu. Nếu đề cho $[a,b]$ 1-based, nhớ trừ 1 cho cả hai trước khi gọi query.

• LOG đặt thiếu. Cần $2^{\text{LOG}}>N$. Với $N=2·{10}^5$ phải có LOG >= 18. Đặt thiếu (vd LOG = 17) làm tầng cao nhất không đủ phủ → truy ra ngoài bảng / kết quả sai với đoạn dài.

Biến thể / Mở rộng

• Range GCD / LCM / AND / OR. Đổi min thành __gcd, &, |. GCD là idempotent ($gcd(x,x)=x$) nên dùng được $O(1)$. Kết hợp với tìm kiếm nhị phân trên độ dài đoạn là kỹ thuật mạnh (xem bài gcdstab).

• LCA $O(1)$ qua Euler Tour. Duyệt Euler cây, ghi lại độ sâu theo thứ tự thăm. LCA của $u,v$ là đỉnh có độ sâu nhỏ nhất trong đoạn Euler giữa lần xuất hiện đầu của $u$ và $v$ → đúng RMQ trên mảng độ sâu. Lưu cặp (độ sâu, chỉ số đỉnh) để lấy ra đỉnh.

vector<int> euler;        // dãy đỉnh theo Euler tour
vector<int> depEuler;     // độ sâu tương ứng
int firstOcc[MAXN];       // vị trí xuất hiện đầu tiên của mỗi đỉnh trong euler

void dfs(int u, int p, int d) {
    firstOcc[u] = euler.size();
    euler.push_back(u);
    depEuler.push_back(d);
    for (int v : adj[u]) if (v != p) {
        dfs(v, u, d + 1);
        euler.push_back(u);        // quay lại u sau mỗi cây con
        depEuler.push_back(d);
    }
}
// Xây Sparse Table trên depEuler lưu argmin (chỉ số có độ sâu nhỏ nhất);
// LCA(u,v): l = min(firstOcc[u], firstOcc[v]); r = max(...);
//           idx = argmin trên depEuler[l..r]; LCA = euler[idx].
// Khoảng cách: dist(u,v) = dep[u] + dep[v] - 2*dep[LCA(u,v)].

Đây là cách trả lời truy vấn LCA / khoảng cách trên cây trong $O(1)$ mỗi truy vấn (xem bài distqry).

Bài tập luyện

• Truy Vấn Nhỏ Nhất Đoạn Tĩnh (staticrmin) — (Trung cấp) RMQ tĩnh thuần túy: mảng cố định, $q$ truy vấn min trên đoạn — bài chuẩn để cài Sparse Table lần đầu.
• Truy Vấn Nhỏ Nhất Đoạn Động (dynrmin) — (Trung cấp) Bài tương phản: có lệnh gán $x_k=u$ xen kẽ truy vấn. Sparse Table không cập nhật được hiệu quả; bài này phải dùng Segment Tree — giúp bạn nhận ra ranh giới áp dụng của Sparse Table.
• Truy vấn khoảng cách (distqry) — (Nâng cao) Khoảng cách hai đỉnh trên cây qua LCA; cài Euler tour + Sparse Table RMQ để trả lời mỗi truy vấn $O(1)$.
• Ổn định mảng (phiên bản GCD) (gcdstab) — (Kỳ cựu) Truy vấn GCD trên đoạn (idempotent) kết hợp tìm kiếm nhị phân/hai con trỏ trên độ dài cửa sổ — ứng dụng nâng cao của Sparse Table ngoài min/max.