Binary Lifting

Bảng nhảy

Gọi up[0][v] là bước kế tiếp của $v$, ví dụ cha trên cây. Đi $2^j$ bước là đi $2^{j-1}$ bước hai lần:

Dựng lần lượt theo $j$ tăng dần. Đi $k$ bước: viết $k$ theo cơ số 2, với mỗi bit $j$ bật thì nhảy $v \gets up[j][v]$. Thứ tự các bit không quan trọng vì mọi bước đều theo cùng một hàm.

Khi bước có thể “ra ngoài” (vượt quá gốc), dùng đỉnh lính canh 0 với up[j][0] = 0: mọi bước nhảy từ 0 vẫn ở 0, và câu trả lời 0 nghĩa là không tồn tại.

Với $n$ đỉnh và $k \le n$ cần $\lceil \log_2 n \rceil$ tầng, 18 tầng cho $2 \cdot 10^5$. Bảng $18 \times 2 \cdot 10^5$ số ll khoảng 29 MB.

Bảng này lớn, nên cách khai báo ảnh hưởng thời gian:

Ở đây up[j][v] kiểu int nhanh nhất: bảng được dựng từng tầng cho mọi đỉnh, nên mỗi tầng nằm liền nhau. up[v][j] chậm hơn khoảng 1,7 lần, bản long long chậm hơn khoảng 1,5 lần. Chỉ số đỉnh đủ nhỏ thì dùng int.

Ví dụTổ Tiên Cách K Bậc

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh gốc 1, cha $p_i < i$. Mỗi câu hỏi $(x, k)$: in tổ tiên cách $x$ đúng $k$ cạnh, hoặc $-1$.

Lời giải. up[j][v] là tổ tiên cách $v$ đúng $2^j$ bậc. Nhảy quá gốc thì về 0 (lính canh), và up[j][0] = 0 nên ở lại 0. Câu hỏi viết $k$ dưới dạng nhị phân: bit $j$ bật thì nhảy $2^j$ bậc; thứ tự các bước không quan trọng vì tổng số bậc vẫn là $k$.

Bước 1: dựng bảng. up[0][v] = p_v, gốc có up[0][1] = 0. Tầng $j$ chỉ đọc tầng $j - 1$ đã xong: tổ tiên $2^j$ bậc là tổ tiên $2^{j-1}$ bậc của tổ tiên $2^{j-1}$ bậc.

for (ll v = 2; v <= n; v++) cin >> up[0][v];
for (ll j = 1; j < LG; j++)
    for (ll v = 1; v <= n; v++) up[j][v] = up[j - 1][up[j - 1][v]];

Bước 2: trả lời. Điều kiện && x dừng sớm khi đã ra 0; ra 0 thì in $-1$.

for (ll j = 0; j < LG && x; j++)
    if (k >> j & 1) x = up[j][x];
cout << (x ? x : -1) << '\n';

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

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

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

    cin >> n >> q;
    for (ll v = 2; v <= n; v++) cin >> up[0][v];
    for (ll j = 1; j < LG; j++)
        for (ll v = 1; v <= n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
    while (q--) {
        ll x, k;
        cin >> x >> k;
        for (ll j = 0; j < LG && x; j++)
            if (k >> j & 1) x = up[j][x];
        cout << (x ? x : -1) << '\n';
    }
}

ChạyInput7 4
1 1 2 2 4 4
7 1
7 2
7 3
7 4

Output4
2
1
-1

Dựng $O(n \log n)$, mỗi câu hỏi $O(\log n)$.

Đồ thị hàm

Trong đồ thị hàm, mỗi đỉnh có đúng một cạnh ra $t_v$. Đi mãi thì rơi vào một chu trình, nên không có lính canh nào cần thiết, và $k$ có thể lớn tùy ý: cần $\lceil \log_2 K \rceil$ tầng, 30 tầng cho $K \le 10^9$, 60 tầng cho $10^{18}$. Cách khác là tìm chu trình rồi lấy $k$ modulo độ dài chu trình, nhưng nhảy nhị phân không cần phân tích cấu trúc và trả lời được mọi điểm xuất phát như nhau.

