🗂️Data StructureAdvanced

HLD - Path Queries and Updates

Key Points

•
Heavy-Light Decomposition (HLD) breaks a tree into a small number of vertical chains so any path (u,v) becomes O(log n) contiguous segments in an array.
•
You can answer path sum/max queries or apply path updates by processing each chain segment with a segment tree or Fenwick tree.
•
For edge queries, store each edge’s value at the position of its deeper endpoint; for vertex queries, store the vertex value directly.
•
The number of light-edge crossings on any root-to-node path is at most O(log n), which makes HLD efficient.
•
Commutative operations (sum, max, xor) are straightforward; non-commutative operations (matrix multiply, string concat) require careful segment direction handling.
•
Path queries with HLD typically run in O((log n)^2): O(log n) segments times O(log n) per segment-tree query.
•
Lazy propagation enables path range updates (e.g., add to every vertex/edge on a path) in the same O((log n)^2) time.
•
Be precise about inclusivity: for edge queries on the same chain, use [pos[v]+1, pos[u]] when u is deeper to exclude the LCA’s slot.

Prerequisites

→Trees (rooted, parent/child, depth) — HLD organizes a tree by sizes and depths and relies on parent-child relationships.
→Depth-First Search (DFS) — Used to compute subtree sizes, parents, and to linearize nodes into chains.
→Segment trees and lazy propagation — Path segments are processed with range data structures; lazy propagation enables path range updates.
→Lowest Common Ancestor (LCA) basics — HLD implicitly computes LCA by chain comparisons; understanding LCA helps reason about path decomposition.
→Associativity and (non-)commutativity — Segment aggregation requires associativity; non-commutative operations need direction-aware handling.
→Modular arithmetic (for matrix or hash examples) — Many tasks use modulo operations for stability and constraints.

Detailed Explanation

Tap terms for definitions

01Overview

Heavy-Light Decomposition (HLD) is a technique to convert hard tree path problems into easier array interval problems. The core idea is to split the tree into vertex-disjoint chains by marking, for each node, one "heavy" child (the child with the largest subtree). Nodes connected through heavy edges form heavy paths (chains); transitions between chains happen over light edges. Because moving along a light edge at least halves the remaining subtree size, any root-to-node path crosses only O(log n) light edges. We then map the tree nodes to a base array in chain order. A path (u, v) is decomposed into O(log n) contiguous segments in that array. With this mapping, standard range data structures (like segment trees with or without lazy propagation, or Fenwick trees) can process each segment efficiently. This enables path queries (sum, max, xor) and path updates (add, assign) in O((log n)^2) time. HLD works for both vertex-weighted and edge-weighted problems; for edges, we store an edge’s value at the deeper endpoint’s array position. For non-commutative operations (e.g., matrix multiply along the path direction), we must respect the order of segments: up-segments must be aggregated in reverse direction and down-segments in forward direction, then concatenated in the correct order.

02Intuition & Analogies

Imagine a city with many small streets and a few long highways. If you want to travel far, you aim to stay on highways as much as possible and only use a few short local streets to get on and off. HLD builds that road system inside your tree. From each intersection (node), you pick the busiest outgoing road (the heavy child, representing the largest part of the city reachable through it). Chaining these heavy roads creates long highways (heavy paths). Any trip in the city—your path from u to v—uses only a handful of local streets (light edges) to hop between highways, because each time you leave a highway, the remaining region you still need to cover shrinks by at least half. Now, label every intersection in the order you would encounter them if you drove each highway straight through. Suddenly, the highway segments of your trip are contiguous intervals in a simple 1D list. Classic interval tools, like a “toll counter” (segment tree for sums) or a “speed camera” (segment tree for max), can quickly tell you the total toll or the maximum speed limit over those contiguous pieces. If you want to add a tax to every road you take, a data structure with lazy updates can add that tax to all roads in each segment quickly. When the operation isn’t symmetric (e.g., multiplying matrices or concatenating strings where order matters), you just have to remember direction: the parts where you drive uphill are read backward, while the downhill parts are read forward, and you glue them together in the order you travel.

03Formal Definition

Given a rooted tree T with n nodes, define for each node u its subtree size sz(u). Let heavy(u) be the child v of u maximizing sz(v); edges (u, heavy(u)) are heavy, others light. A heavy path (chain) is a maximal path connected by heavy edges. HLD assigns each node u a head(u), the top of its chain, and a position pos(u) in a base array obtained by performing a DFS that first follows heavy edges. This yields: (1) Each node belongs to exactly one chain; (2) On any root-to-node path, the number of light edges is at most ⌊log2 n⌋; (3) For any pair (u, v), repeatedly climbing from the deeper chain head toward the root reduces to O(log n) steps until both nodes are in the same chain. A path (u, v) decomposes into O(log n) disjoint contiguous intervals in the base array. For vertex queries, values a[u] are stored at pos(u). For edge queries, values w(u, p(u)) are stored at pos(u) for

u \neq = roo t

, where p(u) is the parent of u. A segment tree (optionally lazy) over the base array supports range queries/updates on each interval; combining across O(log n) intervals gives path operations in O((

lo g

n)^2) time. For non-commutative monoids (associative but order-sensitive), segment queries must respect segment direction and cross-chain concatenation order.

04When to Use

Use HLD when you need fast path queries and/or path updates on a static tree: sums, maximums, xor, counts, or even ordered operations like matrix products or string hashes. It shines in competitive programming tasks requiring many operations online on n up to ~2e5 with O((\log n)^2) time per operation. If you only need subtree queries/updates, an Euler tour with a Fenwick/segment tree is simpler and faster (O(\log n)). If the tree is dynamic (links/cuts), consider Link-Cut Trees or Euler Tour Trees for generality. If you need LCA queries only, binary lifting or RMQ on Euler tour is simpler. For edge vs vertex tasks: choose vertex mode when each node has an intrinsic value; choose edge mode when weights live on edges and queries refer to edge aggregates along paths. For non-commutative operations (e.g., path matrix multiply, function composition along directed paths), HLD remains applicable but you must implement direction-aware segment merging. If your operation is invertible and you need path updates plus path queries, careful data-structure design or rerooting techniques may simplify certain cases, otherwise stick to lazy segment trees within HLD.

