Wiki › Cấu trúc dữ liệu › Cây › Binary Lifting

Binary Lifting

huunguyen Updated Tháng sáu 2, 2026

Binary Lifting (nâng nhị phân, còn gọi là Sparse Table trên cây) là kỹ thuật tiền xử lý một cây cố định để trả lời cực nhanh các truy vấn về tổ tiên: tìm tổ tiên thứ $k$ của một đỉnh, tìm tổ tiên chung gần nhất (LCA — Lowest Common Ancestor) của hai đỉnh, tính khoảng cách giữa hai đỉnh, hay max/min trọng số trên đường đi.

Cách ngây thơ — leo từng cạnh một lên cây — mất $O (N)$ cho mỗi truy vấn (cây hình chuỗi cao tới $N$ ). Binary Lifting bỏ ra $O (N \log N)$ tiền xử lý để rồi mỗi truy vấn chỉ còn $O (\log N)$ . Với $N, Q \leq 2 \cdot 10^{5}$ , đây là khác biệt giữa $4 \cdot 10^{10}$ phép tính (quá hạn) và $\approx 3.6 \cdot 10^{6}$ (tức thì).

Ý tưởng / Trực giác

Vấn đề cốt lõi: ta muốn "nhảy lên $k$ tầng" trên cây thật nhanh. Quan sát then chốt là mọi số nguyên $k$ đều viết được dưới dạng tổng các luỹ thừa của 2 (biểu diễn nhị phân). Ví dụ $k = 13 = 8 + 4 + 1 = 2^{3} + 2^{2} + 2^{0}$ . Vậy nếu ta biết cách nhảy đúng $1, 2, 4, 8, \dots$ bước thì để nhảy 13 bước ta chỉ cần ghép 3 cú nhảy: $+ 8$ , rồi $+ 4$ , rồi $+ 1$ .

Số luỹ thừa của 2 không vượt $N$ chỉ là $⌈ \log_{2} N ⌉$ , nên mỗi cú "nhảy $k$ bước" cần nhiều nhất $O (\log N)$ cú nhảy con.

Để các cú nhảy con thực hiện trong $O (1)$ , ta dựng trước bảng:

$up [u] [k] = tổ tiên cách u đúng 2^{k} bước.$

Điểm đẹp là bảng này tự xây bằng quy hoạch động trên chính nó: nhảy $2^{k}$ bước = nhảy $2^{k - 1}$ bước rồi lại nhảy $2^{k - 1}$ bước:

$up [u] [k] = up [up [u] [k - 1]] [k - 1] .$

Nghĩa là: từ $u$ leo nửa quãng đường ( $2^{k - 1}$ ) tới một đỉnh trung gian, rồi từ đó leo tiếp nửa còn lại. Vì $2^{k - 1} + 2^{k - 1} = 2^{k}$ , kết quả đúng bằng tổ tiên cách $2^{k}$ bước.

Vì sao LCA cũng dùng được kỹ thuật này? Ý tưởng LCA hai bước:

Đưa hai đỉnh về cùng độ sâu bằng cách cho đỉnh sâu hơn nhảy lên (đúng bài toán tổ tiên thứ $k$ ).
Khi đã cùng độ sâu mà chưa trùng nhau, ta cho cả hai cùng nhảy lên từng cú $2^{k}$ giảm dần. Mẹo: chỉ nhảy khi $up [u] [k] \neq up [v] [k]$ (hai đỉnh vẫn ở hai nhánh khác nhau). Cứ "nhảy cao nhất mà chưa gặp nhau", cuối cùng cả hai dừng ngay dưới LCA đúng một bước, và $up [u] [0]$ chính là LCA. Đây thực chất là tìm kiếm nhị phân trên độ cao: ta dò ranh giới giữa "chưa tới tổ tiên chung" và "đã vượt qua tổ tiên chung".

Ví dụ chạy tay

Xét cây gốc tại $1$ :

            1            dep
           / \            0
          2   3           1
         /   / \          2
        4   5   6
                 \        3
                  7

Quan hệ cha: cha(2)=cha(3)=1; cha(4)=2; cha(5)=cha(6)=3; cha(7)=6.

Bảng up[u][k] sau tiền xử lý (quy ước tổ tiên của gốc là chính nó, đánh số bắt đầu từ 0). Cột $k = 0$ chính là cha; cột $k = 1$ là "ông" (nhảy 2 bước); $k = 2$ nhảy 4 bước:

