Difference on Trees
Difference on Trees 1. Concept Tree difference means applying the difference-array technique to a tree structure instead of a linear array. It is almost always used together with LCA (lowest common ancestor). On an array, prefix sum and difference are inverse operations: prefix sum <----- inverse -----> difference On a tree, the analogue of “prefix sum” is the subtree sum: after all marks have been placed, the true value at node u equals the sum of the difference values over the whole subtree rooted at u. That aggregation is done with a single post-order DFS.
Read note →