⚠️Common Mistakes

Mixing edge and vertex indexing: For edge problems, store w(parent(u), u) at pos(u) and remember to exclude the LCA’s position in same-chain queries by using [pos[v]+1, pos[u]] when u is deeper. For vertex problems, include both endpoints.
Wrong segment direction for non-commutative ops: Upward segments should be aggregated in reverse order (use a backward aggregate), while downward segments use forward order; finally concatenate “up” result before the reversed list of “down” results.
Incorrect chain jump: Always move up from the node whose chain head is deeper (compare depth[head[u]] and depth[head[v]]). Otherwise, you might loop or use too many segments.
Off-by-one errors in intervals: Ensure l ≤ r when querying; when u and v are in the same chain, define l = pos[v], r = pos[u] if depth[u] ≥ depth[v]. For edge queries, shift l by +1 to exclude the LCA’s slot.
Forgetting to build the base array in chain order: The segment tree must be built on values placed at pos(u) after decomposition.
Ignoring recursion limits: DFS for sizes and decomposition can overflow the stack for large n; consider iterative DFS or increase stack size when needed.
Lazy propagation bugs: Always push lazy tags before descending to children and pull (recompute) values after updates.
Using non-associative operations: Segment trees require associativity; if your operation isn’t associative, you can’t combine segments reliably.

Key Formulas

Light-edge bound

\text{# light edges on any root-to-node path} \le \lfloor \log_2 n \rfloor

Explanation: Each time you traverse a light edge, the remaining subtree size at least halves. Therefore you can do this at most floor(log2 n) times along any path.

HLD path complexity

T_{path} (n) = O ((lo g n)^{2})

Explanation: A path decomposes into O(log n) segments and each segment-tree query or update takes O(log n) time, giving O((log n)^2) per path operation.

Build complexity

Build time of HLD = O (n) (DFS + decomposition)

Explanation: Computing subtree sizes and heavy children is O(n), and assigning positions in the base array is O(n). Building a segment tree is also O(n).

Segment tree height

Segment tree height = ⌈ lo g_{2} n ⌉

Explanation: A balanced binary segment tree has logarithmic height in the number of leaves, dictating the time per query/update.

Edge-to-array mapping

Edge mapping: b [pos (u)] = w (parent (u), u) for u \neq = root

Explanation: To support edge queries, store each edge’s value at the array index of its deeper endpoint. The root has no incoming edge, so it holds a neutral element.

Ordered path product

prod (u \to v) = (x \in (u \to w] \prod a_{x}) \cdot a_{w} \cdot (x \in [w \to v) \prod a_{x}), w = LCA (u, v)

Explanation: For non-commutative monoids, the product along the path from u to v equals the product from u up to (but excluding) w, then the value at w, then the product from w down to v. Segment directions must match the travel order.

Range add, range sum

i = l \sum r a_{i} lazy add a_{i} \leftarrow a_{i} + Δ \forall i \in [l, r]

Explanation: Lazy propagation applies the same increment to all elements in a query range in O(log n), allowing fast path-add updates combined across O(log n) segments.

Complexity Analysis

Preprocessing runs in O(n): one DFS computes subtree sizes, parents, depths, and selects heavy children; a second DFS assigns head[u] and pos[u], filling the base array. Building a segment tree over the base array is also O(n). For a path query or update, HLD decomposes the path (u, v) into O(log n) contiguous segments by repeatedly jumping from the deeper chain head upward. Each segment is processed by a segment tree operation in O(log n) time, so the total complexity per path operation is O((

lo g

n)^2). Constants are small and practical up to ~2e5 nodes. For edge queries, when u and v lie in the same chain, the last segment excludes pos(lca) by using [pos[v]+1, pos[u]] if depth[u] ≥ depth[v]; otherwise, the decomposition remains identical. For non-commutative operations, we may perform two passes (up and down) and store forward/backward aggregates; this adds only O(1) extra work per segment, preserving O((

lo g

n)^2) time. Space complexity is O(n) for the tree, O(n) for HLD arrays (parent, depth, heavy, head, pos, size), and O(n) for the segment tree. With lazy propagation, the segment tree typically stores arrays of size 4n for values and tags. If you maintain more data in each segment node (e.g., both forward and backward aggregates for non-commutative queries), the space remains O(n) with a larger constant. If you only need subtree queries, Euler tour reduces both time and code complexity to O(

lo g

n) per operation; dynamic trees require different structures (Link-Cut Trees).

Code Examples

HLD with lazy segment tree: path range add and path sum (vertex-weighted)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct SegTreeLazySum {
5     int n;                    // size (number of leaves)
6     vector<long long> tree;   // segment sums
7     vector<long long> lazy;   // pending adds
8 
9     SegTreeLazySum() {}
10     SegTreeLazySum(int n): n(n), tree(4*n, 0), lazy(4*n, 0) {}
11 
12     void build(const vector<long long>& a, int idx, int l, int r) {
13         if (l == r) {
14             tree[idx] = a[l];
15             return;
16         }
17         int mid = (l + r) >> 1;
18         build(a, idx<<1, l, mid);
19         build(a, idx<<1|1, mid+1, r);
20         tree[idx] = tree[idx<<1] + tree[idx<<1|1];
21     }
22     void build(const vector<long long>& a) {
23         build(a, 1, 0, n-1);
24     }
25 
26     void apply(int idx, int l, int r, long long add) {
27         tree[idx] += add * (r - l + 1);
28         lazy[idx] += add;
29     }
30     void push(int idx, int l, int r) {
31         if (lazy[idx] != 0 && l != r) {
32             int mid = (l + r) >> 1;
33             apply(idx<<1, l, mid, lazy[idx]);
34             apply(idx<<1|1, mid+1, r, lazy[idx]);
35             lazy[idx] = 0;
36         }
37     }
38 
39     void range_add(int idx, int l, int r, int ql, int qr, long long val) {
40         if (qr < l || r < ql) return;
41         if (ql <= l && r <= qr) { apply(idx, l, r, val); return; }
42         push(idx, l, r);
43         int mid = (l + r) >> 1;
44         range_add(idx<<1, l, mid, ql, qr, val);
45         range_add(idx<<1|1, mid+1, r, ql, qr, val);
46         tree[idx] = tree[idx<<1] + tree[idx<<1|1];
47     }
48     void range_add(int l, int r, long long val) { if (l>r) return; range_add(1, 0, n-1, l, r, val); }
49 
50     long long range_sum(int idx, int l, int r, int ql, int qr) {
51         if (qr < l || r < ql) return 0;
52         if (ql <= l && r <= qr) return tree[idx];
53         push(idx, l, r);
54         int mid = (l + r) >> 1;
55         return range_sum(idx<<1, l, mid, ql, qr) + range_sum(idx<<1|1, mid+1, r, ql, qr);
56     }
57     long long range_sum(int l, int r) { if (l>r) return 0; return range_sum(1, 0, n-1, l, r); }
58 };
59 
60 struct HLD {
61     int n; vector<vector<int>> g;
62     vector<int> parent, depth, heavy, head, pos, sz;
63     int cur_pos;
64     vector<long long> base;   // base array in pos-order (vertex values)
65     SegTreeLazySum st;
66 
67     HLD(int n): n(n), g(n), parent(n,-1), depth(n,0), heavy(n,-1), head(n,0), pos(n,0), sz(n,0), cur_pos(0), base(n,0), st(n) {}
68 
69     void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); }
70 
71     int dfs(int u, int p) {
72         parent[u] = p; sz[u] = 1; int max_sz = 0;
73         for (int v: g[u]) if (v != p) {
74             depth[v] = depth[u] + 1;
75             int sub = dfs(v, u);
76             sz[u] += sub;
77             if (sub > max_sz) { max_sz = sub; heavy[u] = v; }
78         }
79         return sz[u];
80     }
81 
82     void decompose(int u, int h, const vector<long long>& val) {
83         head[u] = h; pos[u] = cur_pos; base[cur_pos] = val[u]; cur_pos++;
84         if (heavy[u] != -1) decompose(heavy[u], h, val);
85         for (int v: g[u]) if (v != parent[u] && v != heavy[u]) decompose(v, v, val);
86     }
87 
88     void build(int root, const vector<long long>& val) {
89         dfs(root, -1);
90         cur_pos = 0;
91         decompose(root, root, val);
92         st = SegTreeLazySum(n);
93         st.build(base);
94     }
95 
96     // add delta to all vertices on path u-v
97     void path_add(int u, int v, long long delta) {
98         while (head[u] != head[v]) {
99             if (depth[head[u]] < depth[head[v]]) swap(u, v);
100             int hu = head[u];
101             st.range_add(pos[hu], pos[u], delta);
102             u = parent[hu];
103         }
104         if (depth[u] > depth[v]) swap(u, v);
105         // now u is LCA, add on [pos[u], pos[v]]
106         st.range_add(pos[u], pos[v], delta);
107     }
108 
109     // sum of vertex values along path u-v
110     long long path_sum(int u, int v) {
111         long long res = 0;
112         while (head[u] != head[v]) {
113             if (depth[head[u]] < depth[head[v]]) swap(u, v);
114             int hu = head[u];
115             res += st.range_sum(pos[hu], pos[u]);
116             u = parent[hu];
117         }
118         if (depth[u] > depth[v]) swap(u, v);
119         res += st.range_sum(pos[u], pos[v]);
120         return res;
121     }
122 };
123 
124 int main() {
125     ios::sync_with_stdio(false);
126     cin.tie(nullptr);
127 
128     // Example tree:
129     // 0-1, 1-2, 1-3, 3-4, 3-5, 5-6  (n=7)
130     int n = 7; HLD hld(n);
131     hld.add_edge(0,1); hld.add_edge(1,2); hld.add_edge(1,3);
132     hld.add_edge(3,4); hld.add_edge(3,5); hld.add_edge(5,6);
133 
134     vector<long long> val = {5, 1, 4, 2, 7, 3, 6};
135     hld.build(0, val);
136 
137     // Query sum on path 2-6
138     cout << "sum(2,6) = " << hld.path_sum(2,6) << "\n"; // 2->1->3->5->6 : 4+1+2+3+6 = 16
139 
140     // Add +10 to path 4-2
141     hld.path_add(4,2,10);
142 
143     // Query again after update
144     cout << "sum(2,6) after add = " << hld.path_sum(2,6) << "\n"; // nodes 2 and 4 got +10 (and 1,3 as well)
145 
146     return 0;
147 }
148

