LCA với Binary Lifting — Tổ tiên chung gần nhất

git merge-base branch-a branch-b — lệnh này tìm commit chung gần nhất giữa hai branch. Với repository hàng triệu commit, Git không thể duyệt từng commit một. Nó cần trả lời trong O(log N), và kỹ thuật đằng sau chính là Binary Lifting — nhảy theo lũy thừa 2 trên cây.

Lowest Common Ancestor (LCA) là bài toán nền tảng trên cây: cho hai node u và v, tìm tổ tiên chung sâu nhất. Ứng dụng rộng: tính khoảng cách giữa hai node, truy vấn đường đi trên cây, file system common ancestor, DOM tree traversal. Binary Lifting biến mỗi query từ O(N) naive thành O(log N), với preprocessing O(N log N).

Bức tranh tư duy

Hình dung cây gia phả. Muốn tìm ông bà chung gần nhất của hai người, cách naive là cả hai cùng leo lên từng bậc — gặp nhau ở đâu thì đó là tổ tiên chung. Với gia phả 20 thế hệ, mất 20 bước. Với cây 1 triệu node, mất 1 triệu bước.

Binary Lifting: Thay vì leo từng bậc, bạn nhảy cóc theo lũy thừa 2. Cần leo 13 bậc? 13 = 8 + 4 + 1 → nhảy 3 lần thay vì 13 bước. Mọi số nguyên đều biểu diễn được bằng tổng lũy thừa 2 (biểu diễn nhị phân) — nên bất kỳ khoảng cách nào cũng chỉ cần O(log N) lần nhảy.

text

Cần nhảy 13 bậc từ node X:
  13 = 1101₂ = 8 + 4 + 1

  X  ──(nhảy 1)──▶  A  ──(nhảy 4)──▶  B  ──(nhảy 8)──▶  C
     ancestor 2⁰       ancestor 2²       ancestor 2³
     = cha              = ông cố 4 đời    = tổ 8 đời

  3 lần nhảy thay vì 13 bước!

Bảng sparse: Tiền xử lý bảng up[k][v] = tổ tiên thứ 2^k của node v. up[0][v] = cha trực tiếp. up[1][v] = ông (cha của cha). up[2][v] = cụ (cha của ông). Mỗi hàng tính từ hàng trước: up[k][v] = up[k-1][up[k-1][v]].

📌 Khi nào analogy bị phá vỡ

Binary lifting giả định cây tĩnh — cấu trúc không thay đổi. Nếu cây bị chỉnh sửa liên tục (thêm/xóa node), cần cấu trúc động hơn như Euler Tour Tree hoặc Link-Cut Tree.

Cốt lõi kỹ thuật

Xây bảng Binary Lifting

Preprocessing DFS để tính depth[] và up[][]. up[k][v] = tổ tiên thứ 2^k của v.

C++PythonJavaGo

cpp

#include <vector>
using namespace std;

const int LOG = 20; // đủ cho N ≤ 10^6

struct LCA {
    int n;
    vector<vector<int>> adj;
    vector<int> depth;
    vector<array<int, LOG>> up;

    LCA(int n) : n(n), adj(n), depth(n, 0), up(n) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void build(int root = 0) {
        // BFS to compute depth and up table
        vector<bool> visited(n, false);
        queue<int> q;
        q.push(root);
        visited[root] = true;
        up[root].fill(-1);

        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    depth[v] = depth[u] + 1;
                    up[v][0] = u;
                    for (int k = 1; k < LOG; k++) {
                        up[v][k] = up[v][k-1] == -1
                            ? -1 : up[up[v][k-1]][k-1];
                    }
                    q.push(v);
                }
            }
        }
    }

    int liftUp(int v, int dist) {
        for (int k = LOG - 1; k >= 0; k--) {
            if (dist >= (1 << k) && v != -1) {
                v = up[v][k];
                dist -= (1 << k);
            }
        }
        return v;
    }

    int query(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        u = liftUp(u, depth[u] - depth[v]);

        if (u == v) return u;

        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];
    }

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