$u$	$k = 0$ (cha)	$k = 1$ (2 bước)	$k = 2$ (4 bước)
1	1	1	1
2	1	1	1
3	1	1	1
4	2	1	1
5	3	1	1
6	3	1	1
7	6	3	1

Cách điền ô $up [7] [1]$ : $up [7] [1] = up [up [7] [0]] [0] = up [6] [0] = 3$ . Đúng: từ 7 nhảy 2 bước là $7 \to 6 \to 3$ .

Truy vấn kth_ancestor(7, 3) — tổ tiên cách đỉnh 7 đúng 3 bước. Phân tích $3 = (011)_{2} = 2^{1} + 2^{0}$ :

k=0 bit=1 -> u = up[7][0] = 6      (đã đi 1 bước:  7 -> 6)
k=1 bit=1 -> u = up[6][1] = 1      (đi thêm 2 bước: 6 -> 3 -> 1)
k>=2 bit=0 -> bỏ qua
kết quả = 1

Kiểm tra: $7 \to 6 \to 3 \to 1$ , đúng 3 cạnh. ✓

Truy vấn lca(4, 7): $dep [4] = 2$ , $dep [7] = 3$ .

Bước 1 — cân độ sâu: 7 sâu hơn, nhảy lên $3 - 2 = 1$ bước: $7 \to 6$ . Giờ xét cặp $(4, 6)$ , cùng $dep = 2$ .

Bước 2 — nhảy đồng thời từ $k$ lớn xuống nhỏ:

k=2: up[4][2]=1, up[6][2]=1  -> bằng nhau   -> KHÔNG nhảy
k=1: up[4][1]=1, up[6][1]=1  -> bằng nhau   -> KHÔNG nhảy
k=0: up[4][0]=2, up[6][0]=3  -> khác nhau   -> NHẢY: u=2, v=3

Dừng. LCA $= up [2] [0] = up [3] [0] = 1$ . ✓ (đường $4 – 2 – 1 – 3 – 6 – 7$ giao tại đỉnh 1).

Cài đặt

Quy ước: đỉnh đánh số từ 1, gốc root. Đặt tổ tiên của gốc là chính nó (up[root][k] = root) để mọi cú nhảy vượt gốc đều "dừng lại" ở gốc — tránh truy cập chỉ số ngoài mảng.

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

const int MAXN = 2e5 + 5;
const int LOG  = 18;          // 2^18 = 262144 > 2*10^5

vector<int> adj[MAXN];
int up[MAXN][LOG];            // up[u][k] = tổ tiên cách u đúng 2^k bước
int dep[MAXN];

// DFS lặp/đệ quy điền up và dep. p là cha của u.
void dfs(int u, int p) {
    up[u][0] = p;                                  // nhảy 1 bước = cha
    for (int k = 1; k < LOG; k++)
        up[u][k] = up[ up[u][k-1] ][k-1];          // DP: nửa + nửa
    for (int v : adj[u])
        if (v != p) {                              // không quay lại cha
            dep[v] = dep[u] + 1;
            dfs(v, u);
        }
}

// Tổ tiên cách u đúng k bước: tách k theo nhị phân, nhảy từng bit bật
int kth_ancestor(int u, int k) {
    for (int i = 0; i < LOG; i++)
        if ((k >> i) & 1)                          // bit thứ i bật?
            u = up[u][i];
    return u;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);               // u là đỉnh sâu hơn
    u = kth_ancestor(u, dep[u] - dep[v]);          // cân độ sâu
    if (u == v) return u;                          // v đã là tổ tiên của u
    for (int k = LOG - 1; k >= 0; k--)             // nhảy cao -> thấp
        if (up[u][k] != up[v][k]) {                // còn ở hai nhánh -> nhảy
            u = up[u][k];
            v = up[v][k];
        }
    return up[u][0];                               // cha chung = LCA
}

int dist(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];   // số cạnh trên đường đi
}

Khởi tạo và gọi:

// Sau khi đọc cây vào adj:
dep[root] = 0;
up[root][0] = root;   // tổ tiên của gốc là chính nó (chốt chặn)
dfs(root, root);

