Bảng thưa (Sparse Table)

Mức độ: Nâng cao

Có 10⁵ câu hỏi “số nhỏ nhất từ vị trí l đến r là bao nhiêu?”. Tổng tiền tố trả lời tổng đoạn bằng một phép trừ, nhưng nhỏ nhất không trừ được: biết nhỏ nhất của 10 số đầu và của 3 số đầu không suy ra được nhỏ nhất của 7 số còn lại. Bảng thưa chuẩn bị trước nhỏ nhất của các đoạn có độ dài là lũy thừa của 2, rồi mỗi câu hỏi ghép từ hai đoạn như vậy.

Chuẩn bị bảng

Gọi bang[j][i] là số nhỏ nhất của đoạn dài 2^j bắt đầu tại i, tức là từ a_i đến a_{i + 2^j - 1}.

• j = 0: đoạn dài 1, bang[0][i] = a[i].
• j lớn hơn 0: đoạn dài 2^j gồm hai nửa dài 2^{j - 1}, nên bang[j][i] = min(bang[j-1][i], bang[j-1][i + 2^(j-1)]).

Dãy 5 2 4 7 1 3 6 8:

j (độ dài)	i = 0	1	2	3	4	5	6	7
0 (1)	5	2	4	7	1	3	6	8
1 (2)	2	2	4	1	1	3	6
2 (4)	2	1	1	1	1
3 (8)	1

Có khoảng log₂n hàng, mỗi hàng n ô, chuẩn bị mất khoảng n × log₂n bước (n = 10⁵ là khoảng 1,7 × 10⁶).

Trả lời câu hỏi

Đoạn [l, r] dài len = r - l + 1. Lấy k lớn nhất mà 2^k ≤ len. Hai đoạn dài 2^k, một bắt đầu tại l, một kết thúc tại r, phủ kín [l, r] (vì 2^k + 2^k ≥ len). Hai đoạn có thể chồng lên nhau, nhưng với phép nhỏ nhất thì một số bị xét hai lần không làm sai kết quả.

min(l, r) = min(bang[k][l], bang[k][r - 2^k + 1])

Đoạn từ 1 đến 6 (2 4 7 1 3 6) dài 6, k = 2: min(bang[2][1], bang[2][3]) = min(1, 1) = 1.

Python

import sys
du_lieu = sys.stdin.read().split()
n, q = int(du_lieu[0]), int(du_lieu[1])
a = list(map(int, du_lieu[2:2 + n]))
bang = [a]
j = 1
while (1 << j) <= n:
    truoc = bang[-1]
    nua = 1 << (j - 1)
    bang.append([min(truoc[i], truoc[i + nua]) for i in range(n - (1 << j) + 1)])
    j += 1
ket_qua = []
vi_tri = 2 + n
for _ in range(q):
    l, r = int(du_lieu[vi_tri]) - 1, int(du_lieu[vi_tri + 1]) - 1   # đề đánh số từ 1
    vi_tri += 2
    k = (r - l + 1).bit_length() - 1                                # 2^k ≤ độ dài
    ket_qua.append(min(bang[k][l], bang[k][r - (1 << k) + 1]))
print("\n".join(map(str, ket_qua)))

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<vector<long long>> bang(1, vector<long long>(n));
    for (auto &x : bang[0]) cin >> x;
    for (int j = 1; (1 << j) <= n; j++) {
        int nua = 1 << (j - 1);
        bang.push_back(vector<long long>(n - (1 << j) + 1));
        for (int i = 0; i + (1 << j) <= n; i++) bang[j][i] = min(bang[j - 1][i], bang[j - 1][i + nua]);
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        l--, r--;                                  // đề đánh số từ 1
        int k = 31 - __builtin_clz(r - l + 1);    // 2^k ≤ độ dài
        cout << min(bang[k][l], bang[k][r - (1 << k) + 1]) << "\n";
    }
    return 0;
}

