Binary Lifting

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

huunguyen · Last updated 7, Tháng 4, 2026, 21:17

Binary Lifting (hay còn gọi là Sparse Table trên cây) là kỹ thuật tiền xử lý cây để trả lời nhanh các truy vấn về tổ tiên.

Ý tưởng: Với mỗi đỉnh $u$ , lưu tổ tiên thứ $2^{k}$ của $u$ cho mọi $k = 0, 1, \dots, ⌊ \log_{2} N ⌋$ . Nhờ đó, bất kỳ bước nhảy $d$ nào đều có thể thực hiện bằng cách phân tích $d$ theo nhị phân và nhảy qua $O (\log N)$ bước.

Độ phức tạp: $O (N \log N)$ tiền xử lý, $O (\log N)$ mỗi truy vấn.

Tiền xử lý

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

vector<int> adj[MAXN];
int up[MAXN][LOG];     // up[u][k] = tổ tiên thứ 2^k của u
int dep[MAXN];

void dfs(int u, int p) {
    up[u][0] = p;
    for (int k = 1; k < LOG; k++)
        up[u][k] = up[up[u][k-1]][k-1];
    for (int v : adj[u])
        if (v != p) {
            dep[v] = dep[u] + 1;
            dfs(v, u);
        }
}

// Khởi tạo: up[root][0] = root (hoặc 0 nếu dùng node giả)
// dep[root] = 0; dfs(root, root);

Tổ tiên thứ k

Nhảy lên đúng $k$ bước từ $u$ :

int kth_ancestor(int u, int k) {
    for (int i = 0; i < LOG; i++)
        if ((k >> i) & 1)
            u = up[u][i];
    return u;
}

Tổ tiên chung thấp nhất (LCA)

LCA (u, v)

là tổ tiên chung **gần nhất** của

u

và

v

int lca(int u, int v) {
    // Đưa u và v về cùng độ sâu
    if (dep[u] < dep[v]) swap(u, v);
    u = kth_ancestor(u, dep[u] - dep[v]);
    if (u == v) return u;

    // Nhảy lên đồng thời đến ngay dưới LCA
    for (int k = LOG-1; k >= 0; k--)
        if (up[u][k] != up[v][k]) {
            u = up[u][k];
            v = up[v][k];
        }
    return up[u][0];
}

## Khoảng cách giữa hai đỉnh

dist (u, v) = dep [u] + dep [v] - 2 \cdot dep [LCA (u, v)]

int dist(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

Kiểm tra u có phải tổ tiên của v không

$u$ là tổ tiên của $v$ khi và chỉ khi $dep [u] \leq dep [v]$ và $LCA (u, v) = u$ .

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

Ứng dụng: Đỉnh trên đường đi

Tìm đỉnh thứ $k$ (tính từ $u$ ) trên đường đi $u \to v$ :

// Trả về đỉnh thứ k trên đường đi u → v (k tính từ 0)
int kth_on_path(int u, int v, int k) {
    int l = lca(u, v);
    int dist_u = dep[u] - dep[l];
    if (k <= dist_u)
        return kth_ancestor(u, k);
    else
        return kth_ancestor(v, dep[u] + dep[v] - 2*dep[l] - k);
}

Ứng dụng: Max/Min trên đường đi

Mở rộng binary lifting để lưu thêm giá trị tổng hợp (max, min, tổng) trên đoạn tổ tiên $2^{k}$ bước:

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

void dfs(int u, int p, int w) {  // w = trọng số cạnh u-p
    up[u][0] = p;
    mx[u][0] = w;
    for (int k = 1; k < LOG; k++) {
        up[u][k] = up[up[u][k-1]][k-1];
        mx[u][k] = max(mx[u][k-1], mx[up[u][k-1]][k-1]);
    }
    for (auto [v, wv] : adj[u])
        if (v != p) { dep[v] = dep[u] + 1; dfs(v, u, wv); }
}

// Max trọng số cạnh trên đường đi u → v
int max_on_path(int u, int v) {
    int res = 0;
    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, mx[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, mx[u][k], mx[v][k]});
            u = up[u][k]; v = up[v][k];
        }
    res = max({res, mx[u][0], mx[v][0]});
    return res;
}

Tổng kết

Truy vấn	Độ phức tạp
Tổ tiên thứ $k$	$O (\log N)$
LCA	$O (\log N)$
Khoảng cách	$O (\log N)$
Max/Min/Tổng trên đường đi	$O (\log N)$

Binary Lifting phù hợp khi cây cố định (không thay đổi). Nếu cây thay đổi động, dùng Link-Cut Tree.

Bình luận

Không có bình luận tại thời điểm này.