Lưu ý đệ quy: với $N$ tới $2 \cdot 10^{5}$ và cây hình chuỗi, dfs đệ quy có thể tràn ngăn xếp (stack overflow). Khi cần, hãy viết DFS khử đệ quy bằng stack, hoặc xử lý đỉnh theo thứ tự BFS rồi điền up (vì cha luôn được xử lý trước con).

Kiểm tra u có là tổ tiên của v và đỉnh thứ $k$ trên đường đi $u \to v$ :

bool is_ancestor(int u, int v) {
    return dep[u] <= dep[v] && lca(u, v) == u;
}

// Đỉnh thứ k (tính từ 0, bắt đầu tại u) trên đường đi u -> v
int kth_on_path(int u, int v, int k) {
    int l = lca(u, v);
    int up_len = dep[u] - dep[l];                  // số cạnh nhánh u -> l
    if (k <= up_len) return kth_ancestor(u, k);    // còn trên nhánh u
    int down = (dep[u] + dep[v] - 2*dep[l]) - k;   // đếm ngược từ v
    return kth_ancestor(v, down);
}

Biến thể max trọng số cạnh trên đường đi — gắn thêm bảng mx song song với up:

int mxw[MAXN][LOG];   // mxw[u][k] = max trọng số cạnh trong 2^k bước đi lên từ u

void dfs2(int u, int p, int w) {  // w = trọng số cạnh (u, p)
    up[u][0] = p;
    mxw[u][0] = w;
    for (int k = 1; k < LOG; k++) {
        up[u][k]  = up[ up[u][k-1] ][k-1];
        mxw[u][k] = max(mxw[u][k-1], mxw[ up[u][k-1] ][k-1]);  // gộp 2 nửa
    }
    for (auto [v, wv] : adj[u])   // adj lưu cặp (đỉnh, trọng số)
        if (v != p) { dep[v] = dep[u] + 1; dfs2(v, u, wv); }
}

int max_on_path(int u, int v) {
    int res = INT_MIN;
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = 0; k < LOG; k++)
        if ((diff >> k) & 1) { res = max(res, mxw[u][k]); u = up[u][k]; }
    if (u == v) return res;
    for (int k = LOG - 1; k >= 0; k--)
        if (up[u][k] != up[v][k]) {
            res = max({res, mxw[u][k], mxw[v][k]});
            u = up[u][k]; v = up[v][k];
        }
    return max({res, mxw[u][0], mxw[v][0]});  // cộng nốt 2 cạnh tới LCA
}

Độ phức tạp

Tiền xử lý — thời gian $O (N \log N)$ : với mỗi trong $N$ đỉnh ta điền $\log N$ ô của bảng up, mỗi ô tính trong $O (1)$ nhờ công thức DP "nửa + nửa".
Mỗi truy vấn — $O (\log N)$ : kth_ancestor duyệt $\log N$ bit; lca gọi kth_ancestor một lần rồi quét $\log N$ mức một lần nữa, vẫn $O (\log N)$ .
Bộ nhớ — $O (N \log N)$ : bảng up có $N \times \log N$ phần tử. Với $N = 2 \cdot 10^{5}$ , $\log N = 18$ thì cỡ $3.6 \cdot 10^{6}$ số int $\approx 14$ MB — vừa thoải mái. Mỗi bảng phụ (như mxw) tốn thêm chừng đó. Nếu lưu nhiều bảng phụ kiểu long long, hãy canh giới hạn bộ nhớ.

So với cách leo từng cạnh ( $O (N)$ /truy vấn), tổng chi phí $Q$ truy vấn giảm từ $O (N Q)$ xuống $O ((N + Q) \log N)$ .

⚠️ Lỗi thường gặp