Mỗi câu hỏi chỉ tốn một phép so sánh. Trong C++, 31 - __builtin_clz(x) là số mũ của lũy thừa 2 lớn nhất không vượt quá x; trong Python là x.bit_length() - 1.

Phép toán nào dùng được?

Bảng thưa trả lời bằng hai đoạn chồng lên nhau, nên chỉ dùng cho phép toán mà xét một số hai lần không làm sai: f(x, x) = x.

Phép toán	Dùng được?	Vì sao
nhỏ nhất, lớn nhất	được	min(x, x) = x
ƯCLN	được	ƯCLN(x, x) = x
AND, OR theo bit	được	x AND x = x
tổng, tích, XOR	không	x + x khác x: phần chồng bị cộng hai lần

Với tổng thì dùng tổng tiền tố. Bảng thưa không cập nhật được khi dãy thay đổi; dãy thay đổi thì dùng cây Fenwick hoặc cây phân đoạn.

Nhảy nhị phân

Ý tưởng “lưu kết quả cho các bước dài 2^j” còn dùng cho câu hỏi nhảy k bước: mỗi vị trí i có một vị trí tiếp theo tiep[i], hỏi sau k bước (k tới 10¹⁸) đang ở đâu. Lưu nhay[j][i] là vị trí sau 2^j bước từ i, với nhay[j][i] = nhay[j-1][nhay[j-1][i]]. Viết k dưới dạng nhị phân, với mỗi bit 1 thứ j thì nhảy 2^j bước. Cách này còn gọi là binary lifting, dùng nhiều ở bài tổ tiên chung gần nhất.

Luyện tập

Gồm 17 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Câu hỏi trên đoạn

Bài 1. Nhỏ nhất trên đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹), q dòng sau mỗi dòng có l, r (1 ≤ l ≤ r ≤ n). Với mỗi câu hỏi, in ra số nhỏ nhất từ a_l đến a_r.

Ví dụ:

Nhập	In ra
8 3 5 2 4 7 1 3 6 8 2 7 3 4 6 8	1 4 3

Kiểm tra: nhập

10 4
9 -3 7 7 0 12 -5 4 4 1
1 3
4 6
1 10
8 10

Xem đáp số

-3
0
-5
1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Mực nước cao nhất

Một trạm đo ghi mực nước sông trong n ngày. Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số (0 ≤ mực nước ≤ 10⁹), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, in ra mực nước cao nhất từ ngày l đến ngày r.

Ví dụ:

Nhập	In ra
7 3 12 15 11 18 14 13 16 1 3 2 6 5 7	15 18 16

Kiểm tra: nhập

10 4
300 120 450 450 90 610 200 610 50 400
1 2
3 5
6 8
9 10

Xem đáp số

300
450
610
400

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Biên độ nhiệt

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có nhiệt độ n ngày (|t_i| ≤ 100), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, in ra (nhiệt độ cao nhất) - (nhiệt độ thấp nhất) từ ngày l đến ngày r.

Ví dụ:

Nhập	In ra
6 3 20 25 18 30 22 19 1 3 2 5 4 4	7 12 0

Kiểm tra: nhập

10 4
-5 3 -12 8 8 0 -1 15 -20 7
1 4
5 7
1 10
8 9

Xem đáp số

20
9
35
35

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. ƯCLN trên đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên dương (a_i ≤ 10⁹), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, in ra ƯCLN của a_l, …, a_r.

Ví dụ:

Nhập	In ra
6 3 12 18 24 9 27 6 1 3 3 5 4 6	6 3 3

Kiểm tra: nhập

10 4
100 75 50 125 30 45 60 7 14 21
1 4
2 6
8 10
1 10

Xem đáp số

25
5
7
1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. AND và OR trên đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (0 ≤ a_i nhỏ hơn 2³⁰), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, in ra trên một dòng hai số: AND và OR của a_l, …, a_r.

Ví dụ:

Nhập	In ra
5 3 12 10 14 7 15 1 2 2 4 1 5	8 14 2 15 0 15

Kiểm tra: nhập

