Sparse Table

Bảng lũy thừa hai

Gọi st[k][i] là giá trị nhỏ nhất của đoạn dài $2^k$ bắt đầu tại $i$, tức $a[i..i + 2^k - 1]$. Mức 0 là chính dãy, st[0][i] = a[i]. Một đoạn dài $2^k$ là hai nửa liền nhau dài $2^{k-1}$, nên

Dựng lần lượt từ mức thấp lên, mỗi mức có không quá $n$ ô và có $\lfloor \log_2 n \rfloor + 1$ mức: $O(n \log n)$ thời gian và bộ nhớ. Với $n = 2 \cdot 10^5$ cần 18 mức, khoảng $3{,}6 \cdot 10^6$ ô.

Trả lời một đoạn. Đoạn $[l, r]$ dài $L = r - l + 1$, lấy $k = \lfloor \log_2 L \rfloor$. Khối $[l, l + 2^k - 1]$ ở đầu trái và khối $[r - 2^k + 1, r]$ ở đầu phải đều nằm trong đoạn, và vì $2^{k+1} > L$ nên hai khối phủ kín đoạn, có thể chồng lên nhau. Phần chồng được xét hai lần nhưng không làm sai min, nên đáp án là min(st[k][l], st[k][r - (1 << k) + 1]).

Tính sẵn lg[x] $= \lfloor \log_2 x \rfloor$ bằng lg[x] = lg[x / 2] + 1 để khỏi gọi hàm log trên số thực.

Ví dụMức Thấp Nhất

Đề. Dãy $n \le 2 \cdot 10^5$ số không đổi, $q \le 2 \cdot 10^5$ câu hỏi: in giá trị nhỏ nhất trên đoạn $[l, r]$.

Lời giải. Dựng bảng thưa như trên, mỗi câu hỏi đọc hai ô.

Bước 1: dựng bảng. st[k][i] là min của $2^k$ phần tử bắt đầu ở $i$; mức $k$ ghép hai khối liền nhau của mức $k - 1$. Chỉ dựng các ô có $i + 2^k - 1 \le n$, tức khối còn nằm trong dãy. lg[i] $= \lfloor \log_2 i \rfloor$ tính sẵn bằng lg[i / 2] + 1, để câu hỏi khỏi gọi hàm log.

for (ll i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
for (ll k = 1; k < LG; k++)
    for (ll i = 1; i + (1 << k) - 1 <= n; i++)
        st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);

Bước 2: trả lời một đoạn. Với $k = \lfloor \log_2 (r - l + 1) \rfloor$, hai khối dài $2^k$, một bắt đầu ở $l$, một kết thúc ở $r$, phủ trọn đoạn và có thể chồng nhau; min không bận tâm phần chồng. Cả hai khối đều nằm trong $[l, r]$ nên không bao giờ đọc ô ngoài dãy.

ll get(ll l, ll r) {
    ll k = lg[r - l + 1];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}

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

const ll N = 2e5 + 5, LG = 18;
ll n, q, lg[N], st[LG][N];

