Range Query trên mảng tĩnh
📚 Sparse Table: RMQ O(1) và các mở rộng
Sparse Table tiền xử lý các đoạn có độ dài là lũy thừa của 2. Sau O(n log n) tiền xử lý, truy vấn min/max/gcd trên đoạn được trả lời trong O(1).
BuildO(n log n)
QueryO(1)
MemoryO(n log n)
StaticKhông phù hợp update
Mục tiêu bài học
Cần nắm được
st[k][i]lưu gì.- Công thức xây bảng.
- Công thức truy vấn RMQ O(1).
- Vì sao min/max/gcd dùng được còn sum/xor không dùng công thức chồng lấn.
Khi nào dùng?
- Mảng không thay đổi.
- Số truy vấn lớn.
- Phép toán idempotent: min, max, gcd, AND, OR.
- Cần query rất nhanh.
1. Ý tưởng cốt lõi
Ta tiền xử lý kết quả cho mọi đoạn có độ dài 1,2,4,8,....
st[k][i] = kết quả trên đoạn [i, i + 2k - 1]
k = 0
st[0][i] = a[i]
k = 1
Độ dài 2.
k = 2
Độ dài 4.
Công thức xây:
st[k][i] = min(st[k-1][i], st[k-1][i + 2^(k-1)]).2. Mô phỏng xây Sparse Table
Nhấn “Xây bảng”.
3. Truy vấn RMQ O(1)
Với len=R-L+1, chọn k=floor(log2(len)). Lấy hai đoạn dài 2^k phủ từ hai đầu.
min(L,R) = min(st[k][L], st[k][R - 2k + 1])
Xây bảng trước, sau đó nhập L và R.
Hai đoạn được phép chồng lấn vì min idempotent:
min(x,x)=x.4. Phân tích thuật toán
| Phần | Độ phức tạp | Giải thích |
|---|---|---|
| Tiền xử lý log | O(n) | lg[i]=lg[i/2]+1. |
| Xây bảng | O(n log n) | Khoảng log n tầng, mỗi tầng tối đa n trạng thái. |
| Query min/max/gcd | O(1) | Hai đoạn chồng lấn. |
| Bộ nhớ | O(n log n) | Lưu toàn bộ các tầng. |
| Update | Không phù hợp | Nếu có cập nhật, dùng Segment Tree. |
Điều kiện: Công thức O(1) bằng hai đoạn chồng lấn chỉ đúng trực tiếp cho phép toán idempotent. Sum và xor sẽ đếm lặp phần giao.
5. Code mẫu
#include <bits/stdc++.h>
using namespace std;
struct SparseTableMin {
int n, K;
vector<int> lg;
vector<vector<long long>> st;
SparseTableMin(const vector<long long>& a) {
n = (int)a.size();
lg.assign(n + 1, 0);
for (int i = 2; i <= n; i++)
lg[i] = lg[i / 2] + 1;
K = lg[n] + 1;
st.assign(K, vector<long long>(n));
st[0] = a;
for (int k = 1; k < K; k++) {
int len = 1 << k;
int half = len >> 1;
for (int i = 0; i + len <= n; i++) {
st[k][i] = min(st[k - 1][i],
st[k - 1][i + half]);
}
}
}
long long query(int l, int r) const {
int len = r - l + 1;
int k = lg[len];
return min(st[k][l],
st[k][r - (1 << k) + 1]);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<long long> a(n);
for (long long &x : a) cin >> x;
SparseTableMin rmq(a);
while (q--) {
int l, r;
cin >> l >> r;
--l; --r;
cout << rmq.query(l, r) << '\n';
}
}long long queryGcd(int l, int r) {
int k = lg[r - l + 1];
return std::gcd(
st[k][l],
st[k][r - (1 << k) + 1]
);
}class SparseTableMin:
def __init__(self, a):
self.n = len(a)
self.lg = [0] * (self.n + 1)
for i in range(2, self.n + 1):
self.lg[i] = self.lg[i // 2] + 1
self.K = self.lg[self.n] + 1
self.st = [[0] * self.n for _ in range(self.K)]
self.st[0] = a[:]
for k in range(1, self.K):
length = 1 << k
half = length >> 1
for i in range(self.n - length + 1):
self.st[k][i] = min(
self.st[k - 1][i],
self.st[k - 1][i + half]
)
def query(self, left, right):
k = self.lg[right - left + 1]
return min(
self.st[k][left],
self.st[k][right - (1 << k) + 1]
)6. Giải thích code từ bản chất đến công thức
Mục tiêu của phần này: không chỉ nhớ công thức, mà phải trả lời được ba câu hỏi: mỗi tầng quản lý đoạn dài bao nhiêu, vì sao nửa phải dịch đúng
2^(k-1) vị trí, và mảng lg chọn tầng nào cho đoạn truy vấn.6.1. Ý nghĩa chính xác của st[k][i]
kSố tầng. Tầng
k quản lý các đoạn có độ dài 2^k.iVị trí bắt đầu của đoạn.
st[k][i]Giá trị nhỏ nhất trên đoạn
[i, i + 2^k - 1].st[k][i] = min của đoạn [i, i + 2k - 1]
| Tầng k | Độ dài 2k | st[k][i] quản lý |
|---|---|---|
| 0 | 1 | [i, i] |
| 1 | 2 | [i, i+1] |
| 2 | 4 | [i, i+3] |
| 3 | 8 | [i, i+7] |
6.2. Mảng lg dùng để chọn tầng, không quản lý trực tiếp đoạn
lg[len] trả về số nguyên lớn nhất k sao cho 2^k ≤ len. Nói cách khác:
lg[len] = ⌊log2(len)⌋
lg.assign(n + 1, 0);
for (int len = 2; len <= n; len++) {
lg[len] = lg[len / 2] + 1;
}Phải bắt đầu từ 2. Ta cần
lg[1]=0. Nếu lặp từ i=1 thì lg[1]=lg[0]+1=1, sai vì log2(1)=0.Vì sao dùng len/2? Khi chia độ dài cho 2, số mũ lớn nhất của 2 giảm đúng 1. Do đó lg[len] = lg[len/2] + 1.
Không dùng sqrt(len) vì căn bậc hai không cho biết số mũ tầng. Ví dụ len=64: sqrt(64)=8, nhưng tầng đúng là log2(64)=6.
| len | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|
| lg[len] | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 | 4 |
6.3. Công thức quan trọng nhất khi xây Sparse Table
Đoạn dài 2^k được ghép từ hai đoạn liên tiếp, mỗi đoạn dài 2^(k-1).
st[k][i] = min(st[k-1][i], st[k-1][i + 2k-1])
i1
i+12
i+23
i+34
i+45
i+56
i+67
i+78
st[k-1][i]: nửa tráist[k-1][i + 2^(k-1)]: nửa phảiHình minh họa với k=3: đoạn cha dài 2^3=8; mỗi nửa dài 2^2=4; nửa phải bắt đầu tại i+4.
1
Độ dài đoạn cha:
2^k.2
Độ dài mỗi nửa:
2^(k-1).3
Nửa trái bắt đầu tại:
i.4
Nửa phải bắt đầu tại:
i + 2^(k-1), viết trong C++ là i + (1 << (k-1)).Không dùng
i+k. k chỉ là số tầng. Khoảng dịch cần dùng là độ dài nửa đoạn, tức 2^(k-1).6.4. Vì sao điều kiện build là i + len <= n?
Code mẫu dùng chỉ số 0-based. Đoạn bắt đầu tại i, dài len, kết thúc tại i+len-1. Điều kiện không vượt mảng là:
i + len - 1 ≤ n - 1 ⇔ i + len ≤ n
Nếu dùng 1-based như code ban đầu: điều kiện tương đương là
i + (1<<k) - 1 <= n. Hai cách viết đều đúng, nhưng phải thống nhất hệ chỉ số.6.5. Công thức truy vấn RMQ O(1)
long long query(int l, int r) const {
int len = r - l + 1;
int k = lg[len];
return min(
st[k][l],
st[k][r - (1 << k) + 1]
);
}1
len = r-l+1: tính độ dài đoạn cần hỏi.2
k = lg[len]: chọn tầng lớn nhất có 2^k ≤ len.3
st[k][l]: đoạn dài 2^k bám từ đầu trái.4
st[k][r-2^k+1]: đoạn dài 2^k bám đến đầu phải.Ví dụ 0-based: truy vấn [1,6]
Đoạn trái:
Đoạn phải bắt đầu tại
Hai đoạn phủ toàn bộ
len=6, nên k=lg[6]=2 và 2^k=4.Đoạn trái:
[1,4].Đoạn phải bắt đầu tại
6-4+1=3, nên là [3,6].Hai đoạn phủ toàn bộ
[1,6]; phần [3,4] bị chồng lấn nhưng không làm sai phép min.0A[0]
1A[1]
2A[2]
3A[3]
4A[4]
5A[5]
6A[6]
7A[7]
chỉ đoạn tráiphần chồng lấnchỉ đoạn phải
6.6. Vì sao min dùng được hai đoạn chồng lấn, còn sum thì không?
Min là idempotent:
min(x,x)=x. Một phần tử xuất hiện ở cả hai đoạn vẫn chỉ ảnh hưởng như xuất hiện một lần.Sum không idempotent:
x+x≠x. Phần giao sẽ bị cộng hai lần. Range sum tĩnh nên dùng Prefix Sum; phép toán kết hợp tổng quát có thể dùng Disjoint Sparse Table.7. Kiến thức mở rộng
Disjoint Sparse Table
Build O(n log n), query O(1) cho phép toán associative như sum, xor, product. Hai phần dùng để query không chồng lấn.
Argmin / Argmax
Lưu chỉ số thay vì giá trị để biết vị trí phần tử nhỏ nhất/lớn nhất.
2D Sparse Table
Truy vấn min/max trên hình chữ nhật tĩnh, nhưng bộ nhớ lớn: O(nm log n log m).
Fischer–Heun RMQ
Lý thuyết nâng cao đạt build O(n), query O(1), nhưng Sparse Table đơn giản hơn và phù hợp đa số bài thi.
| Cấu trúc | Build | Query | Update | Dùng khi |
|---|---|---|---|---|
| Sparse Table | O(n log n) | O(1) | Không tốt | RMQ tĩnh |
| Segment Tree | O(n) | O(log n) | O(log n) | Có cập nhật |
| Fenwick | O(n) | O(log n) | O(log n) | Tổng prefix/range |
| Prefix Sum | O(n) | O(1) | Không tốt | Range sum tĩnh |
| Disjoint Sparse Table | O(n log n) | O(1) | Không tốt | Phép toán associative |
8. Lỗi hay gặp
- Nhầm 0-based và 1-based.
- Tính sai vị trí đoạn phải.
- Build vượt giới hạn mảng.
- Dùng Sparse Table khi có update.
- Dùng công thức chồng lấn cho sum/xor.
- Dùng
log2()số thực trong query và gặp sai số.
9. Quiz và bài tập
Câu 1.
st[k][i] lưu đoạn nào?Câu 2. Vì sao query min được dùng hai đoạn chồng lấn?
📘 Cơ bản
- RMQ min.
- RMQ max.
- GCD trên đoạn.
📗 Trung bình
- Trả về chỉ số min.
- Binary search kết hợp RMQ.
- Longest subarray thỏa điều kiện min/max.
📙 Nâng cao
- 2D Sparse Table.
- Disjoint Sparse Table cho xor/sum.
- LCA bằng Euler Tour + RMQ.
🐉 HSG
- Cartesian Tree + RMQ.
- GCD subarray compression.
- So sánh Sparse Table và Fischer–Heun.
💳 Quét mã ủng hộ tuỳ tâm nhé!