Tree-based Difference#
Description#
Put the difference array (not prefix sum) on a tree, so that the weight of a certain node is equal to itself plus the sum of the differences of all its child nodes. (Incoherent language)
The purpose of the difference array is to reduce the time complexity of interval modifications. Applied to a tree, it can be used in situations like this:
Node Difference#
Increase the weight of all nodes on the simple path from A to B by 1.
This path can be split into two chains, from A to L (LCA of A and B) and from B to L.
By increasing the marks of A and B by 1, the values corresponding to A to L and B to L will both increase by 1 during calculation, while the value of L increases by a total of 2. Therefore, decrease the mark of L by 1. Similar to modifying the interval of a difference array, decrease the mark of the parent node of L.
Edge Difference#
Transfer the edge weight to the lower node.
Therefore, the mark of node L cannot be changed. So, for each interval increase by 1, the mark of node L should be decreased by 2.