python

from collections import deque

LOG = 20

class LCA:
    def __init__(self, n: int):
        self.n = n
        self.adj: list[list[int]] = [[] for _ in range(n)]
        self.depth = [0] * n
        self.up = [[-1] * LOG for _ in range(n)]

    def add_edge(self, u: int, v: int):
        self.adj[u].append(v)
        self.adj[v].append(u)

    def build(self, root: int = 0):
        visited = [False] * self.n
        visited[root] = True
        q = deque([root])

        while q:
            u = q.popleft()
            for v in self.adj[u]:
                if not visited[v]:
                    visited[v] = True
                    self.depth[v] = self.depth[u] + 1
                    self.up[v][0] = u
                    for k in range(1, LOG):
                        anc = self.up[v][k - 1]
                        self.up[v][k] = self.up[anc][k - 1] if anc != -1 else -1
                    q.append(v)

    def lift_up(self, v: int, dist: int) -> int:
        for k in range(LOG - 1, -1, -1):
            if dist >= (1 << k) and v != -1:
                v = self.up[v][k]
                dist -= (1 << k)
        return v

    def query(self, u: int, v: int) -> int:
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        u = self.lift_up(u, self.depth[u] - self.depth[v])

        if u == v:
            return u

        for k in range(LOG - 1, -1, -1):
            if self.up[u][k] != self.up[v][k]:
                u = self.up[u][k]
                v = self.up[v][k]

        return self.up[u][0]

    def dist(self, u: int, v: int) -> int:
        lca = self.query(u, v)
        return self.depth[u] + self.depth[v] - 2 * self.depth[lca]

java

import java.util.*;

class LCA {
    static final int LOG = 20;
    int n;
    List<List<Integer>> adj;
    int[] depth;
    int[][] up;

    LCA(int n) {
        this.n = n;
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        depth = new int[n];
        up = new int[n][LOG];
        for (int[] row : up) Arrays.fill(row, -1);
    }

    void addEdge(int u, int v) {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }

    void build(int root) {
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.add(root);
        visited[root] = true;

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    depth[v] = depth[u] + 1;
                    up[v][0] = u;
                    for (int k = 1; k < LOG; k++)
                        up[v][k] = up[v][k-1] == -1 ? -1 : up[up[v][k-1]][k-1];
                    q.add(v);
                }
            }
        }
    }

    int query(int u, int v) {
        if (depth[u] < depth[v]) { int t = u; u = v; v = t; }
        int diff = depth[u] - depth[v];
        for (int k = LOG - 1; k >= 0; k--)
            if ((diff & (1 << k)) != 0) u = up[u][k];
        if (u == v) return u;
        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];
    }

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

const LOG = 20

type LCA struct {
    n     int
    adj   [][]int
    depth []int
    up    [][LOG]int
}

func NewLCA(n int) *LCA {
    adj := make([][]int, n)
    depth := make([]int, n)
    up := make([][LOG]int, n)
    for i := range up {
        for k := 0; k < LOG; k++ {
            up[i][k] = -1
        }
    }
    return &LCA{n: n, adj: adj, depth: depth, up: up}
}

func (l *LCA) AddEdge(u, v int) {
    l.adj[u] = append(l.adj[u], v)
    l.adj[v] = append(l.adj[v], u)
}

func (l *LCA) Build(root int) {
    visited := make([]bool, l.n)
    visited[root] = true
    q := []int{root}
    for len(q) > 0 {
        u := q[0]; q = q[1:]
        for _, v := range l.adj[u] {
            if !visited[v] {
                visited[v] = true
                l.depth[v] = l.depth[u] + 1
                l.up[v][0] = u
                for k := 1; k < LOG; k++ {
                    anc := l.up[v][k-1]
                    if anc == -1 { l.up[v][k] = -1 } else {
                        l.up[v][k] = l.up[anc][k-1]
                    }
                }
                q = append(q, v)
            }
        }
    }
}

