Trees and recursion 0/36

Lesson 6 of 6 Advanced

Euler tours: flattening a tree into an array

Number a tree in DFS entry order so each subtree is one array range, then answer subtree sums, root-path sums and ancestry tests with a Fenwick tree.

4,222 words · 19 min read

Part 1 of 11 Euler tour

Subtrees as ranges of an array

A question about a subtree can be answered by walking the subtree edge by edge, one step for each vertex in it. A question about a range of an array can be answered much faster: with prefix sums, the sum of any range is the difference of two stored numbers. This lesson writes the vertices of a tree into an array so that every subtree lands in one block of consecutive positions, an order called an Euler tour, and then answers questions about subtrees as questions about ranges. Let's start with a problem.

You get a tree of nn nodes numbered 1 to nn, rooted at node 1, and every node holds a value. Then come qq queries of two kinds: 1 s x sets the value of node ss to xx, and 2 s asks for the sum of the values in the subtree of ss, which is ss together with every node below it.

The input gives nn and qq, then the nn values, then the n−1n - 1 edges as pairs of nodes, then the queries. Print the answer to every query of the second kind.

Constraints

  • 1≤n,q≤2⋅1051 \le n, q \le 2 \cdot 10^5
  • 1≤a,b,s≤n1 \le a, b, s \le n
  • 1≤vi,x≤1091 \le v_i, x \le 10^9

Sample · Input

5 3
4 2 5 2 1
1 2
1 3
3 4
3 5
2 3
1 5 3
2 3

Output

8
10

Before writing any code, let's make sure we understand the sample. Node 1 has the children 2 and 3, and node 3 has the children 4 and 5. The subtree of node 3 is nodes 3, 4 and 5, so the first query prints 5+2+1=85 + 2 + 1 = 8. The second query sets node 5 to 3, and the last one asks about node 3 again: 5+2+3=105 + 2 + 3 = 10.

Our first idea might be to walk the subtree on every query and add up the values as we go. A walk takes one step per node in the subtree, so the worst case is a tree that is one long chain, with every query asking about node 1 at the top. Each walk then visits all 200,000 nodes, and at a judge's rough rate of 10810^8 simple steps a second, all the queries together take:

2×105 queries×2×105 steps=4×1010 steps4×1010÷108 steps a second≈400 seconds.\begin{aligned} 2 \times 10^5 \text{ queries} \times 2 \times 10^5 \text{ steps} &= 4 \times 10^{10} \text{ steps} \\ 4 \times 10^{10} \div 10^8 \text{ steps a second} &\approx 400 \text{ seconds.} \end{aligned}

The time limit is one second. The opposite approach stores every subtree's sum, so that each question is one lookup, and makes the changes expensive instead. A new value at a node changes the sum of every subtree that contains it: the subtree of the node itself and of every node above it. On the chain, a change at the bottom touches all 200,000 stored sums.

One structure built over an array handles both: a Fenwick tree reports the sum of a range in O(log⁡n)O(\log n) and changes one value in O(log⁡n)O(\log n). If every subtree sat in one block of an array, a subtree sum would be a range sum. The node numbers do not give that layout, so we have to choose the order ourselves.