8 4
255 254 127 128 64 192 3 1
1 3
4 6
6 8
1 8

Xem đáp số

126 255
0 192
0 195
0 255

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Vị trí số nhỏ nhất

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, in ra vị trí của số nhỏ nhất trong đoạn từ l đến r (đánh số từ 1); có nhiều vị trí thì in vị trí nhỏ nhất.

Ví dụ:

Nhập	In ra
7 3 4 2 6 2 5 1 3 1 5 3 5 1 7	2 4 6

Kiểm tra: nhập

10 4
7 3 9 3 3 8 1 6 1 2
1 4
2 5
6 10
3 3

Xem đáp số

2
2
7
3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Độ dốc lớn nhất

Đường đi bộ có n cột mốc, độ cao cột thứ i là h_i. Độ dốc giữa hai cột liền nhau là |h_{i + 1} - h_i|. Dòng đầu có n, q (2 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵), dòng thứ hai có n số h_i (0 ≤ h_i ≤ 10⁹), q dòng sau mỗi dòng có l, r (1 ≤ l nhỏ hơn r ≤ n). Với mỗi câu hỏi, in ra độ dốc lớn nhất khi đi từ cột l đến cột r.

Ví dụ:

Nhập	In ra
6 3 10 13 9 9 20 18 1 3 3 4 1 6	4 0 11

Kiểm tra: nhập

10 4
100 90 95 150 140 141 300 290 285 300
1 3
3 6
6 8
1 10

Xem đáp số

10
55
159
159

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Nhỏ nhất trên vòng tròn

n số xếp thành vòng tròn, sau số thứ n là số thứ 1. Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁹), q dòng sau mỗi dòng có l, r (1 ≤ l, r ≤ n). Với mỗi câu hỏi, đi theo vòng từ vị trí l đến vị trí r (nếu l lớn hơn r thì đi qua vị trí n rồi về 1), in ra số nhỏ nhất đã đi qua.

Ví dụ:

Nhập	In ra
6 3 5 9 2 7 4 8 2 4 5 1 6 6	2 4 8

Kiểm tra: nhập

8 4
3 -1 4 1 -5 9 2 6
7 2
3 6
8 1
1 8

Xem đáp số

-1
-5
3
-5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Số chia hết cho mọi số trong đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số nguyên dương (a_i ≤ 10⁹), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, in ra có bao nhiêu vị trí i trong đoạn từ l đến r mà mọi số trong đoạn đều chia hết cho a_i.

Ví dụ:

Nhập	In ra
5 3 2 4 2 6 3 1 4 2 5 2 2	2 0 1

Kiểm tra: nhập

10 4
6 12 6 18 6 3 9 3 3 27
1 5
1 10
6 9
2 4

Xem đáp số

3
3
3
1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Bảng thưa và tìm kiếm nhị phân

Bài 10. Đếm đoạn có ƯCLN bằng 1

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên dương (a_i ≤ 10⁹). In ra số đoạn liên tiếp có ƯCLN các phần tử bằng 1.

Ví dụ:

Nhập	In ra
4 2 3 4 6	5

Kiểm tra: nhập

10
6 10 15 4 8 9 12 7 14 21

Xem đáp số

38

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Đoạn dài nhất có ƯCLN lớn hơn 1

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên dương (a_i ≤ 10⁹). In ra độ dài lớn nhất của một đoạn liên tiếp có ƯCLN các phần tử lớn hơn 1, hoặc 0 nếu không có.

Ví dụ:

Nhập	In ra
6 3 6 4 8 12 5	4

Kiểm tra: nhập

10
7 14 21 2 6 9 15 25 10 1

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Đoạn ngắn nhất có ƯCLN bằng ƯCLN cả dãy

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên dương (a_i ≤ 10⁹). Gọi G là ƯCLN của cả dãy. In ra độ dài nhỏ nhất của một đoạn liên tiếp có ƯCLN bằng G.

Ví dụ:

Nhập	In ra
5 12 18 8 30 20	2