func (l *LCA) Query(u, v int) int {
    if l.depth[u] < l.depth[v] { u, v = v, u }
    diff := l.depth[u] - l.depth[v]
    for k := LOG - 1; k >= 0; k-- {
        if diff >= (1 << k) {
            u = l.up[u][k]
            diff -= (1 << k)
        }
    }
    if u == v { return u }
    for k := LOG - 1; k >= 0; k-- {
        if l.up[u][k] != l.up[v][k] {
            u = l.up[u][k]
            v = l.up[v][k]
        }
    }
    return l.up[u][0]
}

func (l *LCA) Dist(u, v int) int {
    lca := l.Query(u, v)
    return l.depth[u] + l.depth[v] - 2*l.depth[lca]
}

LCA query — hai bước

Bước 1 — cân bằng depth: Nếu depth[u] > depth[v], nâng u lên cho cùng depth với v bằng binary lifting. Phân tích hiệu depth thành nhị phân, nhảy theo từng bit.

Bước 2 — nhảy song song: Cả u và v cùng nhảy lên. Nếu up[k][u] != up[k][v], cả hai nhảy lên — vì LCA nằm cao hơn. Nếu up[k][u] == up[k][v], không nhảy — LCA có thể nằm thấp hơn. Sau khi duyệt hết k, up[0][u] chính là LCA.

Khoảng cách trên cây

text

dist(u, v) = depth[u] + depth[v] - 2 × depth[LCA(u, v)]

Đây là công thức cốt lõi cho mọi bài toán path query trên cây.

Thực chiến

Tình huống 1: Git merge-base

Bối cảnh: Tìm commit chung gần nhất giữa hai branch — chính là LCA trên commit tree.

python

def git_merge_base(commits: int, parent_edges: list[tuple[int, int]],
                   branch_a: int, branch_b: int) -> int:
    lca = LCA(commits)
    for child, par in parent_edges:
        lca.add_edge(child, par)
    lca.build(0)  # root commit = 0
    return lca.query(branch_a, branch_b)

Tình huống 2: Khoảng cách giữa hai node trên cây

Bối cảnh: File system tree — tính số thư mục cần traverse từ file A đến file B.

python

def file_distance(n: int, edges: list[tuple[int, int]],
                  file_a: int, file_b: int) -> int:
    lca = LCA(n)
    for u, v in edges:
        lca.add_edge(u, v)
    lca.build(0)
    return lca.dist(file_a, file_b)

Sai lầm điển hình

❌ Sai lầm 1: Quên xử lý khi một node là tổ tiên của node kia

Vấn đề: Sau khi cân bằng depth, quên kiểm tra u == v.

python

# SAI: thiếu check u == v sau lift
u = self.lift_up(u, self.depth[u] - self.depth[v])
# tiếp tục nhảy song song → sai nếu u đã == v

Tại sao sai: Nếu v là tổ tiên của u, sau khi lift u lên cùng depth thì u == v → LCA chính là v. Không kiểm tra sẽ nhảy thêm và trả về tổ tiên cao hơn (sai).

python

# ĐÚNG: kiểm tra ngay sau khi cân bằng depth
u = self.lift_up(u, self.depth[u] - self.depth[v])
if u == v:
    return u

❌ Sai lầm 2: Sai thứ tự duyệt k trong binary lifting

Vấn đề: Duyệt k từ 0 lên thay vì từ LOG-1 xuống.

python

# SAI: duyệt k từ nhỏ đến lớn
for k in range(LOG):
    if self.up[u][k] != self.up[v][k]:
        u = self.up[u][k]
        v = self.up[v][k]

Tại sao sai: Phải duyệt từ lũy thừa lớn nhất xuống nhỏ nhất. Nhảy lớn trước, nhảy nhỏ sau — như cách đọc số nhị phân từ bit cao. Duyệt ngược cho kết quả sai vì nhảy quá xa rồi không thể quay lại.

python

# ĐÚNG: duyệt k từ LOG-1 xuống 0
for k in range(LOG - 1, -1, -1):
    if self.up[u][k] != self.up[v][k]:
        u = self.up[u][k]
        v = self.up[v][k]

