Path Updates with the 4-Point Trick
Adding x to the path u..v is four point updates once you know the LCA ā and reading a node is a subtree sum. Derivation, proof, and the classic off-by-one.
Path add, point get
Store point updates in a BIT at tin positions. Define the value of w as
the subtree sum of w over the BIT:
val(w) = prefix(tout[w]) - prefix(tin[w] - 1).
Why this reading works: the subtree of w contains exactly the tin
positions of nodes below w, so the reading sums every stored point inside
w's subtree.
The update ā add x on path u..v, l = LCA(u, v):
upd(tin[u], x); upd(tin[v], x);
upd(tin[l], -x);
if (parent(l)) upd(tin[parent(l)], -x);
Proof sketch: val(w) counts stored points in subtree(w). A node z's stored point is seen by w iff z is inside subtree(w) iff w is an ancestor of z (inclusive). So val(w) = xĀ·[w anc of u] + xĀ·[w anc of v] ā xĀ·[w anc of l] ā xĀ·[w anc of parent(l)]. For w on the path (w ā l): exactly one of u, v lies in subtree(w), l and parent(l) do not ā x. For w = l: both u and v count, l cancels one ā x. For w above l: two pluses and two minuses ā 0. For w outside: 0.
The off-by-one that kills implementations: using prefix(tin[w]) instead
of the two-sided subtree read ā that sums ROOT-side ancestors instead of
the subtree, and fails on any non-chain tree.