Ví dụCổng Dịch Chuyển

Đề. $n \le 2 \cdot 10^5$ trạng thái, trạng thái $i$ đi sang $t_i$. $q \le 2 \cdot 10^5$ câu hỏi $(x, k)$ với $k \le 10^9$: in trạng thái sau đúng $k$ bước.

Lời giải. Như ví dụ trước nhưng trên đồ thị hàm: mỗi trạng thái luôn có đúng một bước kế, nên không cần lính canh, và up[0][v] là chính $t_v$. Cần 30 tầng vì $k \le 10^9 < 2^{30}$.

Bước 1: dựng bảng 30 tầng. Tầng $j$ phụ thuộc toàn bộ tầng $j - 1$, nên vòng $j$ ở ngoài, vòng $v$ ở trong.

for (ll v = 1; v <= n; v++) cin >> up[0][v];
for (ll j = 1; j < LG; j++)
    for (ll v = 1; v <= n; v++) up[j][v] = up[j - 1][up[j - 1][v]];

Bước 2: trả lời. Duyệt 30 bit của $k$, mỗi bit bật là một lần tra bảng.

for (ll j = 0; j < LG; j++)
    if (k >> j & 1) x = up[j][x];

Bảng $30 \times 2 \cdot 10^5$ số long long khoảng 48 MB; dùng int nếu bộ nhớ chật.

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

const ll N = 2e5 + 5, LG = 30;
ll n, q, up[LG][N];

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

    cin >> n >> q;
    for (ll v = 1; v <= n; v++) cin >> up[0][v];
    for (ll j = 1; j < LG; j++)
        for (ll v = 1; v <= n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
    while (q--) {
        ll x, k;
        cin >> x >> k;
        for (ll j = 0; j < LG; j++)
            if (k >> j & 1) x = up[j][x];
        cout << x << '\n';
    }
}

ChạyInput6 5
2 3 1 5 6 4
1 0
1 4
4 3
6 5
2 10

Output1
2
4
5
3

Dựng $O(30n)$, mỗi câu hỏi 30 bước.

Gộp thông tin

Kèm theo mỗi bước nhảy một giá trị gộp của đoạn đường nó đi qua: sm[j][v] là tổng trọng số trên $2^j$ cạnh từ $v$, mn[j][v] là cạnh nhỏ nhất. Hai nửa ghép lại bằng phép gộp kết hợp: $sm[j][v] = sm[j-1][v] + sm[j-1][up[j-1][v]]$, tương tự với min. Đi $k$ bước thì gộp các giá trị của những bước nhảy đã dùng.

Khi mọi điểm xuất phát dùng cùng một $k$, không cần giữ cả bảng. Duyệt các bit của $k$ từ thấp lên, giữ cho mỗi điểm xuất phát vị trí hiện tại và giá trị đã gộp. Ở bit $j$, nếu bit bật thì cho mọi điểm nhảy theo tầng hiện tại; rồi nhân đôi tầng hiện tại tại chỗ thành tầng $j + 1$. Bộ nhớ $O(n)$ thay cho $O(n \log K)$.

Ví dụThống Kê Trên Đường Chuyển

Đề. Đồ thị hàm $N \le 10^5$ đỉnh, cạnh $i \to f_i$ có trọng số $w_i$. Với mỗi đỉnh, in tổng và min trọng số trên đúng $K \le 10^{10}$ cạnh đầu tiên.

Lời giải. Bảng nhảy kèm tổng và min, nhưng không giữ cả bảng $34$ tầng: mọi điểm xuất phát cùng đi đúng $K$ bước, nên xử lý từng bit của $K$ một lần cho cả $n$ điểm, chỉ cần tầng hiện tại. Bộ nhớ $O(n)$ thay cho bảng $n \times 34$.