LOG quá nhỏ. Cần $2^{LOG} > N$ , tức $LOG \geq ⌈ \log_{2} N ⌉$ . Nếu $N = 2 \cdot 10^{5}$ mà đặt LOG = 17 ( $2^{17} = 131072 < 2 \cdot 10^{5}$ ) thì kth_ancestor với $k$ lớn sẽ nhảy thiếu, LCA sai âm thầm. Quy tắc an toàn: LOG = 18 cho $N \leq 2.6 \cdot 10^{5}$ , LOG = 20 cho $N \leq 10^{6}$ .
Quên chốt chặn ở gốc. Nếu để up[root][0] là 0/giá trị rác thay vì root, khi nhảy vượt qua gốc bạn truy cập up[0][...] (đỉnh không tồn tại) hoặc nhảy vào vùng nhớ rác → kết quả LCA sai hoặc lỗi truy cập bộ nhớ. Luôn đặt up[root][0] = root.
Tràn số khi tính khoảng cách/tổng có trọng số. dist đếm cạnh thì int đủ, nhưng nếu cộng độ dài cạnh (trọng số tới $10^{12}$ , tổng tới $10^{18}$ như bài runaway) phải dùng long long. Cộng int sẽ tràn và ra số âm. Tách rõ "số cạnh" (int) và "tổng độ dài" (long long).
Vòng lặp LCA sai chiều. Bước nhảy đồng thời phải đi từ k = LOG-1 xuống 0 (cú nhảy lớn trước). Nếu lặp từ nhỏ lên lớn, bạn có thể nhảy vọt qua LCA rồi không sửa lại được → kết quả sai. Lý do: ta đang tìm "đỉnh cao nhất mà hai bên vẫn khác nhau", phải thử bước lớn trước.
Đỉnh này là tổ tiên của đỉnh kia. Sau khi cân độ sâu, nếu u == v phải trả về ngay. Bỏ qua kiểm tra này thì vòng nhảy đồng thời sẽ chạy với hai đỉnh đã trùng và cho ra cha của LCA (sai một mức).
Quên cân độ sâu trước. Vòng "nhảy khi up[u][k] != up[v][k]" chỉ đúng khi $u, v$ cùng độ sâu. Gọi nó khi lệch độ sâu sẽ cho kết quả vô nghĩa.
Tràn ngăn xếp do DFS đệ quy. Cây hình chuỗi sâu $2 \cdot 10^{5}$ làm đệ quy đổ. Dùng DFS lặp hoặc thứ tự BFS khi $N$ lớn.

Biến thể / Mở rộng

LCA bằng Euler Tour + Sparse Table: truy vấn $O (1)$ sau $O (N \log N)$ tiền xử lý, nhưng cài đặt phức tạp hơn. Binary Lifting thắng ở chỗ dễ mở rộng sang "tổ tiên thứ $k$ " và "gộp giá trị trên đường đi".
Nhảy theo điều kiện (tìm kiếm nhị phân trên cây): thay vì nhảy đúng $k$ bước, ta nhảy xa nhất mà còn thoả một tính chất đơn điệu — ví dụ bài runaway: nhảy lên/xuống xa nhất sao cho tổng độ dài $\leq L$ . Mẫu: quét $k$ từ lớn xuống, nếu cú nhảy $2^{k}$ không vi phạm thì thực hiện.
Gộp toán tử bất kỳ: bảng phụ có thể lưu max, min, tổng, hoặc tích ma trận — miễn phép gộp có tính kết hợp.
Cây thay đổi động (thêm/xoá cạnh) thì Binary Lifting không còn hợp; cân nhắc Link-Cut Tree hoặc Heavy-Light Decomposition.

Bài tập luyện

Tổ tiên chung thấp nhất (LCA) (compqry2) — (Advanced) Bài LCA thuần tuý: dựng up rồi trả lời truy vấn LCA — đúng "hello world" của Binary Lifting.
Truy vấn khoảng cách (distqry) — (Advanced) Tính khoảng cách hai đỉnh qua công thức $dep [u] + dep [v] - 2 dep [LCA]$ , luyện kết hợp LCA với độ sâu.
Vận Chuyển Phép Thuật (trucktsp) — (Advanced) Maximin trên đường đi: dựng cây khung lớn nhất (Kruskal) rồi Binary Lifting lưu min trọng số cạnh trên đường đi — biến thể "gộp giá trị".
Cú Bay Đêm (running) — (Veteran) Mỗi con cú đi theo đường đi trên cây; cần LCA để tách đường thành hai nhánh lên/xuống, kết hợp difference-on-tree để đếm.
Chạy trốn khỏi chuồng (runaway) — (Veteran) Dùng Binary Lifting để nhảy xa nhất theo điều kiện (tổng quãng đường $\leq L$ ) — minh hoạ kỹ thuật tìm kiếm nhị phân trên cây với độ dài tới $10^{18}$ (cẩn thận tràn số).