Path Updates

Some problems ask you to add $x$ to all nodes on a path. Use a lazy propagation segment tree to handle range updates efficiently. During the path walk, instead of querying each chain segment, you update it with a range update operation. This still takes $O(\log n)$ segments times $O(\log n)$ per update, giving $O(\log^2 n)$ total.

The segment tree must support both range updates and range queries with lazy propagation. Without lazy propagation, range updates would take $O(n)$ time, defeating the purpose.

Space complexity is $O(n)$ for the data structures used.