ll get(ll l, ll r) {
    ll k = lg[r - l + 1];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (ll i = 1; i <= n; i++) cin >> st[0][i];
    for (ll i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    for (ll k = 1; k < LG; k++)
        for (ll i = 1; i + (1 << k) - 1 <= n; i++)
            st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
    while (q--) {
        ll l, r;
        cin >> l >> r;
        cout << get(l, r) << '\n';
    }
}

ChạyInput7 4
8 3 6 2 7 2 5
1 3
2 6
4 4
5 7

Output3
2
2
2

Bảng $18 \times 2 \cdot 10^5$ ô dựng trong $O(n \log n)$, mỗi câu hỏi $O(1)$.

Bảng chiếm nhiều bộ nhớ nên cách khai báo cũng đáng chú ý. Vòng ngoài là mức $k$, vòng trong là $i$, vậy st[k][i] để $k$ ở chỉ số đầu thì vòng trong đi liền mạch:

Viết st[i][k] chậm hơn khoảng 2,5 lần, vì bảng được dựng từng mức một và st[k][i] giữ cả mức nằm liền nhau; long long chậm hơn khoảng 1,6 lần. Dựng theo mức thì đặt $k$ ở chỉ số đầu, và dùng int khi giá trị đủ nhỏ.

Phép gộp hợp lệ

Cách trả lời bằng hai khối chồng nhau cần phép gộp $f$ kết hợp (gộp theo thứ tự nào cũng được) và lũy đẳng, $f(x, x) = x$. Min và max thỏa, GCD thỏa vì $\gcd(x, x) = x$, AND và OR theo bit cũng thỏa. Có thể giữ nhiều bảng song song, chẳng hạn một bảng min và một bảng max cho độ chênh của đoạn.

Tổng thì không: phần chồng bị cộng hai lần. Tổng trên đoạn tĩnh đã có tổng tiền tố (bài 02) trả lời $O(1)$; nếu buộc dùng bảng cho phép gộp không lũy đẳng, tách $[l, r]$ thành các khối rời nhau theo các bit của $L$, mất $O(\log n)$ mỗi câu. Bảng thưa cũng không hợp với cập nhật: một phần tử nằm trong tới $2^k$ ô ở mức $k$, tổng cộng khoảng $2n$ ô phải sửa.

Với GCD, mỗi câu hỏi tốn thêm $O(\log V)$ cho phép tính GCD, $V$ là giá trị lớn nhất, nhưng vẫn nhanh hơn nhiều so với cây phân đoạn vì chỉ có một phép gộp.

Ví dụKhác Ước Chung

Đề. Dãy $n \le 10^5$ số nguyên dương. Mỗi câu hỏi $[l, r]$: gọi $g$ là GCD của đoạn, đếm số vị trí trong đoạn có $a_i \ne g$.

Lời giải. GCD của đoạn chia hết mọi phần tử của đoạn, nên phần tử khác $g$ chính là phần tử lớn hơn $g$; đáp án là độ dài đoạn trừ số phần tử bằng đúng $g$. Việc còn lại là lấy $g$ và đếm số lần $g$ xuất hiện trong $[l, r]$. Với đoạn $[4, 7]$ là $6, 9, 3, 6$: $g = 3$, chỉ một vị trí bằng 3, đáp án 3.

Bước 1: bảng thưa GCD. Như bảng min, thay min bằng __gcd. GCD lũy đẳng ($\gcd(x, x) = x$) nên hai khối chồng nhau vẫn cho đúng.

ll get(ll l, ll r) {
    ll k = lg[r - l + 1];
    return __gcd(st[k][l], st[k][r - (1 << k) + 1]);
}

Bước 2: các vị trí theo giá trị. Sắp các cặp (giá trị, chỉ số) tăng dần. Các vị trí cùng giá trị $g$ nằm liền nhau và tăng theo chỉ số, nên hai lần lower_bound với $(g, l)$ và $(g, r + 1)$ chặn đúng các vị trí có giá trị $g$ và chỉ số trong $[l, r]$.

ll g = get(l, r);
ll same = lower_bound(v + 1, v + n + 1, make_pair(g, r + 1)) - lower_bound(v + 1, v + n + 1, make_pair(g, l));
cout << r - l + 1 - same << '\n';

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

const ll N = 1e5 + 5, LG = 17;
ll n, q, lg[N], st[LG][N];
pair<ll, ll> v[N];

ll get(ll l, ll r) {
    ll k = lg[r - l + 1];
    return __gcd(st[k][l], st[k][r - (1 << k) + 1]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> st[0][i];
        v[i] = {st[0][i], i};
    }
    sort(v + 1, v + n + 1);
    for (ll i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    for (ll k = 1; k < LG; k++)
        for (ll i = 1; i + (1 << k) - 1 <= n; i++)
            st[k][i] = __gcd(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
    cin >> q;
    while (q--) {
        ll l, r;
        cin >> l >> r;
        ll g = get(l, r);
        ll same = lower_bound(v + 1, v + n + 1, make_pair(g, r + 1)) - lower_bound(v + 1, v + n + 1, make_pair(g, l));
        cout << r - l + 1 - same << '\n';
    }
}

ChạyInput7
6 10 15 6 9 3 6
5
1 3
1 4
4 7
1 1
1 7

Output3
4
3
0
7

Dựng $O(n \log n)$, mỗi câu hỏi $O(\log n)$ cho hai lần chặt nhị phân.

Chặt nhị phân

Cố định đầu trái $l$ và kéo dài đầu phải $r$: min chỉ giảm, max chỉ tăng, GCD chỉ giảm hoặc giữ nguyên (mỗi lần đổi ít nhất chia đôi, nên đổi không quá $\log_2 V$ lần), AND chỉ mất bit, OR chỉ thêm bit.

Mọi điều kiện kiểu “max - min $\le k$”, “GCD $> 1$”, “AND $\ge k$” vì thế đúng trên một khúc đầu các giá trị $r$ rồi sai mãi về sau. Với mỗi $l$, tìm kiếm nhị phân (bài 05) vị trí $r$ xa nhất còn thỏa, mỗi bước kiểm bằng một câu hỏi $O(1)$ trên bảng: tổng $O(n \log n)$.

Hai con trỏ (bài 06) cũng làm được khi đầu trái và đầu phải cùng tiến, nhưng cần một cấu trúc gộp được khi bỏ phần tử ở đầu trái, như hàng đợi đơn điệu cho min/max; với GCD không có cách bỏ phần tử đơn giản, nên bảng thưa cộng tìm kiếm nhị phân là cách gọn nhất.

Ví dụĐoạn Ổn Định Dài Nhất

Đề. Dãy $n \le 10^5$ số và số $k$. Đoạn ổn định nếu max - min không vượt $k$. In độ dài lớn nhất $L$ của đoạn ổn định, số đoạn dài đúng $L$, rồi liệt kê chúng theo đầu trái tăng dần.

Lời giải. Với mỗi đầu trái $i$, max - min của $[i, r]$ không giảm khi $r$ tăng (max chỉ tăng, min chỉ giảm khi kéo dài), nên tìm kiếm nhị phân $r$ xa nhất còn ổn định, gọi là $R_i$. Đoạn ổn định dài nhất bắt đầu tại $i$ là $[i, R_i]$; độ dài lớn nhất toàn bài là max của $R_i - i + 1$, và mỗi đoạn dài đúng $L$ bắt đầu tại một $i$ có $R_i - i + 1 = L$, nên duyệt $i$ tăng dần là có đúng thứ tự cần in. Với ví dụ, ba đầu trái 1, 4, 7 cho đoạn dài 3.

Bước 1: kiểm một đoạn trong $O(1)$. Dựng hai bảng thưa, một min một max, cùng mảng lg; ok(l, r) đọc max và min của đoạn rồi so hiệu với $k$.

bool ok(ll l, ll r) {
    ll t = lg[r - l + 1], j = r - (1 << t) + 1;
    return max(mx[t][l], mx[t][j]) - min(mn[t][l], mn[t][j]) <= k;
}

Bước 2: chặt nhị phân cho mỗi đầu trái. Đoạn một phần tử luôn ổn định nên res bắt đầu bằng $i$.

for (ll i = 1; i <= n; i++) {
    ll l = i, r = n, res = i;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (ok(i, mid)) l = (res = mid) + 1;
        else r = mid - 1;
    }
    R[i] = res;
    best = max(best, res - i + 1);
}

Bước 3: đếm và in. Lượt thứ hai đi lại $i$ tăng dần, đếm rồi in các đoạn có độ dài bằng best.

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

const ll N = 1e5 + 5, LG = 17;
ll n, k, lg[N], mn[LG][N], mx[LG][N], R[N];

bool ok(ll l, ll r) {
    ll t = lg[r - l + 1], j = r - (1 << t) + 1;
    return max(mx[t][l], mx[t][j]) - min(mn[t][l], mn[t][j]) <= k;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    for (ll i = 1; i <= n; i++) {
        cin >> mn[0][i];
        mx[0][i] = mn[0][i];
    }
    for (ll i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    for (ll t = 1; t < LG; t++)
        for (ll i = 1; i + (1 << t) - 1 <= n; i++) {
            mn[t][i] = min(mn[t - 1][i], mn[t - 1][i + (1 << (t - 1))]);
            mx[t][i] = max(mx[t - 1][i], mx[t - 1][i + (1 << (t - 1))]);
        }
    ll best = 0, cnt = 0;
    for (ll i = 1; i <= n; i++) {
        ll l = i, r = n, res = i;
        while (l <= r) {
            ll mid = (l + r) >> 1;
            if (ok(i, mid)) l = (res = mid) + 1;
            else r = mid - 1;
        }
        R[i] = res;
        best = max(best, res - i + 1);
    }
    for (ll i = 1; i <= n; i++)
        if (R[i] - i + 1 == best) cnt++;
    cout << best << ' ' << cnt << '\n';
    for (ll i = 1; i <= n; i++)
        if (R[i] - i + 1 == best) cout << i << ' ' << R[i] << '\n';
}

ChạyInput9 2
4 6 5 9 8 7 1 2 3

Output3 3
1 3
4 6
7 9

Dựng $O(n \log n)$, mỗi đầu trái $O(\log n)$ lần kiểm $O(1)$: tổng $O(n \log n)$.

Ví dụĐoạn Cùng Phần Dư

Đề. Nhiều test, tổng $n \le 2 \cdot 10^5$, các số đôi một khác nhau và tới $10^{18}$. Tìm đoạn dài nhất mà có một $m \ge 2$ làm mọi phần tử trong đoạn cùng số dư khi chia cho $m$.

Lời giải. Mọi phần tử cùng dư theo $m$ khi và chỉ khi $m$ chia hết mọi hiệu kề nhau trong đoạn, tức chia hết GCD của các hiệu đó. Đặt $d_i = |a_{i+1} - a_i|$; đoạn $[i, j + 1]$ tốt khi $\gcd(d_i, \dots, d_j) > 1$. GCD không tăng khi kéo dài, nên với mỗi $i$ tìm kiếm nhị phân $j$ xa nhất. Các số khác nhau nên $d_i \ge 1$, và đoạn một phần tử luôn tốt. Với test đầu, hiệu là $7, 3, 6, 6, 13$, đoạn hiệu $3, 6, 6$ có GCD 3, cho đoạn dài 4.

Bước 1: bảng thưa GCD trên mảng hiệu. lg tính một lần cho mọi test; mỗi test dựng lại bảng trên mảng hiệu dài $m = n - 1$.

for (ll i = 1; i <= m; i++) st[0][i] = abs(a[i + 1] - a[i]);
for (ll k = 1; k < LG; k++)
    for (ll i = 1; i + (1 << k) - 1 <= m; i++)
        st[k][i] = __gcd(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);

Bước 2: chặt nhị phân cho mỗi $i$. res = i - 1 nghĩa là chưa có $j$ nào: đoạn tốt dài nhất bắt đầu ở $i$ chỉ có 1 phần tử. Đoạn hiệu $[i, j]$ ứng với đoạn số $[i, j + 1]$, dài $j - i + 2$.

for (ll i = 1; i <= m; i++) {
    ll l = i, r = m, res = i - 1;
    while (l <= r) {
        ll mid = (l + r) >> 1;
        if (get(i, mid) > 1) l = (res = mid) + 1;
        else r = mid - 1;
    }
    ans = max(ans, res - i + 2);
}

Với $n = 1$ không có hiệu nào, vòng lặp không chạy và ans giữ 1.

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

const ll N = 2e5 + 5, LG = 18;
ll n, a[N], lg[N], st[LG][N];

ll get(ll l, ll r) {
    ll k = lg[r - l + 1];
    return __gcd(st[k][l], st[k][r - (1 << k) + 1]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    for (ll i = 2; i < N; i++) lg[i] = lg[i / 2] + 1;
    ll T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (ll i = 1; i <= n; i++) cin >> a[i];
        ll m = n - 1, ans = 1;
        for (ll i = 1; i <= m; i++) st[0][i] = abs(a[i + 1] - a[i]);
        for (ll k = 1; k < LG; k++)
            for (ll i = 1; i + (1 << k) - 1 <= m; i++)
                st[k][i] = __gcd(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
        for (ll i = 1; i <= m; i++) {
            ll l = i, r = m, res = i - 1;
            while (l <= r) {
                ll mid = (l + r) >> 1;
                if (get(i, mid) > 1) l = (res = mid) + 1;
                else r = mid - 1;
            }
            ans = max(ans, res - i + 2);
        }
        cout << ans << '\n';
    }
}

ChạyInput3
6
1 8 5 11 17 4
1
10
5
6 10 14 9 21

Output4
1
3

Mỗi test $O(n \log n)$ cả dựng lẫn chặt nhị phân, cộng một thừa số $\log$ cho phép tính GCD.

Hai chiều

Ý tưởng mở rộng nguyên vẹn sang ma trận. Khi mọi câu hỏi là hình vuông, gọi mn[k][i][j] là min của hình vuông cạnh $2^k$ có góc trên trái $(i, j)$; nó là min của bốn hình vuông cạnh $2^{k-1}$ ở bốn góc. Hình vuông cạnh $b$ được phủ bởi bốn hình vuông cạnh $2^k$ với $k = \lfloor \log_2 b \rfloor$, đặt ở bốn góc của nó; chúng chồng nhau, nhưng min và max không bận tâm. Bộ nhớ $O(n^2 \log n)$, mỗi câu hỏi $O(1)$.

Hình chữ nhật tùy ý cần hai chỉ số mũ riêng cho hàng và cột, st[a][b][i][j] cho khối $2^a \times 2^b$, tốn $O(nm \log n \log m)$ bộ nhớ; chỉ dùng khi ma trận nhỏ, cỡ $500 \times 500$.

Ví dụĐộ Chênh Trên Ô Vuông

Đề. Ma trận $n \times n$ với $n \le 250$ và một cạnh $b$ cố định. Mỗi câu hỏi $(x, y)$ là hình vuông $b \times b$ có góc trên trái $(x, y)$; in max - min trong hình vuông đó. Có tới $10^5$ câu hỏi.

Lời giải. Bảng thưa hai chiều cho hình vuông: ô mn[k][i][j] là min của hình vuông cạnh $2^k$ góc trên trái $(i, j)$, và tương tự mx. Bốn hình vuông cạnh $2^k$ đặt ở bốn góc phủ trọn hình vuông cạnh $b$ khi $2^k \le b < 2^{k+1}$. Duyệt thẳng $b^2$ ô mỗi câu là $6 \cdot 10^9$ phép khi $b = n = 250$. Với câu hỏi $(2, 2)$ hình vuông gồm $3, 6, 9, 1$, độ chênh $8$.

Bước 1: dựng hai bảng. Hình vuông cạnh $2^k$ ghép từ bốn hình vuông cạnh $2^{k-1}$, góc trên trái lệch nhau $h = 2^{k-1}$ theo hàng và theo cột.

for (ll k = 1; k <= lg[n]; k++) {
    ll h = 1 << (k - 1);
    for (ll i = 1; i + 2 * h - 1 <= n; i++)
        for (ll j = 1; j + 2 * h - 1 <= n; j++) {
            mn[k][i][j] = min({mn[k - 1][i][j], mn[k - 1][i + h][j], mn[k - 1][i][j + h], mn[k - 1][i + h][j + h]});
            mx[k][i][j] = max({mx[k - 1][i][j], mx[k - 1][i + h][j], mx[k - 1][i][j + h], mx[k - 1][i + h][j + h]});
        }
}

Bước 2: trả lời. Mọi câu hỏi cùng cạnh $b$, nên $k = \lfloor \log_2 b \rfloor$ và độ dời s = b - 2^k tính một lần ngoài vòng. Bốn góc là $(x, y)$, $(x + s, y)$, $(x, y + s)$, $(x + s, y + s)$.

ll k = lg[b], s = b - (1 << k);
while (q--) {
    ll x, y;
    cin >> x >> y;
    ll lo = min({mn[k][x][y], mn[k][x + s][y], mn[k][x][y + s], mn[k][x + s][y + s]});
    ll hi = max({mx[k][x][y], mx[k][x + s][y], mx[k][x][y + s], mx[k][x + s][y + s]});
    cout << hi - lo << '\n';
}

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

const ll N = 255;
ll n, b, q, lg[N], mn[8][N][N], mx[8][N][N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> b >> q;
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= n; j++) {
            cin >> mn[0][i][j];
            mx[0][i][j] = mn[0][i][j];
        }
    for (ll i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    for (ll k = 1; k <= lg[n]; k++) {
        ll h = 1 << (k - 1);
        for (ll i = 1; i + 2 * h - 1 <= n; i++)
            for (ll j = 1; j + 2 * h - 1 <= n; j++) {
                mn[k][i][j] = min({mn[k - 1][i][j], mn[k - 1][i + h][j], mn[k - 1][i][j + h], mn[k - 1][i + h][j + h]});
                mx[k][i][j] = max({mx[k - 1][i][j], mx[k - 1][i + h][j], mx[k - 1][i][j + h], mx[k - 1][i + h][j + h]});
            }
    }
    ll k = lg[b], s = b - (1 << k);
    while (q--) {
        ll x, y;
        cin >> x >> y;
        ll lo = min({mn[k][x][y], mn[k][x + s][y], mn[k][x][y + s], mn[k][x + s][y + s]});
        ll hi = max({mx[k][x][y], mx[k][x + s][y], mx[k][x][y + s], mx[k][x + s][y + s]});
        cout << hi - lo << '\n';
    }
}

ChạyInput4 2 4
1 5 2 4
7 3 6 0
8 9 1 2
4 6 5 3
1 1
1 3
2 2
3 3

Output6
6
8
4

Mỗi bảng $8 \times 255^2$ ô, khoảng 4 MB; dựng $O(n^2 \log n)$, câu hỏi $O(1)$.