This program builds an HLD over a vertex-weighted tree. It maintains a lazy segment tree on the base array to support range add and range sum. path_add(u,v,Δ) decomposes (u,v) into O(log n) chain segments and applies range_add on each. path_sum(u,v) sums those segments. Because sum is commutative, direction does not matter.

Time: Preprocessing O(n); each path_add and path_sum is O((log n)^2).Space: O(n) for HLD arrays and O(n) for the segment tree (about 4n nodes).

HLD for edge-weighted path maximum with point edge updates

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct SegTreeMax {
5     int n; vector<long long> st;
6     const long long NEG_INF = LLONG_MIN/4;
7     SegTreeMax() {}
8     SegTreeMax(int n): n(n), st(4*n, NEG_INF) {}
9     void build(const vector<long long>& a, int idx, int l, int r) {
10         if (l==r) { st[idx]=a[l]; return; }
11         int m=(l+r)>>1; build(a,idx<<1,l,m); build(a,idx<<1|1,m+1,r);
12         st[idx]=max(st[idx<<1],st[idx<<1|1]);
13     }
14     void build(const vector<long long>& a){ build(a,1,0,n-1);}    
15     void point_set(int idx, int l, int r, int p, long long v){
16         if(l==r){st[idx]=v;return;}int m=(l+r)>>1;
17         if(p<=m) point_set(idx<<1,l,m,p,v); else point_set(idx<<1|1,m+1,r,p,v);
18         st[idx]=max(st[idx<<1],st[idx<<1|1]);
19     }
20     void point_set(int p,long long v){ point_set(1,0,n-1,p,v);}    
21     long long range_max(int idx,int l,int r,int ql,int qr){
22         if(qr<l||r<ql) return NEG_INF; if(ql<=l&&r<=qr) return st[idx];
23         int m=(l+r)>>1; return max(range_max(idx<<1,l,m,ql,qr),range_max(idx<<1|1,m+1,r,ql,qr));
24     }
25     long long range_max(int l,int r){ if(l>r) return NEG_INF; return range_max(1,0,n-1,l,r);}    
26 };
27 
28 struct HLD {
29     int n; vector<vector<pair<int,int>>> g; // (to, edgeId)
30     vector<int> parent, depth, heavy, head, pos, sz;
31     int cur_pos; vector<long long> base; // stores edge weights at deeper endpoint
32 
33     // Edge list to map id -> (u,v,w)
34     struct Edge{int u,v; long long w;};
35     vector<Edge> edges;
36 
37     SegTreeMax st;
38 
39     HLD(int n): n(n), g(n), parent(n,-1), depth(n,0), heavy(n,-1), head(n,0), pos(n,0), sz(n,0), cur_pos(0), base(n,LLONG_MIN/4), st(n) {}
40 
41     void add_edge(int u,int v,long long w){
42         int id = (int)edges.size();
43         edges.push_back({u,v,w});
44         g[u].push_back({v,id}); g[v].push_back({u,id});
45     }
46 
47     int dfs(int u,int p){
48         parent[u]=p; sz[u]=1; int mx=0;
49         for(auto [v,id]: g[u]) if(v!=p){
50             depth[v]=depth[u]+1; dfs(v,u); sz[u]+=sz[v];
51             if(sz[v]>mx){mx=sz[v]; heavy[u]=v;}
52         }
53         return sz[u];
54     }
55 
56     void decompose(int u,int h){
57         head[u]=h; pos[u]=cur_pos++;
58         if(heavy[u]!=-1) decompose(heavy[u],h);
59         for(auto [v,id]: g[u]) if(v!=parent[u] && v!=heavy[u]) decompose(v,v);
60     }
61 
62     void build(int root){
63         dfs(root,-1); cur_pos=0; decompose(root,root);
64         // place edge weights at deeper endpoint
65         for(auto &e: edges){
66             int a=e.u, b=e.v; long long w=e.w;
67             int child = (parent[a]==b? a : b);
68             // root has no incoming edge; keep NEG_INF as identity for max
69             base[pos[child]] = w;
70         }
71         st = SegTreeMax(n); st.build(base);
72     }
73 
74     // update edge by id to new weight
75     void update_edge(int id, long long w){
76         auto &e = edges[id]; e.w = w;
77         int child = (parent[e.u]==e.v? e.u : e.v);
78         st.point_set(pos[child], w);
79     }
80 
81     long long path_max(int u,int v){
82         const long long NEG_INF = LLONG_MIN/4;
83         long long ans = NEG_INF;
84         while(head[u]!=head[v]){
85             if(depth[head[u]] < depth[head[v]]) swap(u,v);
86             // edges on this segment are [pos[head[u]], pos[u]] (all valid except possibly head[u] if it is root)
87             ans = max(ans, st.range_max(pos[head[u]], pos[u]));
88             u = parent[head[u]];
89         }
90         if(depth[u] < depth[v]) swap(u,v);
91         // same chain; exclude LCA's position for edge queries
92         // edges from v->...->u are stored at positions (pos[v]+1 .. pos[u])
93         ans = max(ans, st.range_max(pos[v]+1, pos[u]));
94         return ans;
95     }
96 };
97 
98 int main(){
99     ios::sync_with_stdio(false); cin.tie(nullptr);
100 
101     // Tree:
102     // 0-1(5), 1-2(1), 1-3(7), 3-4(3), 3-5(9), 5-6(2)
103     int n=7; HLD hld(n);
104     hld.add_edge(0,1,5); hld.add_edge(1,2,1); hld.add_edge(1,3,7);
105     hld.add_edge(3,4,3); hld.add_edge(3,5,9); hld.add_edge(5,6,2);
106     hld.build(0);
107 
108     cout << "max edge on path(2,6) = " << hld.path_max(2,6) << "\n"; // expect max of edges 2-1-3-5-6 = max(1,7,9,2)=9
109     hld.update_edge(2, 0); // change edge (1,3) weight from 7 to 0 (edge id depends on insertion order)
110     cout << "after update, max edge on path(2,6) = " << hld.path_max(2,6) << "\n"; // now max is max(1,0,9,2)=9
111 
112     return 0;
113 }
114

