Tree-based Difference#
Description#
Place the difference array (not the prefix sum) on a tree, so that the weight of a certain node is equal to its own value plus the sum of the differences of all child nodes. (Incoherent)
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 a 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, which is the point after the interval.
Edge Difference#
Transfer the edge weight to the lower point.
Therefore, the mark of point L cannot be changed. So, for each interval increase by 1, the mark of point L should be decreased by 2.