❌ Sai lầm 3: LOG quá nhỏ cho N

Vấn đề: LOG = 17 nhưng N có thể lên 10⁶.

python

# SAI: LOG = 17 chỉ đủ cho N ≤ 2^17 = 131072
LOG = 17

Tại sao sai: 2^17 = 131,072. Nếu N = 500,000 thì cần ít nhất LOG = 19 (2^19 = 524,288). Thiếu LOG khiến nhảy không đủ xa → LCA sai.

python

# ĐÚNG: LOG = 20 đủ cho N ≤ 10^6
LOG = 20  # 2^20 = 1,048,576

Under the Hood

Hiệu năng

Giai đoạn	Time	Space
Preprocessing (build)	O(N log N)	O(N log N)
Mỗi LCA query	O(log N)	O(1)
K-th ancestor query	O(log N)	O(1)
Distance query	O(log N)	O(1)

Space O(N log N) cho bảng up[][] — với N = 10⁶ và LOG = 20, cần 20 triệu int ≈ 80 MB. Có thể tối ưu bằng cách dùng Euler Tour + Sparse Table RMQ.

So sánh các phương pháp LCA

Phương pháp	Preprocessing	Query	Space	Ghi chú
Naive (leo từng bậc)	O(N)	O(N)	O(N)	Quá chậm
Binary Lifting	O(N log N)	O(log N)	O(N log N)	Cân bằng, dễ cài
Euler Tour + RMQ	O(N)	O(1)	O(N)	Query nhanh nhất
Heavy-Light Decomposition	O(N)	O(log N)	O(N)	Linh hoạt cho path query

Binary Lifting là lựa chọn phổ biến nhất cho competitive programming và production: cài đặt rõ ràng, dễ debug, hỗ trợ tự nhiên k-th ancestor. Euler Tour + RMQ tối ưu hơn lý thuyết (O(1) query) nhưng cài phức tạp hơn.

Euler Tour + RMQ — phương pháp thay thế

DFS tạo Euler Tour: mỗi khi vào/ra một node, ghi lại. LCA(u, v) = node có depth nhỏ nhất giữa lần xuất hiện đầu tiên của u và v trong tour. Bài toán quy về Range Minimum Query (RMQ) — giải bằng Sparse Table O(1) query hoặc Segment Tree O(log N) query.

Checklist ghi nhớ

✅ Checklist triển khai

Xây dựng

[ ] Bảng up[k][v] = tổ tiên thứ 2^k của v
[ ] Transition: up[k][v] = up[k-1][up[k-1][v]]
[ ] LOG đủ lớn: LOG ≥ ceil(log2(N)) + 1
[ ] DFS/BFS từ root để tính depth[] và up[0][v] = parent[v]

LCA query

[ ] Bước 1: cân bằng depth — lift node sâu hơn lên
[ ] Kiểm tra u == v sau bước 1
[ ] Bước 2: duyệt k từ LOG-1 xuống 0, nhảy khi up[k][u] != up[k][v]
[ ] Kết quả: up[0][u] sau vòng lặp

Ứng dụng

[ ] Khoảng cách: dist(u,v) = depth[u] + depth[v] - 2*depth[LCA(u,v)]
[ ] K-th ancestor: phân tích K thành nhị phân, nhảy theo từng bit
[ ] Path query: split thành u→LCA và LCA→v

Bài tập luyện tập

Bài 1: Kth Ancestor of a Tree Node — Foundation

Đề bài: Cho cây N node, trả lời Q query dạng: tổ tiên thứ k của node v. Trả về -1 nếu không tồn tại. (LeetCode 1483)

🧠 Quiz

Preprocessing binary lifting table tốn bao nhiêu thời gian và bộ nhớ?

[ ] A. O(N) time, O(N) space
[x] B. O(N log N) time, O(N log N) space
[ ] C. O(N²) time, O(N²) space
[ ] D. O(N) time, O(N log N) space Giải thích: Có N node × LOG levels = N × log N ô trong bảng. Mỗi ô tính O(1) từ ô trước đó. Tổng: O(N log N) time và space.