Kiểm tra: nhập

10
60 84 36 90 150 42 70 105 140 210

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Đếm đoạn có AND bằng k

Dòng đầu có n, k (1 ≤ n ≤ 10⁵, 0 ≤ k nhỏ hơn 2³⁰), dòng thứ hai có n số nguyên (0 ≤ a_i nhỏ hơn 2³⁰). In ra số đoạn liên tiếp có AND các phần tử bằng k.

Ví dụ:

Nhập	In ra
4 2 7 6 3 2	6

Kiểm tra: nhập

10 4
12 13 4 6 15 7 5 4 12 28

Xem đáp số

40

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Điểm cao nhất trong đoạn

Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có điểm của n vận động viên theo số áo 1, 2, …, n (0 ≤ điểm ≤ 10⁹), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, in ra số áo của vận động viên điểm cao nhất trong các số áo từ l đến r; nếu nhiều người bằng điểm thì in số áo lớn nhất.

Ví dụ:

Nhập	In ra
6 3 8 9 7 9 6 9 1 3 1 5 5 6	2 4 6

Kiểm tra: nhập

10 4
5 5 2 8 8 3 1 8 7 0
1 2
3 7
1 10
9 10

Xem đáp số

2
5
8
9

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Bảng thưa hai chiều

Bài 15. Nhỏ nhất trên hình chữ nhật

Bảng có m hàng, n cột. Dòng đầu có m, n, q (1 ≤ m, n ≤ 300, 1 ≤ q ≤ 10⁵), m dòng sau mỗi dòng có n số nguyên (|giá trị| ≤ 10⁹), q dòng sau mỗi dòng có r₁, c₁, r₂, c₂ (r₁ ≤ r₂, c₁ ≤ c₂). Với mỗi câu hỏi, in ra số nhỏ nhất trong hình chữ nhật từ hàng r₁ đến r₂, cột c₁ đến c₂.

Ví dụ:

Nhập	In ra
3 4 2 5 8 2 6 7 1 9 4 3 6 5 8 1 1 2 2 2 3 3 4	1 4

Kiểm tra: nhập

4 5 3
9 4 7 3 8
2 6 1 5 9
8 3 7 2 4
5 9 6 1 3
1 1 2 3
3 4 4 5
1 1 4 5

Xem đáp số

1
1
1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Nhảy nhị phân

Bài 16. Nhảy k bước

Có n ô đánh số 1 đến n, từ ô i luôn nhảy sang ô t_i. Dòng đầu có n, q (1 ≤ n, q ≤ 10⁵), dòng thứ hai có n số t_i (1 ≤ t_i ≤ n), q dòng sau mỗi dòng có x, k (1 ≤ x ≤ n, 0 ≤ k ≤ 10¹⁸). Với mỗi câu hỏi, in ra ô đang đứng sau k lần nhảy bắt đầu từ ô x.

Ví dụ:

Nhập	In ra
5 3 2 3 1 5 4 1 4 4 3 2 0	2 5 2

Kiểm tra: nhập

8 4
3 5 6 2 8 1 4 7
1 1000000000000000000
2 7
7 12345
8 1

Xem đáp số

3
8
7
7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Chia đoạn thành ít khúc nhất

Dòng đầu có n, S, q (1 ≤ n, q ≤ 10⁵, 1 ≤ S ≤ 10¹⁴), dòng thứ hai có n số nguyên dương (a_i ≤ S), q dòng sau mỗi dòng có l, r. Với mỗi câu hỏi, in ra số khúc ít nhất khi chia đoạn a_l, …, a_r thành các khúc liên tiếp, mỗi khúc có tổng không quá S.

Ví dụ:

Nhập	In ra
7 10 3 4 5 3 6 2 7 1 1 7 2 4 6 6	3 2 1

Kiểm tra: nhập

10 15 4
8 7 3 9 5 6 10 2 4 12
1 10
3 6
2 9
7 8

Xem đáp số

6
2
5
1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.