¶ Range Minimum Query (RMQ) - Sparse Table
Tác giả:
- Lê Minh Hoàng - Đại học Khoa học Tự nhiên, ĐHQG-HCM
Reviewer:
- Hồ Ngọc Vĩnh Phát - Đại học Khoa học Tự nhiên, ĐHQG-HCM
- Hoàng Xuân Nhật - Đại học Khoa học Tự nhiên, ĐHQG-HCM
- Nguyễn Anh Bảo - Đại học Bách Khoa Hà Nội
¶ Giới thiệu
Bài toán được phát biểu như sau:
- Cho mảng gồm phần tử và truy vấn có dạng . Với mỗi truy vấn, in ra giá trị nhỏ nhất trong mảng từ đến .
Ví dụ:
Bài toán có nhiều cách giải, nhưng cách phổ biến nhất là:
- Sparse Table: tiền xử lý, mỗi truy vấn.
- Segment Tree: tiền xử lý, mỗi truy vấn.
Sự khác biệt giữa cách giải này nằm ở chỗ, Segment Tree có thể xử lý được hoạt động sửa đổi xen kẽ với các truy vấn, còn Sparse Table thì không.
Nhưng Sparse Table không "phế", sức mạnh của Sparse Table nằm ở khả năng truy vấn trong khi các phép toán thoả mãn tính chất Idempotence: "một giá trị có thể xuất hiện nhiều lần nhưng không làm thay đổi kết quả phép toán", ví dụ như
Và Sparse Table cũng có khả năng truy vấn trong nếu phép toán không thoả mãn tính chất Idempotence (ví dụ như bài toán Range Sum Query ở bên dưới).
Lưu ý: Trong suốt bài viết mình dùng __lg(x) để tính của 1 số vì ta cần giá trị nguyên, còn log2(x) thì trả về số thực. Nếu không muốn dùng hàm thì có thể tính trước như sau:
int lg2[N];
void BuildLog2Array() {
lg2[1] = 0;
for (int i = 2; i < N; ++i)
lg2[i] = lg2[i / 2] + 1;
}
¶ Sparse Table
Đầu tiên, ta sẽ tìm hiểu về ý tưởng để tối ưu thời gian truy vấn từ đến của Sparse Table qua bài toán Range Minimum Query (RMQ), và cách để truy vấn trong nếu phép toán không thoả mãn tính chất Idempotence qua bài toán Range Sum Query (RSQ).
¶ Range Minimum Query (RMQ)
Cho mảng gồm phần tử và truy vấn có dạng . Với mỗi truy vấn, in ra giá trị nhỏ nhất trong mảng từ đến .
Giới hạn:
¶ Thuật toán ngây thơ
Ta duyệt qua tất cả phần tử.
int a[N];
int queryMin(int l, int r) {
int mi = INT_MAX;
for (int i = l; i <= r; ++i) {
mi = min(mi, a[i]);
}
return mi;
}
¶ Phân tích
- Độ phức tạp truy vấn:
- Có truy vấn, vì thế tổng độ phức tạp là
Câu hỏi đặt ra là ta còn có thể tối ưu thời gian truy vấn được hay không?
- Nhận xét: Thay vì duyệt qua từng phần tử, ta có thể duyệt qua từng nhóm phần tử. Từ đó, ta có thể giảm thời gian truy vấn xuống còn
¶ Thuật toán tối ưu 1.1
- Ta xây dựng mảng với công thức $$a2_i = min(a_i, a_{i+1})$$.
- Khi truy vấn, nếu độ dài đoạn cần truy vấn thì ta in ra , nếu thì ra dùng mảng :
int a[N], a2[N];
void preprocess() {
for (int i = 1; i + 1 <= n; ++i) {
a2[i] = min(a[i], a[i + 1]);
}
}
int queryMin(int l, int r) {
int len = r - l + 1;
if (len == 1) return a[l];
int mi = INT_MAX;
for (int i = l; i + 1 <= r; i += 2) {
mi = min(mi, a2[i]);
}
// khi kết thúc vòng lặp phía trên, có thể còn 1 số phần tử chưa được xét
// ví dụ [l, r] = [1, 5], ta chỉ mới xét a[1...4] chứ chưa xét a[5]
// nhận xét: lượng phần tử chưa xét nhỏ hơn 2
// vậy nên ta chỉ cần xét thêm a[r - 1] và a[r]
// (sức mạnh của tính chất Idempotence bắt đầu tại đây)
mi = min(mi, a2[r - 1]);
return mi;
}
¶ Phân tích:
- Độ phức tạp tiền xử lý: (tạo mảng )
- Độ phức tạp truy vấn: ( vòng for và lệnh if cho biến )
- Có truy vấn, vì thế tổng độ phức tạp thời gian là
- Độ phức tạp bộ nhớ: ( mảng và )
¶ Thuật toán tối ưu 1.2
Tương tự 1.1, ta có nhận xét: Thay vì duyệt qua từng nhóm phần tử, ta có thể duyệt qua từng nhóm phần tử.
Từ đó, ta có thể giảm thời gian truy vấn xuống còn
Khi truy vấn:
- Nếu độ dài đoạn cần truy vấn thì ta in ra
- Nếu độ dài đoạn cần truy vấn thoả mãn thì ta in ra
- nếu thì ra dùng mảng :
int a[N], a2[N], a4[N];
void preprocess() {
for (int i = 1; i + 1 <= n; ++i) {
a2[i] = min(a[i], a[i + 1]);
}
for (int i = 1; i + 3 <= n; ++i) {
a4[i] = min(a2[i], a2[i + 2]);
}
}
int queryMin(int l, int r) {
int len = r - l + 1;
if (len == 1) return a[l];
if (len < 4) {
return min(a2[l], a2[r - 1]);
// dòng này hợp lý bởi vì chắc chắn 2 đoạn [l, l + 1] và [r - 1, r] sẽ giao nhau (vì 2 + 2 > len)
}
int mi = INT_MAX;
for (int i = l; i + 3 <= r; i += 4) {
mi = min(mi, a4[i]);
}
mi = min(mi, a4[r - 3]);
return mi;
}
¶ Phân tích:
- Độ phức tạp tiền xử lý: (tạo mảng và )
- Độ phức tạp truy vấn: ( vòng for và lệnh if cho biến )
- Có truy vấn, vì thế tổng độ phức tạp thời gian là
- Độ phức tạp bộ nhớ: ( mảng , và )
¶ Thuật toán tối ưu 1.3
Ta vẫn có thể tối ưu thời gian truy vấn bằng cách duyệt qua các nhóm lớn hơn (nhóm độ lớn phần tử).
int a[N], a2[N], a4[N], a8[N];
void preprocess() {
for (int i = 1; i + 1 <= n; ++i) {
a2[i] = min(a[i], a[i + 1]);
}
for (int i = 1; i + 3 <= n; ++i) {
a4[i] = min(a2[i], a2[i + 2]);
}
for (int i = 1; i + 7 <= n; ++i) {
a8[i] = min(a4[i], a4[i + 4]);
}
}
int queryMin(int l, int r) {
int len = r - l + 1;
if (len == 1) return a[l];
if (len < 4) return min(a2[l], a2[r - 1]);
if (len < 8) return min(a4[l], a4[r - 3]);
int mi = INT_MAX;
for (int i = l; i + 7 <= r; i += 8) {
mi = min(mi, a8[i]);
}
mi = min(mi, a8[r - 7]);
return mi;
}
¶ Phân tích:
- Độ phức tạp tiền xử lý: (tạo mảng , và )
- Độ phức tạp truy vấn: ( vòng for và lệnh if cho biến )
- Có truy vấn, vì thế tổng độ phức tạp thời gian là
- Độ phức tạp bộ nhớ: ( mảng , , và )
¶ Thuật toán tối ưu 1.n
Nếu ta làm tiếp như thuật toán tối ưu (tiếp tục tạo các mảng ) ta sẽ có mảng , độ phức tạp bài toán lúc này như sau:
- Độ phức tạp tiền xử lý: ( mảng )
- Độ phức tạp truy vấn: ( vòng for và lệnh if cho biến )
- Có truy vấn, vì thế tổng độ phức tạp thời gian là
- Độ phức tạp bộ nhớ: (mảng ban đầu và mảng tiền xử lý)
¶ Thuật toán tối ưu 2
Nhưng nếu dùng mảng sẽ mang đến cho ta nhiều bất tiện (code dài, dễ sai, ...). Do đó, ta có thể đặt:
- là giá trị nhỏ nhất của phần tử tính từ (min của ), tương ứng với ) ( ở đây là viết tắt của (parse)(able)).
- Ta có công thức truy hồi sau:
Nhận xét thêm:
- lệnh if trong lúc này thật ra chỉ thực hiện nhiệm vụ: tìm nhỏ nhất thoả mãn (hay nói cách khác là để chắc chắn đoạn và giao nhau nhưng vẫn nằm trong đoạn ).
- Ví dụ:
- , vì
- , vì
- Vậy nên, còn có một cách tính khác là $$k=__lg(len)$$ (phần nguyên của phép )
- Từ đây, ta có thể giảm độ phức tạp truy vấn xuống còn
// LG là số lớn nhất thoả 2^LG < N
// ví dụ: N = 10^5 thì LG = 16 vì 2^16 = 65536
int a[N], st[LG + 1][N];
void preprocess() {
for (int i = 1; i <= n; ++i) st[0][i] = a[i];
for (int j = 1; j <= LG; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
int queryMin(int l, int r) {
int k = __lg(r - l + 1);
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
- Độ phức tạp tiền xử lý:
- Độ phức tạp truy vấn:
- Có truy vấn, vì thế tổng độ phức tạp thời gian là
- Độ phức tạp bộ nhớ:
¶ Range Sum Queries (RSQ)
¶ Bài toán
Cho mảng gồm phần tử và truy vấn có dạng . Với mỗi truy vấn, in ra tổng các phần tử trong mảng từ đến .
Giới hạn:
¶ Ý tưởng
Giống như RMQ, ta vẫn sẽ dựng mảng .
Nhưng lúc này, ta không thể lấy $$k = __lg(len)$$ rồi như RMQ được nữa (vì đoạn chắc chắn giao nhau).
Nhận xét: Ta luôn có thể tách một số nguyên dương thành tổng các lũy thừa phân biệt của 2 (hệ nhị phân). Ví dụ: .
Từ nhận xét trên, ta có thể tách thành đoạn có độ dài như sau:
- Đặt
- Duyệt từ đến $$__lg(len)$$, nếu bit thứ của là thì:
- Ta tách thành và
- (tiếp tục tách như )
¶ Cài đặt
// LG là số lớn nhất thoả 2^LG < N
// ví dụ: N = 10^5 thì LG = 16 vì 2^16 = 65536
int a[N], st[LG + 1][N];
void preprocess() {
for (int i = 1; i <= n; ++i) st[0][i] = a[i];
for (int j = 1; j <= LG; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
st[j][i] = st[j - 1][i] + st[j - 1][i + (1 << (j - 1))];
}
int querySum(int l, int r) {
int len = r - l + 1;
int sum = 0;
for (int j = 0; (1 << j) <= len; ++j)
if (len >> j & 1) {
sum = sum + st[j][l];
l = l + (1 << j);
}
return sum;
}
- Độ phức tạp tiền xử lý:
- Độ phức tạp truy vấn:
- Có truy vấn, vì thế tổng độ phức tạp thời gian là
- Độ phức tạp bộ nhớ:
¶ Lưu ý
Mình biết rằng bài này có cách dễ hơn là dùng Mảng Cộng Dồn, nhưng lý do mảng cộng dồn sử dụng được là vì phép cộng có "phép đảo ngược" là phép trừ.
Nếu xét phép toán nhân ma trận không vuông:
- Phép nhân ma trận không thoả tính chất Idempotence
- Ma trận không vuông không có ma trận nghịch đảo nên không có "phép đảo ngược"
Vậy bài toán lúc này không thể dùng mảng cộng dồn, cũng không thể dùng Sparse Table truy vấn . Do đó, Sparse Table truy vấn là một giải pháp hợp lý (dù khá tốn bộ nhớ so với Segment Tree).
¶ Bài tập áp dụng
- Library Checker - Static RMQ
- VNOJ - AVLBIT (Dãy cấp số cộng)
- Codechef - FRMQ (Chef and Array)
- Codeforces - 5C (Longest Regular Bracket Sequence)
- Codeforces - 1454F (Array Partition)
- Codeforces - 475D (CGCDSSQ)
- Codeforces - 487B (Strip)
¶ Sparse Table 2D
Ta có bài toán như sau:
- Cho một ma trận chiều độ lớn và truy vấn . Với mỗi truy vấn, in ra giá trị nhỏ nhất trong ma trận con có góc trái dưới là và góc phải trên là .
- Giới hạn:
Hiện tại, ta đang có thuật toán:
- Thuật toán ngây thơ: Duyệt qua tất cả phần tử trong ma trận con.
- Độ phức tạp tiền xử lý:
- Độ phức tạp truy vấn:
- Có truy vấn, vì thế tổng độ phức tạp thời gian là
- Độ phức tạp bộ nhớ:
- Thuật toán thông minh: Với mỗi hàng, ta dựng một Sparse Table 1D.
- Độ phức tạp tiền xử lý:
- Độ phức tạp truy vấn:
- Có truy vấn, vì thế tổng độ phức tạp thời gian là
- Độ phức tạp bộ nhớ:
Với giới hạn như trên, rõ ràng cả thuật toán đều không đủ nhanh, và vấn đề nằm ở thời gian truy vấn còn chậm.
Để truy vấn nhanh hơn, ta có thể ứng dụng ý tưởng của Sparse Table 1D vào thuật toán thông minh:
- Xem mỗi Sparse Table 1D của mỗi hàng như "nhóm" phần tử.
- Để gộp "nhóm" phần tử, ta thực hiện gộp từng "phần tử" trong "nhóm".
 |
|---|
 |
| Gộp "nhóm" Sparse Table |
Từ ý tưởng trên, ta xây dựng công thức như sau:
- Đặt là giá trị nhỏ nhất của hình chữ nhật
- Khi , ta dựng Sparse Table 1D của hàng (vì ), là :
- Khi , ta dựng bằng cách gộp và .
Tóm lại, ta có công thức truy hồi như sau:
int a[M][N], st[LGM + 1][M][LGN + 1][N];
void preprocess() {
for (int k = 0; k <= LGM; ++k) {
for (int i = 1; i + (1 << k) - 1 <= m; ++i) {
for (int l = 0; l <= LGN; ++l) {
for (int j = 1; j + (1 << l) - 1 <= n; ++j) {
if (k == 0) {
if (l == 0) {
st[0][i][0][j] = a[i][j];
}
else {
st[0][i][l][j] = min(st[0][i][l - 1][j], st[0][i][l - 1][j + (1 << (l - 1))]);
}
}
else {
st[k][i][l][j] = min(st[k - 1][i][l][j], st[k - 1][i + (1 << (k - 1))][l][j]);
}
}
}
}
}
}
Để truy vấn trong bằng Sparse Table 2D, ta làm tương tự như Bài Toán RMQ, nhưng tách cả chiều và , nghĩa là:
int getMin(int x, int y, int a, int b) {
int k = __lg(a - x + 1);
int l = __lg(b - y + 1);
return min({ st[k][x][l][y],
st[k][x][l][b - (1 << l) + 1],
st[k][a - (1 << k) + 1][l][y],
st[k][a - (1 << k) + 1][l][b - (1 << l) + 1] });
¶ Bài toán: Codechef - Chef and Rectangle Array
Cho ma trận chiều có kích thước .
Một ma trận chiều được gọi là "đẹp" nếu tồn tại một ma trận con sao cho tất cả phần tử đều bằng nhau. Trong một thao tác, ta có thể tăng giá trị của phần tử trong ma trận A lên đơn vị.
Có truy vấn, mỗi truy vấn gồm hai số và , ta cần in ra số thao tác tối thiểu để ma trận được gọi là "đẹp".
Giới hạn:
¶ Ý tưởng
- Duyệt qua tất cả các ma trận con , số thao tác tối thiểu để các phần tử của ma trận con bằng nhau là .
¶ Phân tích độ phức tạp
- Độ phức tạp tiền xử lý:
- Độ phức tạp truy vấn:
- Có truy vấn, vì thế tổng độ phức tạp thời gian là
- Độ phức tạp bộ nhớ:
¶ Cài đặt
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 + 3, LG = 9;
int m, n;
int a[N][N];
int prf[N][N];
int st[LG + 1][N][LG + 1][N];
void preprocess() {
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
prf[i][j] = prf[i - 1][j] + prf[i][j - 1] - prf[i - 1][j - 1] + a[i][j];
}
}
for (int k = 0; k <= LG; ++k) {
for (int i = 1; i + (1 << k) - 1 <= m; ++i) {
for (int l = 0; l <= LG; ++l) {
for (int j = 1; j + (1 << l) - 1 <= n; ++j) {
if (k == 0) {
if (l == 0) {
st[0][i][0][j] = a[i][j];
}
else {
st[0][i][l][j] = max(st[0][i][l - 1][j], st[0][i][l - 1][j + (1 << (l - 1))]);
}
}
else {
st[k][i][l][j] = max(st[k - 1][i][l][j], st[k - 1][i + (1 << (k - 1))][l][j]);
}
}
}
}
}
}
int getSum(int x, int y, int a, int b) {
return prf[a][b] - prf[a][y - 1] - prf[x - 1][b] + prf[x - 1][y - 1];
}
int getMax(int x, int y, int a, int b) {
int k = __lg(a - x + 1);
int l = __lg(b - y + 1);
return max({ st[k][x][l][y],
st[k][x][l][b - (1 << l) + 1],
st[k][a - (1 << k) + 1][l][y],
st[k][a - (1 << k) + 1][l][b - (1 << l) + 1] });
}
int main() {
cin >> m >> n;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> a[i][j];
}
}
preprocess();
int q;
cin >> q;
while (q--) {
int a, b;
cin >> a >> b;
int ans = INT_MAX;
for (int i = a; i <= m; ++i) {
for (int j = b; j <= n; ++j) {
int tmp = getMax(i - a + 1, j - b + 1, i, j) * a * b - getSum(i - a + 1, j - b + 1, i, j);
ans = min(ans, tmp);
}
}
cout << ans << '\n';
}
}