Bước 1: tầng hiện tại và trạng thái. nx, cs, cm là chỗ tới, tổng và min sau $2^j$ bước từ mỗi đỉnh; ban đầu là một bước. pos, s, m là trạng thái của từng điểm xuất phát: đang ở đâu, tổng và min đã gom.

for (ll i = 0; i < n; i++) cin >> nx[i];
for (ll i = 0; i < n; i++) {
    cin >> cs[i];
    cm[i] = cs[i];
    pos[i] = i;
    m[i] = INF;
}

Bước 2: bit bật thì mọi điểm cùng nhảy.

if (k & 1)
    for (ll i = 0; i < n; i++) {
        s[i] += cs[pos[i]];
        m[i] = min(m[i], cm[pos[i]]);
        pos[i] = nx[pos[i]];
    }

Bước 3: nhân đôi tầng. $2^{j+1}$ bước từ $i$ là $2^j$ bước từ $i$ rồi $2^j$ bước từ nx[i]. Viết ra mảng tạm rồi mới chép lại, để không đọc phải giá trị vừa sửa trong cùng vòng.

for (ll i = 0; i < n; i++) {
    nn[i] = nx[nx[i]];
    ns[i] = cs[i] + cs[nx[i]];
    nm[i] = min(cm[i], cm[nx[i]]);
}
for (ll i = 0; i < n; i++) nx[i] = nn[i], cs[i] = ns[i], cm[i] = nm[i];

Tổng tới $10^{18}$, vẫn vừa ll.

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

const ll N = 1e5 + 5, INF = 1e18;
ll n, k, nx[N], cs[N], cm[N], pos[N], s[N], m[N], nn[N], ns[N], nm[N];

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

    cin >> n >> k;
    for (ll i = 0; i < n; i++) cin >> nx[i];
    for (ll i = 0; i < n; i++) {
        cin >> cs[i];
        cm[i] = cs[i];
        pos[i] = i;
        m[i] = INF;
    }
    for (; k; k >>= 1) {
        if (k & 1)
            for (ll i = 0; i < n; i++) {
                s[i] += cs[pos[i]];
                m[i] = min(m[i], cm[pos[i]]);
                pos[i] = nx[pos[i]];
            }
        for (ll i = 0; i < n; i++) {
            nn[i] = nx[nx[i]];
            ns[i] = cs[i] + cs[nx[i]];
            nm[i] = min(cm[i], cm[nx[i]]);
        }
        for (ll i = 0; i < n; i++) nx[i] = nn[i], cs[i] = ns[i], cm[i] = nm[i];
    }
    for (ll i = 0; i < n; i++) cout << s[i] << ' ' << m[i] << '\n';
}

ChạyInput5 4
1 2 0 2 4
5 1 7 3 9

Output18 1
14 1
20 1
16 1
36 9

$O(n \log K)$.

Nhảy xa nhất

Thay vì biết trước $k$, nhiều bài hỏi “đi được xa nhất bao nhiêu khi một điều kiện còn đúng”, với điều kiện đơn điệu dọc đường: tổng chi phí không vượt ngân sách, vị trí chưa vượt đích.

Duyệt tầng từ cao xuống thấp: thử bước nhảy $2^j$, nếu sau bước đó điều kiện vẫn đúng thì nhảy, không thì bỏ qua tầng này. Giống tìm kiếm nhị phân trên số bước: các bit của số bước tốt nhất được dựng từ cao xuống. Đếm số bước ít nhất để vượt một mốc làm ngược lại: nhảy khi chưa tới mốc, rồi cộng thêm một bước cuối.

Ví dụNăng Lượng Về Phòng Gốc

Đề. Cây $N \le 10^5$ phòng gốc 1, đường hầm có độ dài. Con kiến ở phòng $v$ có năng lượng $E_v$, đi về phía gốc, mỗi hầm tốn đúng độ dài của nó. In phòng gần gốc nhất mỗi con kiến tới được.