💡 Gợi ý

Xây bảng binary lifting từ parent array
Mỗi query: phân tích k thành nhị phân, nhảy theo từng bit 1
Chú ý: nếu nhảy ra ngoài root (= -1), trả về -1

✅ Lời giải

python

class TreeAncestor:
    def __init__(self, n: int, parent: list[int]):
        self.LOG = 20
        self.up = [[-1] * self.LOG for _ in range(n)]
        for v in range(n):
            self.up[v][0] = parent[v]
        for k in range(1, self.LOG):
            for v in range(n):
                if self.up[v][k-1] != -1:
                    self.up[v][k] = self.up[self.up[v][k-1]][k-1]

    def getKthAncestor(self, node: int, k: int) -> int:
        v = node
        for bit in range(self.LOG):
            if k & (1 << bit) and v != -1:
                v = self.up[v][bit]
        return v

Phân tích: Preprocessing O(N log N), mỗi query O(log N). Space O(N log N).

Bài 2: Distance Between Nodes — Intermediate

Đề bài: Cho cây N node và Q query. Mỗi query (u, v): tính khoảng cách giữa u và v.

💡 Gợi ý

Build LCA với binary lifting
dist(u, v) = depth[u] + depth[v] - 2 * depth[LCA(u, v)]
Cẩn thận: cây có thể root ở bất kỳ node nào

✅ Lời giải

python

def solve_distance_queries(n: int, edges: list[tuple[int, int]],
                           queries: list[tuple[int, int]]) -> list[int]:
    lca = LCA(n)
    for u, v in edges:
        lca.add_edge(u, v)
    lca.build(0)
    return [lca.dist(u, v) for u, v in queries]

Phân tích: Preprocessing O(N log N), mỗi query O(log N), tổng O((N + Q) log N).

Liên kết học tiếp

Từ khóa glossary: LCA, binary lifting, tổ tiên chung gần nhất, sparse table, Euler tour, k-th ancestor

Tìm kiếm liên quan: tổ tiên chung, lowest common ancestor, tree distance, git merge-base, binary lifting

LCA với Binary Lifting — Tổ tiên chung gần nhất ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Xây bảng Binary Lifting ​

LCA query — hai bước ​

Khoảng cách trên cây ​

Thực chiến ​

Tình huống 1: Git merge-base ​

Tình huống 2: Khoảng cách giữa hai node trên cây ​

Sai lầm điển hình ​

❌ Sai lầm 1: Quên xử lý khi một node là tổ tiên của node kia ​

❌ Sai lầm 2: Sai thứ tự duyệt k trong binary lifting ​

❌ Sai lầm 3: LOG quá nhỏ cho N ​

Under the Hood ​

Hiệu năng ​

So sánh các phương pháp LCA ​

Euler Tour + RMQ — phương pháp thay thế ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Kth Ancestor of a Tree Node — Foundation ​

Bài 2: Distance Between Nodes — Intermediate ​

Liên kết học tiếp ​

LCA với Binary Lifting — Tổ tiên chung gần nhất

Bức tranh tư duy

Cốt lõi kỹ thuật

Xây bảng Binary Lifting

LCA query — hai bước

Khoảng cách trên cây

Thực chiến

Tình huống 1: Git merge-base

Tình huống 2: Khoảng cách giữa hai node trên cây

Sai lầm điển hình

❌ Sai lầm 1: Quên xử lý khi một node là tổ tiên của node kia

❌ Sai lầm 2: Sai thứ tự duyệt k trong binary lifting

❌ Sai lầm 3: LOG quá nhỏ cho N

Under the Hood

Hiệu năng

So sánh các phương pháp LCA

Euler Tour + RMQ — phương pháp thay thế

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Kth Ancestor of a Tree Node — Foundation

Bài 2: Distance Between Nodes — Intermediate

Liên kết học tiếp