2010. Totals for a Subtree While Values Change
A tree with n nodes is given, rooted at node 1, and each node holds a value.
Then q operations arrive:
set i x replace the value at node i with x
sub i print the total of every value in the subtree rooted at i,
including node i itself
``` values: 1 2 3 4 5 edges: 1-2 1-3 2-4 2-5
sub 1 -> 15 the whole tree sub 2 -> 11 nodes 2, 4 and 5 set 4 100 sub 2 -> 107 ```
## What most people try first
Walk the subtree and add. A set is free and a sub costs the size of the
subtree, so 2 * 10^5 queries on the root of a tree with 2 * 10^5 nodes is
4 * 10^10 steps.
Caching each subtree total is the obvious repair and it is worse than it looks:
changing one value invalidates the cached total of every ancestor, which on a
path is all n of them.
The real obstacle is that a subtree is not a contiguous piece of anything. The array machinery from problems 2001 and 2006 answers questions about a RANGE, and there is no range here to ask about.
## Flatten the tree so a subtree becomes a range
Walk the tree depth first and stamp each node with the time you enter it and the time you finish it:
tin[v] = the step on which v was entered
tout[v] = the last step used anywhere inside v's subtree
Because a depth-first walk finishes everything below a node before leaving it,
the nodes of v's subtree are exactly those whose entry time lies in
tin[v] .. tout[v], and they are CONSECUTIVE. The subtree has become a range.
Now place each node's value at index tin[v] of an array and put a Fenwick tree
over it, exactly as in problem 2001:
set i x: tree.add(tin[i], x - current[i]); current[i] = x
sub i: tree.pre(tout[i]) - tree.pre(tin[i] - 1)
## Why the interval is exactly the subtree
Two directions, and both matter.
Every node below v is entered after v and finished before v finishes, so
its entry time lies inside the interval. And a node NOT below v is either
entered before v, or entered after the walk has left v entirely, so its
entry time falls outside. Nothing else can happen, because a depth-first walk
cannot leave a subtree and return to it.
That last clause is the whole argument. It is a property of the traversal, not of the tree, which is why a breadth-first walk does not produce usable stamps.
## The update is a difference, not an assignment
set writes a value; the Fenwick tree only knows how to ADD. So add the
difference x - current[i] and keep current yourself. Adding x directly is
the classic wrong version: it leaves the old value in the total as well, and on
set 4 100 it reports 111 instead of 107.
## Overflow
2 * 10^5 values of 10^9 total 2 * 10^14, well past the 2147483647 a
signed 32 bit integer holds, so the totals need 64 bits. Individual values do
not; 10^9 fits, and so would 2 * 10^9.
## Cost
O(n) to flatten, O(log n) per operation, about 3.6 * 10^6 steps at the
limits. Build the tour ITERATIVELY: a path-shaped tree of 2 * 10^5 nodes
overflows the default recursion limit in Python and the default stack in several
of the others.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `-10^9 ≤ each value ≤ 10^9` - `1 ≤ i ≤ n` and `-10^9 ≤ x ≤ 10^9` - the `n - 1` edges always form a tree, rooted at node 1
Input
The first line contains two integers n and q.
The second line contains n integers: the starting value at node 1, then node 2, and so on.
Each of the next n - 1 lines contains two integers u and v, an edge of the tree.
Each of the next q lines is either set i x or sub i.
Output
Print one integer on its own line for every sub operation, in the order the operations arrive: the total of all values in that node's subtree, counting the node itself. A set prints nothing.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.