Lời giải. Bảng nhảy kèm chi phí: up[j][v] là tổ tiên cách $2^j$ bậc, cost[j][v] là tổng độ dài để tới đó. Độ dài dương nên năng lượng cần tăng dần theo số bậc đi lên: “đi $k$ bậc vẫn đủ năng lượng” là điều kiện đơn điệu theo $k$. Vì vậy dựng số bậc lớn nhất bằng cách thử bit từ cao xuống, như chặt nhị phân.

Bước 1: BFS lấy cha và độ dài cạnh lên cha. Gốc có cha 0.

vector<ll> ord = {1};
for (ll i = 0; i < (ll)ord.size(); i++) {
    ll u = ord[i];
    for (pair<ll, ll> x : g[u])
        if (x.first != up[0][u]) {
            up[0][x.first] = u;
            cost[0][x.first] = x.second;
            ord.push_back(x.first);
        }
}

Bước 2: dựng bảng kèm chi phí. cost[j][v] ghép hai nửa liền nhau, giống up.

for (ll j = 1; j < LG; j++)
    for (ll v = 1; v <= n; v++) {
        ll mid = up[j - 1][v];
        up[j][v] = up[j - 1][mid];
        cost[j][v] = cost[j - 1][v] + cost[j - 1][mid];
    }

Bước 3: mỗi con kiến. Thử từ bước lớn xuống nhỏ, nhảy khi tổ tiên tồn tại và còn đủ năng lượng.

ll x = v, rem = e[v];
for (ll j = LG - 1; j >= 0; j--)
    if (up[j][x] && cost[j][x] <= rem) {
        rem -= cost[j][x];
        x = up[j][x];
    }

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

const ll N = 1e5 + 5, LG = 17;
ll n, e[N], up[LG][N], cost[LG][N];
vector<pair<ll, ll>> g[N];

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

    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> e[i];
    for (ll i = 1; i < n; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    vector<ll> ord = {1};
    for (ll i = 0; i < (ll)ord.size(); i++) {
        ll u = ord[i];
        for (pair<ll, ll> x : g[u])
            if (x.first != up[0][u]) {
                up[0][x.first] = u;
                cost[0][x.first] = x.second;
                ord.push_back(x.first);
            }
    }
    for (ll j = 1; j < LG; j++)
        for (ll v = 1; v <= n; v++) {
            ll mid = up[j - 1][v];
            up[j][v] = up[j - 1][mid];
            cost[j][v] = cost[j - 1][v] + cost[j - 1][mid];
        }
    for (ll v = 1; v <= n; v++) {
        ll x = v, rem = e[v];
        for (ll j = LG - 1; j >= 0; j--)
            if (up[j][x] && cost[j][x] <= rem) {
                rem -= cost[j][x];
                x = up[j][x];
            }
        cout << x << '\n';
    }
}

+12 dòngChạyInput6
1
4
12
7
20
3
1 2 5
1 3 4
2 4 6
2 5 3
3 6 8

Output1
2
1
2
1
6

Dựng $O(N \log N)$, mỗi con kiến $O(\log N)$.

Bước tham lam

Bài chọn nhiều khoảng không chồng nhau trong một khung $[a, b]$ có lời giải tham lam quen thuộc: luôn chọn khoảng kết thúc sớm nhất trong số các khoảng bắt đầu sau điểm hiện tại. Bước tham lam đó là một hàm: từ khoảng vừa chọn, khoảng chọn tiếp theo đã xác định. Vậy có thể nhảy nhị phân trên các khoảng: tầng $j$ là khoảng chọn sau $2^j$ bước; mỗi câu hỏi đếm số bước nhảy khi khoảng còn kết thúc trong khung.

Ví dụLịch Phim Trong Khung Giờ

Đề. $N \le 2 \cdot 10^5$ bộ phim $[s, e]$, $Q \le 2 \cdot 10^5$ câu hỏi $[a, b]$: số phim nhiều nhất xem trọn trong khung, phim sau bắt đầu không sớm hơn lúc phim trước kết thúc.

