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 →Prefix Sum A prefix sum array p is a data structure that helps answer range sum queries efficiently. Given an input array a of length $n$, its prefix sum array p (also of length $n$) is defined as: $$ p[i] = a[0] + a[1] + \dots + a[i] = \sum_{k=0}^{i} a[k] $$ This means $p[i]$ stores the cumulative sum of all elements from the start of the array up to and including index $i$. For example, if:
Read note →Difference Arrays For an array $a$, the difference array $\mathrm{diff}$ is defined as: $$ \mathrm{diff}[i] = a[i] - a[i - 1], \quad \text{where } a[0] = 0. $$ Computing the prefix sums of the difference array restores the original array: $$ \mathrm{diff}[1] + \mathrm{diff}[2] + \dots + \mathrm{diff}[i] = a[1] + (a[2] - a[1]) + \dots + (a[i] - a[i - 1]) = a[i]. $$ To perform range addition on the original array (adding $x$ to all elements in the interval $[l, r]$), the operations on the difference array are: $$ \mathrm{diff}[l] \mathrel{+}= x, \quad \mathrm{diff}[r + 1] \mathrel{-}= x. $$ Two-dimensional Difference Arrays $$ \mathrm{diff}_{i, j} = a_{i, j} - a_{i - 1, j} - a_{i, j - 1} + a_{i - 1, j - 1} $$ To perform range addition between $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$, do
Read note →