Heavy-Light Decomposition (HLD)

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

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

Heavy-Light Decomposition (HLD) là kỹ thuật phân rã cây thành các chain (chuỗi đỉnh liên tiếp), cho phép truy vấn và cập nhật trên đường đi giữa hai đỉnh bất kỳ trong $O (\log^{2} N)$ — hoặc $O (\log N)$ nếu dùng Segment Tree với Euler tour.

Ứng dụng: Truy vấn tổng, max, min trên đường đi $u \to v$ trong cây cố định.

Ý tưởng

Với mỗi đỉnh $u$ , chọn con nặng (heavy child) là con có cây con lớn nhất. Cạnh tới heavy child gọi là heavy edge; các cạnh còn lại là light edge.

Tính chất quan trọng: Trên bất kỳ đường đi từ gốc đến lá, số lần chuyển từ chain này sang chain khác (qua light edge) không vượt quá $O (\log N)$ , vì mỗi lần đi qua light edge, kích thước cây con ít nhất nhân đôi.

Mỗi dãy heavy edge liên tiếp tạo thành một heavy chain. Sau khi gán nhãn DFS theo thứ tự ưu tiên heavy child, các đỉnh trong cùng một chain có chỉ số liên tiếp — có thể dùng Segment Tree để truy vấn đoạn.

Cài đặt

const int MAXN = 2e5 + 5;

vector<int> adj[MAXN];
int par[MAXN], dep[MAXN], sz[MAXN], heavy[MAXN];
int head[MAXN], pos[MAXN], cur_pos;
long long val[MAXN];   // giá trị tại mỗi đỉnh

// Bước 1: DFS tính kích thước cây con và heavy child
int dfs(int u, int p, int d) {
    par[u] = p; dep[u] = d; sz[u] = 1;
    heavy[u] = -1;
    int max_sz = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        sz[u] += dfs(v, u, d+1);
        if (sz[v] > max_sz) { max_sz = sz[v]; heavy[u] = v; }
    }
    return sz[u];
}

// Bước 2: Gán nhãn DFS theo chain (ưu tiên heavy child trước)
void decompose(int u, int h) {
    head[u] = h;
    pos[u]  = ++cur_pos;
    if (heavy[u] != -1) decompose(heavy[u], h);
    for (int v : adj[u])
        if (v != par[u] && v != heavy[u])
            decompose(v, v);   // v là đầu chain mới
}

// Khởi tạo
void build(int root, int n) {
    cur_pos = 0;
    dfs(root, root, 0);
    decompose(root, root);
    // Sau đó build Segment Tree trên mảng pos[]
}

Segment Tree hỗ trợ

struct SegTree {
    int n;
    vector<long long> tree;
    SegTree(int n) : n(n), tree(4*n+5, 0) {}

    void update(int node, int l, int r, int p, long long v) {
        if (l == r) { tree[node] = v; return; }
        int mid = (l+r)/2;
        if (p <= mid) update(2*node, l, mid, p, v);
        else          update(2*node+1, mid+1, r, p, v);
        tree[node] = tree[2*node] + tree[2*node+1];
    }

    long long query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l+r)/2;
        return query(2*node, l, mid, ql, qr)
             + query(2*node+1, mid+1, r, ql, qr);
    }
} seg(MAXN);

Truy vấn đường đi

// Truy vấn tổng trên đường đi u → v
long long path_query(int u, int v) {
    long long res = 0;
    while (head[u] != head[v]) {
        if (dep[head[u]] < dep[head[v]]) swap(u, v);
        // u có chain head sâu hơn — truy vấn từ head[u] đến u
        res += seg.query(1, 1, MAXN, pos[head[u]], pos[u]);
        u = par[head[u]];   // nhảy lên chain cha
    }
    // u và v cùng chain — truy vấn đoạn [min_pos, max_pos]
    if (dep[u] > dep[v]) swap(u, v);
    res += seg.query(1, 1, MAXN, pos[u], pos[v]);
    return res;
}

// Cập nhật giá trị đỉnh u
void path_update(int u, long long v) {
    seg.update(1, 1, MAXN, pos[u], v);
}

Ví dụ đầy đủ

int main() {
    int n, q;
    cin >> n >> q;

    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }

    build(1, n);

    // Đưa giá trị ban đầu vào Segment Tree
    for (int i = 1; i <= n; i++)
        seg.update(1, 1, MAXN, pos[i], val[i]);

    while (q--) {
        int op, u, v;
        cin >> op >> u >> v;
        if (op == 1) {
            path_update(u, v);   // cập nhật giá trị đỉnh u thành v
        } else {
            cout << path_query(u, v) << "\n";
        }
    }
}

HLD trên cạnh

Khi trọng số đặt trên cạnh (thay vì đỉnh), gán trọng số cạnh $(u, par [u])$ vào đỉnh $u$ (đỉnh con). Khi truy vấn, bỏ qua đỉnh LCA (vì nó không thuộc cạnh nào trên đường đi):

long long path_query_edge(int u, int v) {
    long long res = 0;
    while (head[u] != head[v]) {
        if (dep[head[u]] < dep[head[v]]) swap(u, v);
        res += seg.query(1, 1, MAXN, pos[head[u]], pos[u]);
        u = par[head[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    // Bỏ qua đỉnh u (là LCA) — chỉ truy vấn từ pos[u]+1
    if (u != v)
        res += seg.query(1, 1, MAXN, pos[u]+1, pos[v]);
    return res;
}

Độ phức tạp

	Độ phức tạp
Tiền xử lý	$O (N)$
Cập nhật đỉnh/cạnh	$O (\log N)$
Truy vấn đường đi	$O (\log^{2} N)$

So sánh với các kỹ thuật khác

	Binary Lifting	HLD	Link-Cut Tree
Cây thay đổi	Không	Không	Có
LCA	$O (\log N)$	$O (\log N)$	$O (\log N)$
Truy vấn đường đi	Không trực tiếp	$O (\log^{2} N)$	$O (\log N)$
Cài đặt	Đơn giản	Trung bình	Phức tạp

Bình luận

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