Lời giải. Trong một khung giờ, cách tham lam của bài 04 (luôn chọn phim kết thúc sớm nhất trong các phim còn xem được) cho số phim nhiều nhất. “Phim chọn tiếp sau phim $i$” là một hàm, nên dựng bảng nhảy trên nó và đếm số bước nhảy còn kết thúc không quá $b$.

Bước 1: phim kết thúc sớm nhất từ một vị trí. Sắp phim theo giờ bắt đầu; sm[i] là phim kết thúc sớm nhất trong các phim từ vị trí $i$ trở đi (hậu tố min). Phim 0 là lính canh kết thúc ở $+\infty$, và sm[n + 1] = 0.

e[0] = INF;
sm[n + 1] = 0;
for (ll i = n; i >= 1; i--) sm[i] = (e[i] < e[sm[i + 1]] ? i : sm[i + 1]);

Bước 2: lựa chọn kế tiếp. first(t) là phim kết thúc sớm nhất trong các phim bắt đầu không sớm hơn $t$, tức lựa chọn tham lam khi đang rảnh từ thời điểm $t$. Phim chọn sau phim $i$ là first(e[i]).

ll first(ll t) {
    return sm[lower_bound(s + 1, s + n + 1, t) - s];
}

for (ll i = 1; i <= n; i++) up[0][i] = first(e[i]);
for (ll j = 1; j < LG; j++)
    for (ll i = 0; i <= n; i++) up[j][i] = up[j - 1][up[j - 1][i]];

Tầng của phim 0 luôn là 0, nên lính canh tự chặn mọi bước nhảy quá cuối.

Bước 3: trả lời. Phim đầu tiên là first(a); kết thúc sau $b$ thì không xem được phim nào. Ngược lại đếm 1 rồi nhảy từ cao xuống khi phim đích còn kết thúc không quá $b$.

ll cur = first(a);
if (e[cur] > b) {
    cout << 0 << '\n';
    continue;
}
ll ans = 1;
for (ll j = LG - 1; j >= 0; j--)
    if (e[up[j][cur]] <= b) {
        cur = up[j][cur];
        ans += 1LL << j;
    }

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

const ll N = 2e5 + 5, LG = 18, INF = 1e18;
ll n, q, s[N], e[N], sm[N], up[LG][N];
pair<ll, ll> mv[N];

ll first(ll t) {
    return sm[lower_bound(s + 1, s + n + 1, t) - s];
}

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

    cin >> n >> q;
    for (ll i = 1; i <= n; i++) cin >> mv[i].first >> mv[i].second;
    sort(mv + 1, mv + n + 1);
    for (ll i = 1; i <= n; i++) s[i] = mv[i].first, e[i] = mv[i].second;
    e[0] = INF;
    sm[n + 1] = 0;
    for (ll i = n; i >= 1; i--) sm[i] = (e[i] < e[sm[i + 1]] ? i : sm[i + 1]);
    for (ll i = 1; i <= n; i++) up[0][i] = first(e[i]);
    for (ll j = 1; j < LG; j++)
        for (ll i = 0; i <= n; i++) up[j][i] = up[j - 1][up[j - 1][i]];
    while (q--) {
        ll a, b;
        cin >> a >> b;
        ll cur = first(a);
        if (e[cur] > b) {
            cout << 0 << '\n';
            continue;
        }
        ll ans = 1;
        for (ll j = LG - 1; j >= 0; j--)
            if (e[up[j][cur]] <= b) {
                cur = up[j][cur];
                ans += 1LL << j;
            }
        cout << ans << '\n';
    }
}

+14 dòngChạyInput7 6
1 4
4 6
2 5
6 9
5 8
9 11
10 12
1 11
2 9
4 12
5 8
3 5
10 12

Output4
2
3
1
0
1

Dựng $O(N \log N)$, mỗi câu hỏi $O(\log N)$.