This example shows edge-weighted HLD using a max segment tree. Each edge weight is stored at the deeper endpoint’s position. For same-chain queries, we use [pos[v]+1, pos[u]] to exclude the LCA. Edge updates are point updates in the segment tree.

Time: Preprocessing O(n). Each path_max is O((log n)^2). Each edge update is O(log n).Space: O(n) for HLD data and O(n) for the segment tree.

Non-commutative path query: ordered 2x2 matrix product along path (vertex-weighted)

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 static const long long MOD = 1000000007LL;
5 
6 struct Mat {
7     long long a[2][2];
8     Mat(long long diag = 1) { a[0][0]=a[1][1]=diag; a[0][1]=a[1][0]=0; }
9     static Mat from(long long a00,long long a01,long long a10,long long a11){ Mat m(0); m.a[0][0]=a00; m.a[0][1]=a01; m.a[1][0]=a10; m.a[1][1]=a11; return m; }
10 };
11 
12 Mat mul(const Mat& x, const Mat& y){
13     Mat r(0);
14     for(int i=0;i<2;i++) for(int k=0;k<2;k++) for(int j=0;j<2;j++){
15         r.a[i][j] = (r.a[i][j] + x.a[i][k]*y.a[k][j]) % MOD;
16     }
17     return r;
18 }
19 
20 struct SegNode { Mat fwd, bwd; }; // fwd: left->right product; bwd: right->left product
21 
22 struct SegTreeMat {
23     int n; vector<SegNode> st;
24     SegTreeMat(){}
25     SegTreeMat(int n): n(n), st(4*n){}
26 
27     static SegNode make_leaf(const Mat& m){ return {m, m}; }
28     static SegNode merge(const SegNode& L, const SegNode& R){
29         // array order: L segment then R segment
30         SegNode res;
31         res.fwd = mul(L.fwd, R.fwd);   // left-to-right
32         res.bwd = mul(R.bwd, L.bwd);   // right-to-left
33         return res;
34     }
35 
36     void build(const vector<Mat>& a, int idx, int l, int r){
37         if(l==r){ st[idx] = make_leaf(a[l]); return; }
38         int m=(l+r)>>1; build(a,idx<<1,l,m); build(a,idx<<1|1,m+1,r);
39         st[idx] = merge(st[idx<<1], st[idx<<1|1]);
40     }
41     void build(const vector<Mat>& a){ build(a,1,0,n-1); }
42 
43     void point_set(int idx,int l,int r,int p,const Mat& m){
44         if(l==r){ st[idx]=make_leaf(m); return; }
45         int mid=(l+r)>>1; if(p<=mid) point_set(idx<<1,l,mid,p,m); else point_set(idx<<1|1,mid+1,r,p,m);
46         st[idx]=merge(st[idx<<1],st[idx<<1|1]);
47     }
48     void point_set(int p,const Mat& m){ point_set(1,0,n-1,p,m); }
49 
50     SegNode range_query(int idx,int l,int r,int ql,int qr){
51         if(ql==l && r==qr) return st[idx];
52         int m=(l+r)>>1;
53         if(qr<=m) return range_query(idx<<1,l,m,ql,qr);
54         if(ql>m)  return range_query(idx<<1|1,m+1,r,ql,qr);
55         SegNode L = range_query(idx<<1,l,m,ql,m);
56         SegNode R = range_query(idx<<1|1,m+1,r,m+1,qr);
57         return merge(L,R);
58     }
59     SegNode range_query(int l,int r){ return range_query(1,0,n-1,l,r); }
60 };
61 
62 struct HLD {
63     int n; vector<vector<int>> g; 
64     vector<int> parent, depth, heavy, head, pos, sz;
65     int cur_pos; vector<Mat> base;
66     SegTreeMat st;
67 
68     HLD(int n): n(n), g(n), parent(n,-1), depth(n,0), heavy(n,-1), head(n,0), pos(n,0), sz(n,0), cur_pos(0), base(n), st(n) {}
69 
70     void add_edge(int u,int v){ g[u].push_back(v); g[v].push_back(u); }
71 
72     int dfs(int u,int p){ parent[u]=p; sz[u]=1; int mx=0; for(int v: g[u]) if(v!=p){ depth[v]=depth[u]+1; dfs(v,u); sz[u]+=sz[v]; if(sz[v]>mx){mx=sz[v]; heavy[u]=v;} } return sz[u]; }
73 
74     void decompose(int u,int h,const vector<Mat>& val){ head[u]=h; pos[u]=cur_pos; base[cur_pos]=val[u]; cur_pos++; if(heavy[u]!=-1) decompose(heavy[u],h,val); for(int v: g[u]) if(v!=parent[u] && v!=heavy[u]) decompose(v,v,val); }
75 
76     void build(int root,const vector<Mat>& val){ dfs(root,-1); cur_pos=0; decompose(root,root,val); st=SegTreeMat(n); st.build(base); }
77 
78     // Ordered product along path u -> v
79     Mat path_product(int u,int v){
80         Mat upRes(1); // identity
81         vector<Mat> downSegs; downSegs.reserve(20);
82         while(head[u]!=head[v]){
83             if(depth[head[u]] >= depth[head[v]]){
84                 auto seg = st.range_query(pos[head[u]], pos[u]);
85                 upRes = mul(upRes, seg.bwd); // going up: need right->left
86                 u = parent[head[u]];
87             }else{
88                 auto seg = st.range_query(pos[head[v]], pos[v]);
89                 downSegs.push_back(seg.fwd); // will apply later in reverse chain order
90                 v = parent[head[v]];
91             }
92         }
93         if(depth[u] >= depth[v]){
94             auto seg = st.range_query(pos[v], pos[u]);
95             upRes = mul(upRes, seg.bwd); // u up to v
96         }else{
97             auto seg = st.range_query(pos[u], pos[v]);
98             downSegs.push_back(seg.fwd); // v down from u
99         }
100         Mat res = upRes;
101         for(int i=(int)downSegs.size()-1;i>=0;--i) res = mul(res, downSegs[i]);
102         return res;
103     }
104 
105     void point_set(int u, const Mat& m){ st.point_set(pos[u], m); }
106 };
107 
108 int main(){
109     ios::sync_with_stdio(false); cin.tie(nullptr);
110 
111     // Build a small tree and assign a 2x2 matrix to each node
112     int n=6; HLD hld(n);
113     hld.add_edge(0,1); hld.add_edge(1,2); hld.add_edge(1,3); hld.add_edge(3,4); hld.add_edge(3,5);
114 
115     vector<Mat> val(n);
116     // arbitrary matrices
117     val[0]=Mat::from(1,2,3,4);
118     val[1]=Mat::from(2,0,1,2);
119     val[2]=Mat::from(0,1,1,0);
120     val[3]=Mat::from(3,1,4,1);
121     val[4]=Mat::from(1,0,0,1);
122     val[5]=Mat::from(2,2,2,2);
123 
124     hld.build(0, val);
125 
126     // Ordered product along path 2 -> 5: 2->1->3->5
127     Mat ans = hld.path_product(2,5);
128     cout << ans.a[0][0] << " " << ans.a[0][1] << "\n" << ans.a[1][0] << " " << ans.a[1][1] << "\n";
129 
130     // Update node 3's matrix
131     hld.point_set(3, Mat::from(1,1,1,1));
132     ans = hld.path_product(2,5);
133     cout << ans.a[0][0] << " " << ans.a[0][1] << "\n" << ans.a[1][0] << " " << ans.a[1][1] << "\n";
134 
135     return 0;
136 }
137

