Heavy-Light Decomposition (HLD)

Heavy-Light Decomposition turns each tree path into a small number of contiguous array ranges. A range-query data structure can then answer queries such as the sum or maximum along a path while vertex values change. It is a static-tree technique: values may change, but edges stay fixed. HLD combines subtree sizes, a carefully chosen array order, and an ordinary Fenwick or segment tree. The example implements point assignment and path sums using a Fenwick tree; the decomposition itself is independent of that choice.

Prerequisites: Subtree sizes, rooted-tree depth, Fenwick or segment trees, logarithmic complexity.

Build the idea

1. 1. Choose a heavy child. Root the tree at 1 and calculate parent, depth, and size. For every nonleaf vertex v, choose a child with maximum subtree size and call it heavy[v]. Other child edges are light. Follow heavy edges to form chains; head[v] identifies the highest vertex of its chain. Ties can be resolved arbitrarily. A chain does not have to begin at the root, and a heavy child is defined by subtree size, not by depth or label.
2. 2. Why only logarithmically many light edges occur. If c is a light child of v, a heavy sibling has size at least size[c]. Thus size[v]≥1+2·size[c]: crossing a light edge downward more than halves the remaining subtree size. A root-to-vertex path has O(log N) light edges. Any u–v path consists of two such upward paths, so it meets O(log N) heavy-chain segments. Heavy edges themselves can form a very long chain; one range query handles that entire segment.
3. 3. Assign consecutive array positions. Walk each chain from its head through heavy children and assign pos[v] successively. Save each light child as the head of a new chain to process later. Every chain is contiguous in top-to-bottom order. Store value[v] at pos[v] in the Fenwick tree. This program initializes that structure using N point additions in O(N log N). The decomposition alone is O(N); a segment tree could instead be built in O(N) over the same array.
4. 4. Remove the deeper chain segment. While head[u] differs from head[v], choose the endpoint whose chain head has greater depth. Add the range sum from pos[head[u]] through pos[u], then set u=parent[head[u]]. This removes a complete chain suffix without crossing the LCA. When both endpoints share a head, the remaining path is the range between their positions. Add that range once, including both endpoints. No separately calculated LCA is needed.
5. 5. Work a query and update. Use edges 1–2, 1–3, 2–4, 2–5 with values [1,2,3,4,5]. One chain choice is 1–2–4, with singleton chains 3 and 5. Path 4–3 splits into [4,2,1] and [3], totaling 10. Path 4–5 totals 11. Assigning vertex 2 the value 10 changes the latter sum to 19. An assignment must add new−old to the Fenwick tree, because its native update is addition, not replacement.
6. 6. Respect orientation and scope. This program handles vertex sums, a commutative operation. For edge values, store each edge at its deeper endpoint and omit the LCA's position in the final same-chain interval. For string concatenation or matrix multiplication, upward and downward segments have different directions: store forward/reverse aggregates and combine them in path order. Range path updates need a suitable lazy segment tree. HLD does not support arbitrary link/cut operations without a different dynamic-tree technique.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
struct Fenwick{
    int n;
    vector<long long>bit;
    Fenwick(int n):n(n),bit(n+1){
    }
    void add(int p,long long x){
        for(;p<=n;p+=p&-p){
            bit[p]+=x;
        }
    }
    long long prefix(int p){
        long long s=0;
        for(;p>0;p-=p&-p){
            s+=bit[p];
        }
        return s;
    }
    long long range(int l,int r){
        return prefix(r)-prefix(l-1);
    }
};
int main(){
    int n,q;
    cin>>n>>q;
    vector<long long>value(n+1);
    for(int v=1;v<=n;v++){
        cin>>value[v];
    }
    vector<vector<int>>g(n+1);
    for(int i=1,u,v;i<n;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // First root the tree: every parent precedes its children in order.
    vector<int>par(n+1),dep(n+1),sz(n+1,1),heavy(n+1),order{1};
    for(int i=0;i<(int)order.size();i++){
        int v=order[i];
        for(int u:g[v]){
            if(u!=par[v]){
                par[u]=v;
                dep[u]=dep[v]+1;
                order.push_back(u);
            }
        }
    }
    // Reverse order computes subtree sizes and chooses the largest child.
    for(int i=n-1;i>=0;i--){
        int v=order[i];
        for(int u:g[v]){
            if(par[u]==v){
                sz[v]+=sz[u];
                if(!heavy[v]||sz[u]>sz[heavy[v]]){
                    heavy[v]=u;
                }
            }
        }
    }
    vector<int>head(n+1),pos(n+1);
    // Process a heavy chain consecutively; light children begin new chains.
    vector<pair<int,int>>pending{{1,1}};
    int timer=0;
    while(!pending.empty()){
        auto[v,h]=pending.back();
        pending.pop_back();
        for(;v!=0;v=heavy[v]){
            head[v]=h;
            pos[v]=++timer;
            for(int u:g[v]){
                if(par[u]==v&&u!=heavy[v]){
                    pending.push_back({u,u});
                }
            }
        }
    }
    Fenwick bit(n);
    for(int v=1;v<=n;v++){
        bit.add(pos[v],value[v]);
    }
    while(q--){
        int type;
        cin>>type;
        if(type==1){
            int v;
            long long x;
            cin>>v>>x;
            // Fenwick updates add a delta; subtract the old value for assignment.
            bit.add(pos[v],x-value[v]);
            value[v]=x;
        }
        else{
            int u,v;
            cin>>u>>v;
            long long answer=0;
            while(head[u]!=head[v]){
                if(dep[head[u]]<dep[head[v]]){
                    swap(u,v);
                }
                answer+=bit.range(pos[head[u]],pos[u]);
                // Remove the queried chain segment by jumping above its head.
                u=par[head[u]];
            }
            if(pos[u]>pos[v]){
                swap(u,v);
            }
            // The final same-chain range includes the LCA exactly once.
            answer+=bit.range(pos[u],pos[v]);
            cout<<answer<<'\n';
        }
    }
}

Complexity analysis

Decomposition O(N); this Fenwick initialization O(N log N). Point assignment O(log N), path sum O(log² N): O(log N) chain ranges each cost O(log N). O(N) space. Static per-chain prefix aggregates can improve some variants; this dynamic implementation has the log-squared bound.

Example input and output

N Q, N vertex values, N−1 edges, then operations: 1 v x assigns value[v]=x; 2 u v prints the inclusive path sum.

Input

5 4
1 2 3 4 5
1 2
1 3
2 4
2 5
2 4 3
2 4 5
1 2 10
2 4 5

Output

10
11
19

The first path contains 4,2,1,3. After value[2]=10, path 4–5 sums to 4+10+5.

Practical applications

Dynamic vertex/edge path aggregates and path updates with lazy segment trees. Euler flattening is simpler for pure subtree queries; binary lifting is simpler for ancestor-only queries.

Check your understanding

Why does a path cross only O(log N) light edges?

Put it into practice

Replace path sums with path maxima using a segment tree.