We store a 2x2 matrix at each vertex and query the ordered product along a path from u to v. The segment tree keeps both forward and backward aggregates so we can read segments in the correct direction: upward segments use bwd, downward segments use fwd, and we concatenate up-result followed by the reversed list of down-segments. This pattern generalizes to any associative non-commutative operation.

Time: Preprocessing O(n). Each ordered path query is O((log n)^2). Each point update is O(log n).Space: O(n) for HLD and O(n) for the segment tree; each segment node stores two 2x2 matrices.

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct SegTreeLazySum {
5	int n; // size (number of leaves)
6	vector<long long> tree; // segment sums
7	vector<long long> lazy; // pending adds
8
9	SegTreeLazySum() {}
10	SegTreeLazySum(int n): n(n), tree(4n, 0), lazy(4n, 0) {}
11
12	void build(const vector<long long>& a, int idx, int l, int r) {
13	if (l == r) {
14	tree[idx] = a[l];
15	return;
16	}
17	int mid = (l + r) >> 1;
18	build(a, idx<<1, l, mid);
19	build(a, idx<<1\|1, mid+1, r);
20	tree[idx] = tree[idx<<1] + tree[idx<<1\|1];
21	}
22	void build(const vector<long long>& a) {
23	build(a, 1, 0, n-1);
24	}
25
26	void apply(int idx, int l, int r, long long add) {
27	tree[idx] += add * (r - l + 1);
28	lazy[idx] += add;
29	}
30	void push(int idx, int l, int r) {
31	if (lazy[idx] != 0 && l != r) {
32	int mid = (l + r) >> 1;
33	apply(idx<<1, l, mid, lazy[idx]);
34	apply(idx<<1\|1, mid+1, r, lazy[idx]);
35	lazy[idx] = 0;
36	}
37	}
38
39	void range_add(int idx, int l, int r, int ql, int qr, long long val) {
40	if (qr < l \|\| r < ql) return;
41	if (ql <= l && r <= qr) { apply(idx, l, r, val); return; }
42	push(idx, l, r);
43	int mid = (l + r) >> 1;
44	range_add(idx<<1, l, mid, ql, qr, val);
45	range_add(idx<<1\|1, mid+1, r, ql, qr, val);
46	tree[idx] = tree[idx<<1] + tree[idx<<1\|1];
47	}
48	void range_add(int l, int r, long long val) { if (l>r) return; range_add(1, 0, n-1, l, r, val); }
49
50	long long range_sum(int idx, int l, int r, int ql, int qr) {
51	if (qr < l \|\| r < ql) return 0;
52	if (ql <= l && r <= qr) return tree[idx];
53	push(idx, l, r);
54	int mid = (l + r) >> 1;
55	return range_sum(idx<<1, l, mid, ql, qr) + range_sum(idx<<1\|1, mid+1, r, ql, qr);
56	}
57	long long range_sum(int l, int r) { if (l>r) return 0; return range_sum(1, 0, n-1, l, r); }
58	};
59
60	struct HLD {
61	int n; vector<vector<int>> g;
62	vector<int> parent, depth, heavy, head, pos, sz;
63	int cur_pos;
64	vector<long long> base; // base array in pos-order (vertex values)
65	SegTreeLazySum st;
66
67	HLD(int n): n(n), g(n), parent(n,-1), depth(n,0), heavy(n,-1), head(n,0), pos(n,0), sz(n,0), cur_pos(0), base(n,0), st(n) {}
68
69	void add_edge(int u, int v) { g[u].push_back(v); g[v].push_back(u); }
70
71	int dfs(int u, int p) {
72	parent[u] = p; sz[u] = 1; int max_sz = 0;
73	for (int v: g[u]) if (v != p) {
74	depth[v] = depth[u] + 1;
75	int sub = dfs(v, u);
76	sz[u] += sub;
77	if (sub > max_sz) { max_sz = sub; heavy[u] = v; }
78	}
79	return sz[u];
80	}
81
82	void decompose(int u, int h, const vector<long long>& val) {
83	head[u] = h; pos[u] = cur_pos; base[cur_pos] = val[u]; cur_pos++;
84	if (heavy[u] != -1) decompose(heavy[u], h, val);
85	for (int v: g[u]) if (v != parent[u] && v != heavy[u]) decompose(v, v, val);
86	}
87
88	void build(int root, const vector<long long>& val) {
89	dfs(root, -1);
90	cur_pos = 0;
91	decompose(root, root, val);
92	st = SegTreeLazySum(n);
93	st.build(base);
94	}
95
96	// add delta to all vertices on path u-v
97	void path_add(int u, int v, long long delta) {
98	while (head[u] != head[v]) {
99	if (depth[head[u]] < depth[head[v]]) swap(u, v);
100	int hu = head[u];
101	st.range_add(pos[hu], pos[u], delta);
102	u = parent[hu];
103	}
104	if (depth[u] > depth[v]) swap(u, v);
105	// now u is LCA, add on [pos[u], pos[v]]
106	st.range_add(pos[u], pos[v], delta);
107	}
108
109	// sum of vertex values along path u-v
110	long long path_sum(int u, int v) {
111	long long res = 0;
112	while (head[u] != head[v]) {
113	if (depth[head[u]] < depth[head[v]]) swap(u, v);
114	int hu = head[u];
115	res += st.range_sum(pos[hu], pos[u]);
116	u = parent[hu];
117	}
118	if (depth[u] > depth[v]) swap(u, v);
119	res += st.range_sum(pos[u], pos[v]);
120	return res;
121	}
122	};
123
124	int main() {
125	ios::sync_with_stdio(false);
126	cin.tie(nullptr);
127
128	// Example tree:
129	// 0-1, 1-2, 1-3, 3-4, 3-5, 5-6 (n=7)
130	int n = 7; HLD hld(n);
131	hld.add_edge(0,1); hld.add_edge(1,2); hld.add_edge(1,3);
132	hld.add_edge(3,4); hld.add_edge(3,5); hld.add_edge(5,6);
133
134	vector<long long> val = {5, 1, 4, 2, 7, 3, 6};
135	hld.build(0, val);
136
137	// Query sum on path 2-6
138	cout << "sum(2,6) = " << hld.path_sum(2,6) << "\n"; // 2->1->3->5->6 : 4+1+2+3+6 = 16
139
140	// Add +10 to path 4-2
141	hld.path_add(4,2,10);
142
143	// Query again after update
144	cout << "sum(2,6) after add = " << hld.path_sum(2,6) << "\n"; // nodes 2 and 4 got +10 (and 1,3 as well)
145
146	return 0;
147	}
148

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct SegTreeMax {
5	int n; vector<long long> st;
6	const long long NEG_INF = LLONG_MIN/4;
7	SegTreeMax() {}
8	SegTreeMax(int n): n(n), st(4*n, NEG_INF) {}
9	void build(const vector<long long>& a, int idx, int l, int r) {
10	if (l==r) { st[idx]=a[l]; return; }
11	int m=(l+r)>>1; build(a,idx<<1,l,m); build(a,idx<<1\|1,m+1,r);
12	st[idx]=max(st[idx<<1],st[idx<<1\|1]);
13	}
14	void build(const vector<long long>& a){ build(a,1,0,n-1);}
15	void point_set(int idx, int l, int r, int p, long long v){
16	if(l==r){st[idx]=v;return;}int m=(l+r)>>1;
17	if(p<=m) point_set(idx<<1,l,m,p,v); else point_set(idx<<1\|1,m+1,r,p,v);
18	st[idx]=max(st[idx<<1],st[idx<<1\|1]);
19	}
20	void point_set(int p,long long v){ point_set(1,0,n-1,p,v);}
21	long long range_max(int idx,int l,int r,int ql,int qr){
22	if(qr<l\|\|r<ql) return NEG_INF; if(ql<=l&&r<=qr) return st[idx];
23	int m=(l+r)>>1; return max(range_max(idx<<1,l,m,ql,qr),range_max(idx<<1\|1,m+1,r,ql,qr));
24	}
25	long long range_max(int l,int r){ if(l>r) return NEG_INF; return range_max(1,0,n-1,l,r);}
26	};
27
28	struct HLD {
29	int n; vector<vector<pair<int,int>>> g; // (to, edgeId)
30	vector<int> parent, depth, heavy, head, pos, sz;
31	int cur_pos; vector<long long> base; // stores edge weights at deeper endpoint
32
33	// Edge list to map id -> (u,v,w)
34	struct Edge{int u,v; long long w;};
35	vector<Edge> edges;
36
37	SegTreeMax st;
38
39	HLD(int n): n(n), g(n), parent(n,-1), depth(n,0), heavy(n,-1), head(n,0), pos(n,0), sz(n,0), cur_pos(0), base(n,LLONG_MIN/4), st(n) {}
40
41	void add_edge(int u,int v,long long w){
42	int id = (int)edges.size();
43	edges.push_back({u,v,w});
44	g[u].push_back({v,id}); g[v].push_back({u,id});
45	}
46
47	int dfs(int u,int p){
48	parent[u]=p; sz[u]=1; int mx=0;
49	for(auto [v,id]: g[u]) if(v!=p){
50	depth[v]=depth[u]+1; dfs(v,u); sz[u]+=sz[v];
51	if(sz[v]>mx){mx=sz[v]; heavy[u]=v;}
52	}
53	return sz[u];
54	}
55
56	void decompose(int u,int h){
57	head[u]=h; pos[u]=cur_pos++;
58	if(heavy[u]!=-1) decompose(heavy[u],h);
59	for(auto [v,id]: g[u]) if(v!=parent[u] && v!=heavy[u]) decompose(v,v);
60	}
61
62	void build(int root){
63	dfs(root,-1); cur_pos=0; decompose(root,root);
64	// place edge weights at deeper endpoint
65	for(auto &e: edges){
66	int a=e.u, b=e.v; long long w=e.w;
67	int child = (parent[a]==b? a : b);
68	// root has no incoming edge; keep NEG_INF as identity for max
69	base[pos[child]] = w;
70	}
71	st = SegTreeMax(n); st.build(base);
72	}
73
74	// update edge by id to new weight
75	void update_edge(int id, long long w){
76	auto &e = edges[id]; e.w = w;
77	int child = (parent[e.u]==e.v? e.u : e.v);
78	st.point_set(pos[child], w);
79	}
80
81	long long path_max(int u,int v){
82	const long long NEG_INF = LLONG_MIN/4;
83	long long ans = NEG_INF;
84	while(head[u]!=head[v]){
85	if(depth[head[u]] < depth[head[v]]) swap(u,v);
86	// edges on this segment are [pos[head[u]], pos[u]] (all valid except possibly head[u] if it is root)
87	ans = max(ans, st.range_max(pos[head[u]], pos[u]));
88	u = parent[head[u]];
89	}
90	if(depth[u] < depth[v]) swap(u,v);
91	// same chain; exclude LCA's position for edge queries
92	// edges from v->...->u are stored at positions (pos[v]+1 .. pos[u])
93	ans = max(ans, st.range_max(pos[v]+1, pos[u]));
94	return ans;
95	}
96	};
97
98	int main(){
99	ios::sync_with_stdio(false); cin.tie(nullptr);
100
101	// Tree:
102	// 0-1(5), 1-2(1), 1-3(7), 3-4(3), 3-5(9), 5-6(2)
103	int n=7; HLD hld(n);
104	hld.add_edge(0,1,5); hld.add_edge(1,2,1); hld.add_edge(1,3,7);
105	hld.add_edge(3,4,3); hld.add_edge(3,5,9); hld.add_edge(5,6,2);
106	hld.build(0);
107
108	cout << "max edge on path(2,6) = " << hld.path_max(2,6) << "\n"; // expect max of edges 2-1-3-5-6 = max(1,7,9,2)=9
109	hld.update_edge(2, 0); // change edge (1,3) weight from 7 to 0 (edge id depends on insertion order)
110	cout << "after update, max edge on path(2,6) = " << hld.path_max(2,6) << "\n"; // now max is max(1,0,9,2)=9
111
112	return 0;
113	}
114

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	static const long long MOD = 1000000007LL;
5
6	struct Mat {
7	long long a[2][2];
8	Mat(long long diag = 1) { a[0][0]=a[1][1]=diag; a[0][1]=a[1][0]=0; }
9	static Mat from(long long a00,long long a01,long long a10,long long a11){ Mat m(0); m.a[0][0]=a00; m.a[0][1]=a01; m.a[1][0]=a10; m.a[1][1]=a11; return m; }
10	};
11
12	Mat mul(const Mat& x, const Mat& y){
13	Mat r(0);
14	for(int i=0;i<2;i++) for(int k=0;k<2;k++) for(int j=0;j<2;j++){
15	r.a[i][j] = (r.a[i][j] + x.a[i][k]*y.a[k][j]) % MOD;
16	}
17	return r;
18	}
19
20	struct SegNode { Mat fwd, bwd; }; // fwd: left->right product; bwd: right->left product
21
22	struct SegTreeMat {
23	int n; vector<SegNode> st;
24	SegTreeMat(){}
25	SegTreeMat(int n): n(n), st(4*n){}
26
27	static SegNode make_leaf(const Mat& m){ return {m, m}; }
28	static SegNode merge(const SegNode& L, const SegNode& R){
29	// array order: L segment then R segment
30	SegNode res;
31	res.fwd = mul(L.fwd, R.fwd); // left-to-right
32	res.bwd = mul(R.bwd, L.bwd); // right-to-left
33	return res;
34	}
35
36	void build(const vector<Mat>& a, int idx, int l, int r){
37	if(l==r){ st[idx] = make_leaf(a[l]); return; }
38	int m=(l+r)>>1; build(a,idx<<1,l,m); build(a,idx<<1\|1,m+1,r);
39	st[idx] = merge(st[idx<<1], st[idx<<1\|1]);
40	}
41	void build(const vector<Mat>& a){ build(a,1,0,n-1); }
42
43	void point_set(int idx,int l,int r,int p,const Mat& m){
44	if(l==r){ st[idx]=make_leaf(m); return; }
45	int mid=(l+r)>>1; if(p<=mid) point_set(idx<<1,l,mid,p,m); else point_set(idx<<1\|1,mid+1,r,p,m);
46	st[idx]=merge(st[idx<<1],st[idx<<1\|1]);
47	}
48	void point_set(int p,const Mat& m){ point_set(1,0,n-1,p,m); }
49
50	SegNode range_query(int idx,int l,int r,int ql,int qr){
51	if(ql==l && r==qr) return st[idx];
52	int m=(l+r)>>1;
53	if(qr<=m) return range_query(idx<<1,l,m,ql,qr);
54	if(ql>m) return range_query(idx<<1\|1,m+1,r,ql,qr);
55	SegNode L = range_query(idx<<1,l,m,ql,m);
56	SegNode R = range_query(idx<<1\|1,m+1,r,m+1,qr);
57	return merge(L,R);
58	}
59	SegNode range_query(int l,int r){ return range_query(1,0,n-1,l,r); }
60	};
61
62	struct HLD {
63	int n; vector<vector<int>> g;
64	vector<int> parent, depth, heavy, head, pos, sz;
65	int cur_pos; vector<Mat> base;
66	SegTreeMat st;
67
68	HLD(int n): n(n), g(n), parent(n,-1), depth(n,0), heavy(n,-1), head(n,0), pos(n,0), sz(n,0), cur_pos(0), base(n), st(n) {}
69
70	void add_edge(int u,int v){ g[u].push_back(v); g[v].push_back(u); }
71
72	int dfs(int u,int p){ parent[u]=p; sz[u]=1; int mx=0; for(int v: g[u]) if(v!=p){ depth[v]=depth[u]+1; dfs(v,u); sz[u]+=sz[v]; if(sz[v]>mx){mx=sz[v]; heavy[u]=v;} } return sz[u]; }
73
74	void decompose(int u,int h,const vector<Mat>& val){ head[u]=h; pos[u]=cur_pos; base[cur_pos]=val[u]; cur_pos++; if(heavy[u]!=-1) decompose(heavy[u],h,val); for(int v: g[u]) if(v!=parent[u] && v!=heavy[u]) decompose(v,v,val); }
75
76	void build(int root,const vector<Mat>& val){ dfs(root,-1); cur_pos=0; decompose(root,root,val); st=SegTreeMat(n); st.build(base); }
77
78	// Ordered product along path u -> v
79	Mat path_product(int u,int v){
80	Mat upRes(1); // identity
81	vector<Mat> downSegs; downSegs.reserve(20);
82	while(head[u]!=head[v]){
83	if(depth[head[u]] >= depth[head[v]]){
84	auto seg = st.range_query(pos[head[u]], pos[u]);
85	upRes = mul(upRes, seg.bwd); // going up: need right->left
86	u = parent[head[u]];
87	}else{
88	auto seg = st.range_query(pos[head[v]], pos[v]);
89	downSegs.push_back(seg.fwd); // will apply later in reverse chain order
90	v = parent[head[v]];
91	}
92	}
93	if(depth[u] >= depth[v]){
94	auto seg = st.range_query(pos[v], pos[u]);
95	upRes = mul(upRes, seg.bwd); // u up to v
96	}else{
97	auto seg = st.range_query(pos[u], pos[v]);
98	downSegs.push_back(seg.fwd); // v down from u
99	}
100	Mat res = upRes;
101	for(int i=(int)downSegs.size()-1;i>=0;--i) res = mul(res, downSegs[i]);
102	return res;
103	}
104
105	void point_set(int u, const Mat& m){ st.point_set(pos[u], m); }
106	};
107
108	int main(){
109	ios::sync_with_stdio(false); cin.tie(nullptr);
110
111	// Build a small tree and assign a 2x2 matrix to each node
112	int n=6; HLD hld(n);
113	hld.add_edge(0,1); hld.add_edge(1,2); hld.add_edge(1,3); hld.add_edge(3,4); hld.add_edge(3,5);
114
115	vector<Mat> val(n);
116	// arbitrary matrices
117	val[0]=Mat::from(1,2,3,4);
118	val[1]=Mat::from(2,0,1,2);
119	val[2]=Mat::from(0,1,1,0);
120	val[3]=Mat::from(3,1,4,1);
121	val[4]=Mat::from(1,0,0,1);
122	val[5]=Mat::from(2,2,2,2);
123
124	hld.build(0, val);
125
126	// Ordered product along path 2 -> 5: 2->1->3->5
127	Mat ans = hld.path_product(2,5);
128	cout << ans.a[0][0] << " " << ans.a[0][1] << "\n" << ans.a[1][0] << " " << ans.a[1][1] << "\n";
129
130	// Update node 3's matrix
131	hld.point_set(3, Mat::from(1,1,1,1));
132	ans = hld.path_product(2,5);
133	cout << ans.a[0][0] << " " << ans.a[0][1] << "\n" << ans.a[1][0] << " " << ans.a[1][1] << "\n";
134
135	return 0;
136	}
137