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 nodes numbered 1 to , rooted at node 1, and every node holds a value. Then come queries of two kinds: 1 s x sets the value of node to , and 2 s asks for the sum of the values in the subtree of , which is together with every node below it.
The input gives and , then the values, then the edges as pairs of nodes, then the queries. Print the answer to every query of the second kind.
Constraints
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 . The second query sets node 5 to 3, and the last one asks about node 3 again: .
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 simple steps a second, all the queries together take:
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 and changes one value in . 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.
Write the vertices in depth-first order
Let's work with a slightly larger tree, parents = [-1, 0, 0, 1, 2, 1, 2, 5], where entry is the parent of vertex and -1 marks the root, vertex 0. Here the vertex numbers do not keep subtrees together: the subtree of vertex 1 is , four numbers spread across 0 to 7, with 2, 4 and 6 from another subtree between them.
The order in which a depth-first search visits the vertices keeps every subtree together. Once the search enters a vertex, it finishes everything below that vertex before it moves on to a sibling. Suppose we keep a list order and append each vertex when the search enters it. Then between entering and leaving it, the search writes exactly the subtree of , in one block of order. This list is the Euler tour, and two numbers per vertex, tin and tout (for time in and time out), mark where each block starts and ends.
Definition
When the search enters , tin[v] is the length of order just before is appended, which is the position of . When the search leaves , after every child has finished, tout[v] is the length of order at that moment, the first position past the subtree of .
The subtree of is then the half-open interval of positions from tin[v] up to tout[v] - 1, with the right end excluded:
A leaf covers one position, and the root covers .
Walk the example tree
Let's run the search on the example from the root. At each vertex it visits the children in increasing order. It enters 0, 1 and 3. Vertex 3 has no children, so the search leaves it with three vertices written: tout[3] = 3. Back at 1, it enters 5 and then 7, and leaves 7, 5 and 1 with five vertices written, so all three get tout = 5. It then enters 2 and 4, leaves 4 at length 7, enters 6, and leaves 6, 2 and 0 with all eight written. The array is order = [0, 1, 3, 5, 7, 2, 4, 6].
Each subtree as a half-open interval
| Vertex | tin | tout | Positions | Subtree in order |
|---|---|---|---|---|
| 0 | 0 | 8 | [0, 8) | 0, 1, 3, 5, 7, 2, 4, 6 |
| 1 | 1 | 5 | [1, 5) | 1, 3, 5, 7 |
| 2 | 5 | 8 | [5, 8) | 2, 4, 6 |
| 3 | 2 | 3 | [2, 3) | 3 |
| 4 | 6 | 7 | [6, 7) | 4 |
| 5 | 3 | 5 | [3, 5) | 5, 7 |
| 6 | 7 | 8 | [7, 8) | 6 |
| 7 | 4 | 5 | [4, 5) | 7 |
[1, 5) means positions 1, 2, 3 and 4. Subtree 5 sits at positions 3 and 4, inside the range of subtree 1, because vertex 5 is below vertex 1.
Why each subtree is one range
Call a vertex open from when the search enters it until it leaves. The search enters a vertex only while at its parent, and leaves it only after leaving all its children, so the open vertices always form the path from the root to the vertex the search is at.
While is open, it lies on that path, so every vertex entered in that time is below , and closes only after every vertex below it has closed. So positions tin[v] to tout[v] - 1 hold the subtree of and nothing else. In the example, the search reaches vertex 2 only after leaving vertex 1, so subtree 1 fills positions 1 to 4 and vertex 2 starts at position 5.
Recall Would breadth-first order make subtrees consecutive?
No. Breadth-first order writes the tree level by level, so on the example it is [0, 1, 2, 3, 5, 4, 6, 7], and vertex 2 lands between vertex 1 and the vertices below 1. Depth-first order may visit siblings in any order without splitting a subtree.
Step through the tour
The widget runs the same search one step at a time. Each vertex is written into the next free position when the search enters it and gets its tout when the search leaves it, which happens only after every vertex below it has one.
Pick a vertex to see its subtree light up in the tree and in the array as one unbroken range, along with the subtree's sum, which a later part computes from two prefix sums. Adding to one vertex's value changes one position of the array and every prefix sum after it.
Build the tour with an explicit stack
The function takes a parent array like the example's, with exactly one -1 for the root, and returns order, tin and tout.
The search keeps its own stack instead of calling itself recursively. A tree can be one chain of 200,000 vertices, which a recursive search would enter as 200,000 nested calls, and by default Python stops any program that nests more than about 1,000. Each vertex goes on the stack twice: once to enter it, and once, underneath its children, as an exit marker. The exit marker of comes off only after every other vertex of its subtree, when len(order) is the first position past the subtree, so it sits on the stack exactly while is open. Children are pushed in reverse so the smallest comes off first.
def euler_tour(parents):
n = len(parents)
children = [[] for _ in range(n)]
root = parents.index(-1)
for v, p in enumerate(parents):
if p != -1:
children[p].append(v)
order, tin, tout = [], [0] * n, [0] * n
stack = [(root, False)]
while stack:
v, finished = stack.pop()
if finished:
tout[v] = len(order)
continue
tin[v] = len(order)
order.append(v)
stack.append((v, True))
for child in reversed(children[v]):
stack.append((child, False))
return order, tin, toutPython details
Unpack the result with order, tin, tout = euler_tour(parents). Store the values in tour order with flat = [values[v] for v in order].
On the example this returns the order, tin and tout from the table above. Building the child lists and handling two stack records per vertex takes time and space.
Sum a subtree with prefix sums
Now let's use the tour for sums. We write each vertex's value at its position, so position holds values[order[i]]. On the example the values are [7, 3, 4, 2, 5, 1, 6, 2] by vertex, so the array in tour order is [7, 3, 2, 1, 2, 4, 5, 6]. Its prefix sums are [0, 7, 10, 12, 13, 15, 19, 24, 30], where entry is the total of positions 0 to . The sum of a subtree is then the difference of two of them:
Subtree 1 is the range and subtree 2 is , so
The first is the values 3, 2, 1 and 2 of vertices 1, 3, 5 and 7. After one search and one pass for the prefix sums, every subtree sum costs two lookups, compared with one visit per vertex for walking the subtree.
Subtree interval invariant
The subtree of is exactly the vertices at positions tin[v] to tout[v] - 1 of order.
It follows that two subtree intervals are either nested or disjoint, never partly overlapping, because one subtree contains the other or they share no vertex. It also gives an ancestry test. A vertex is an ancestor of , or itself, exactly when 's position lies in 's interval:
We will use that test later in this lesson, to check a whole set of vertices against one path.
Worked example
Trace the tour and the subtree sums
The trace runs the search on the example, records tin and tout, and subtracts prefix sums for every subtree. Two presets show the extreme shapes: on a chain of four vertices every range ends at the end of the array, and on a star, a root with three children, each child is a range of length 1.
Enter 0 at index 0. Record it before its children.
Change the example input
Current result: [30,8,15,2,5,3,6,2]
Keep subtree sums under changes with a Fenwick tree
Let's return to Subtree Queries. Prefix sums answer each question with two lookups, but this problem also changes values, and one changed value changes every prefix sum after its position. Rebuilding them after each change costs , so 200,000 changes on the chain of 200,000 nodes cost the same steps as walking it.
A Fenwick tree keeps the prefix sums of an array whose values change, with two operations of each: add adds a number at one position, and prefix(i) returns the sum of positions 1 to . How it reaches is the subject of the Fenwick trees lesson; this program uses only the two operations, and the listing below includes both. A Fenwick tree numbers its positions from 1, so position of the tour is index .
We load each node's value at index tin[v] + 1. Setting node to adds x - value[s] there. A question about covers tour positions tin[s] to tout[s] - 1, which are indices tin[s] + 1 to tout[s], so its answer is
The input lists edges rather than parents, so flatten works out the parents as it walks down from node 1: every neighbor of except its parent is a child of . It also records depths, which the ancestry test below needs.
Point changes and subtree sums in full
def flatten(n, adj):
tin, tout = [0] * (n + 1), [0] * (n + 1)
parent, depth = [0] * (n + 1), [0] * (n + 1)
timer = 0
stack = [(1, False)]
while stack:
v, finished = stack.pop()
if finished:
tout[v] = timer
continue
tin[v] = timer
timer += 1
stack.append((v, True))
for u in reversed(adj[v]):
if u != parent[v]:
parent[u] = v
depth[u] = depth[v] + 1
stack.append((u, False))
return tin, tout, parent, depth
def add(tree, i, delta):
while i < len(tree):
tree[i] += delta
i += i & -i
def prefix(tree, i):
total = 0
while i > 0:
total += tree[i]
i -= i & -i
return total
def main():
it = iter(map(int, sys.stdin.buffer.read().split()))
n, q = next(it), next(it)
value = [0] + [next(it) for _ in range(n)]
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
a, b = next(it), next(it)
adj[a].append(b)
adj[b].append(a)
tin, tout, _, _ = flatten(n, adj)
tree = [0] * (n + 1)
for v in range(1, n + 1):
add(tree, tin[v] + 1, value[v])
out = []
for _ in range(q):
if next(it) == 1:
s, x = next(it), next(it)
add(tree, tin[s] + 1, x - value[s])
value[s] = x
else:
s = next(it)
out.append(prefix(tree, tout[s]) - prefix(tree, tin[s]))
print("\n".join(map(str, out)))
main()On the official sample the program prints 8 and 10.
On the sample, flatten enters the nodes in the order 1, 2, 3, 4, 5, so node 3 has tin = 2 and tout = 5, and its subtree is positions 2 to 4. Loading the values and answering the queries cost each, so the whole input takes . With , that is about
Sum the path from the root
The input, the tree and the change query 1 s x are as in Subtree Queries, but 2 s asks for the sum of the values on the path from the root to node .
Constraints
Sample · Input
5 3 4 2 5 2 1 1 2 1 3 3 4 3 5 2 4 1 3 2 2 4
Output
11 8
Let's check the sample first. It uses the same tree and values as Subtree Queries, and the question 2 4 covers nodes 1, 3 and 4: . After 1 3 2 sets node 3 to 2, the same question prints .
A path from the root is not a range of the tour: on the sample, the path 1, 3, 4 sits at positions 0, 2 and 3, with node 2 at position 1 between them. So let's turn the question around. Instead of asking which values lie on the path to , we ask which path sums include a given value.
The value of a node belongs to the path sum of exactly the nodes in its subtree, because those are the nodes whose path from the root passes through it. So we add each value to its whole subtree range and read a single position: the number at position tin[s] collects the values of every node whose range covers it, which are the nodes on the path from the root to .
Adding to every position of a range takes only two updates if, instead of the numbers themselves, we store the difference between each number and the one before it: add at and subtract at . The number at position is then the sum of the stored entries up to . That sum includes the when and the when , so counts exactly for . The stored array is called a difference array, and the Fenwick tree holds it, so reading position is one prefix sum. A change to node adds x - value[s] over its range.
Range additions and point reads in full
flatten, add and prefix are the same as in Subtree Queries. Only main changes.
def flatten(n, adj):
tin, tout = [0] * (n + 1), [0] * (n + 1)
parent, depth = [0] * (n + 1), [0] * (n + 1)
timer = 0
stack = [(1, False)]
while stack:
v, finished = stack.pop()
if finished:
tout[v] = timer
continue
tin[v] = timer
timer += 1
stack.append((v, True))
for u in reversed(adj[v]):
if u != parent[v]:
parent[u] = v
depth[u] = depth[v] + 1
stack.append((u, False))
return tin, tout, parent, depth
def add(tree, i, delta):
while i < len(tree):
tree[i] += delta
i += i & -i
def prefix(tree, i):
total = 0
while i > 0:
total += tree[i]
i -= i & -i
return total
def main():
it = iter(map(int, sys.stdin.buffer.read().split()))
n, q = next(it), next(it)
value = [0] + [next(it) for _ in range(n)]
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
a, b = next(it), next(it)
adj[a].append(b)
adj[b].append(a)
tin, tout, _, _ = flatten(n, adj)
tree = [0] * (n + 2)
def add_to_subtree(v, delta):
add(tree, tin[v] + 1, delta)
add(tree, tout[v] + 1, -delta)
for v in range(1, n + 1):
add_to_subtree(v, value[v])
out = []
for _ in range(q):
if next(it) == 1:
s, x = next(it), next(it)
add_to_subtree(s, x - value[s])
value[s] = x
else:
s = next(it)
out.append(prefix(tree, tin[s] + 1))
print("\n".join(map(str, out)))
main()On the official sample the program prints 11 and 8.
On the sample, node 3's value is added to positions 2 to 4, the range of nodes 3, 4 and 5. Node 4 sits at position 3, which the ranges of nodes 1, 3 and 4 cover, so the prefix up to it is . The tree has cells because tout[v] can be , which puts the subtraction at index .
Test whether one vertex is above another
You get a tree of vertices rooted at vertex 1 and queries. Each query is a set of distinct vertices. For each set, print YES if there is a path from the root down to some vertex such that every vertex of the set is on the path or one edge away from a vertex on it, and NO otherwise.
The input gives and , then the edges, then one line per query: followed by the vertices.
Constraints
- The set sizes add up to at most
Sample · Input
10 6 1 2 1 3 1 4 2 5 2 6 3 7 7 8 7 9 9 10 4 3 8 9 10 3 2 4 6 3 2 1 5 3 4 8 2 2 6 10 3 5 4 7
Output
YES YES YES YES NO NO
Let's check two of the sets by hand. For the first, , the path 1, 3, 7, 9, 10 contains 3, 9 and 10, and 8 hangs off vertex 7, so the answer is YES. For the fifth set, , a path that covers 10 must reach vertex 9, which means going through 3 and 7, and then neither 6 nor its parent 2 is on it, so the answer is NO.
To test a set without trying every path, we look at parents: a vertex is on the path or one edge away exactly when its parent is on the path. A path that starts at the root and contains also contains 's parent, and if a neighbor of is on the path without , that neighbor is 's parent, because a child of on the path would bring with it. The root has no parent, so we let it count as its own parent. So we replace every vertex of the set by its parent and ask whether the parents all lie on one path from the root.
The path to test against is the one from the root to , the deepest vertex of the set: the parents lie on one path from the root exactly when each of them is or an ancestor of . The subtree interval invariant turns each check into two comparisons instead of a walk up from :
Deeper read: why testing against the deepest vertex is enough
If every parent is an ancestor of (or itself), the path from the root to contains all of them, so the answer is YES.
For the other direction, suppose the parents all lie on one path from the root. Any two of them are then ancestor and descendant. Let be the parent of . Every other parent is the parent of a vertex no deeper than , so is no deeper than . Of two vertices on one path from the root, the one that is no deeper is an ancestor of the other or the same vertex, so is or an ancestor of , and in both cases an ancestor of . A set whose deepest vertex is not unique works the same way: pick any deepest one.
Ancestor checks on a set of vertices in full
flatten is the same as in Subtree Queries. Setting parent[1] = 1 makes the root its own parent, as the test above assumes.
def flatten(n, adj):
tin, tout = [0] * (n + 1), [0] * (n + 1)
parent, depth = [0] * (n + 1), [0] * (n + 1)
timer = 0
stack = [(1, False)]
while stack:
v, finished = stack.pop()
if finished:
tout[v] = timer
continue
tin[v] = timer
timer += 1
stack.append((v, True))
for u in reversed(adj[v]):
if u != parent[v]:
parent[u] = v
depth[u] = depth[v] + 1
stack.append((u, False))
return tin, tout, parent, depth
def main():
it = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(it), next(it)
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
a, b = next(it), next(it)
adj[a].append(b)
adj[b].append(a)
tin, tout, parent, depth = flatten(n, adj)
parent[1] = 1
out = []
for _ in range(m):
k = next(it)
vertices = [next(it) for _ in range(k)]
u = max(vertices, key=lambda v: depth[v])
fits = all(tin[parent[v]] <= tin[u] < tout[parent[v]] for v in vertices)
out.append("YES" if fits else "NO")
print("\n".join(out))
main()On the official sample the program prints YES, YES, YES, YES, NO and NO.
On the sample, the set tests vertex 10, at tin = 8, against the range of vertex 2 and fails. Each set costs after the search, so the whole input takes .
Rebuild the tour when the tree changes shape
The intervals depend on the root and the edges, not on the values. Changing a value leaves them as they are and is a point update, as in Subtree Queries. Changing the tree itself is different: moving a subtree under a new parent can shift the positions of many vertices at once, so we rebuild the tour. A new root changes which vertices form a subtree: if the example tree is rooted at vertex 1 instead of vertex 0, the subtree of 1 is the whole tree, so that needs a new search too.
Deeper read: the longer tour and where the name comes from
In graph theory an Euler tour is a walk that uses every edge exactly once. If we replace each tree edge with two directed edges, one down and one up, the depth-first search walks every one of them once: down into a child, back up to the parent. Writing a vertex every time the walk arrives at it gives entries. On the example tree that is [0, 1, 3, 1, 5, 7, 5, 1, 0, 2, 4, 2, 6, 2, 0], 15 entries for 8 vertices.
This longer tour answers a different question, the lowest common ancestor of two vertices: the deepest vertex that is an ancestor of both. Between the first appearances of and , the walk climbs no higher than their lowest common ancestor and passes through it, so the answer is the shallowest vertex in that stretch. For 3 and 7, the first appearances are at positions 2 and 5, the stretch is 3, 1, 5, 7, and the shallowest is 1.
A sparse table over the depths, which stores the shallowest vertex of every stretch whose length is a power of two, answers each such question in after preparation: any stretch is covered by two of those stretches that overlap, so a question takes two lookups. Binary lifting, which stores the ancestors of each vertex at distances 1, 2, 4, 8 and so on, finds the same ancestor without the longer tour.
How long the tour and each query take
- Build the tour
time - One search enters and leaves each vertex once.
- Subtree Queries and Path Queries
per query - A Fenwick tree: one or two updates per change, one or two prefix sums per question.
- Extra space
order,tin,toutand the Fenwick tree each hold one entry per vertex.
Common Euler tour mistakes
Building prefix sums over
valuesin vertex order instead of tour order.- Where it breaks
- On the example, subtree 1 becomes
prefix[5] - prefix[1]over[7, 3, 4, 2, 5, 1, 6, 2]: instead of . Positions in the tour are not vertex numbers. - The fix
- Put
values[order[i]]at position first, then build the prefix sums.
Treating
tout[v]as the last position of the subtree and summing up to it inclusive.- Where it breaks
- Vertex 4 has
tin = 6andtout = 7. Summing positions 6 and 7 adds vertex 6 too: instead of . - The fix
- Keep the range half-open: the sum is
prefix[tout[v]] - prefix[tin[v]].
Updating position
vinstead of positiontin[v].- Where it breaks
- Adding 4 to vertex 7 at position 7 lands in vertex 6's slot. Subtree 2 grows to and subtree 1 stays at , when they should be and .
- The fix
- Turn every vertex number into a position with
tinfirst.
Recording
toutwhen the search enters a vertex, right after appending it and before the loop over its children.- Where it breaks
- Every range has length 1: subtree 1 becomes
[1, 2), which holds vertex 1 alone, and its sum comes out as instead of . - The fix
- Record
tout[v]after every child of has finished.
Recall On the example, vertex 5 has tin = 3 and tout = 5. Which of vertices 7 and 4 lie in its subtree?
Vertex 7 has tin = 4, inside , so it is in the subtree. Vertex 4 has tin = 6, outside it, so it is not.
Key terms
| Term | Meaning |
|---|---|
| subtree | A vertex together with every vertex below it. |
| Euler tour | The vertices in the order a depth-first search enters them; every subtree is one block of it. |
| tin, tout | The position of a vertex in the tour, and the first position past its subtree. |
| half-open interval | : the positions from up to . |
Further reading
- USACO Guide, Gold(Optional) Euler Tour Technique(opens in a new tab)
Flattens a tree with entry and exit times and solves Subtree Queries with a range-sum structure.
- Antti Laaksonen, chapter 18 (PDF)Competitive Programmer’s Handbook(opens in a new tab)
Section 18.2 builds the tree traversal array and answers subtree and path queries with it. Section 18.3 writes a vertex on every visit, the longer tour, to find lowest common ancestors.
- cp-algorithmsLowest Common Ancestor - O(√N) and O(log N) with O(N) preprocessing(opens in a new tab)
Finds the LCA as the shallowest vertex between two positions of the longer tour.
- Jeff Erickson (PDF)Algorithms, Chapter 6: Depth-first search(opens in a new tab)
Section 6.1 gives every vertex a starting and a finishing time from one clock, and shows that two vertices' intervals are nested when one is an ancestor of the other and disjoint otherwise. Parts of this page adapt this chapter’s text, licensed CC BY 4.0 (creativecommons.org/licenses/by/4.0), with changed wording, examples and code.
- OI Wiki, in ChineseDFS(图论)(opens in a new tab)
Its DFS 序列 section is the entry order used here, with each subtree as one contiguous block; the 括号序列 section records an entry and an exit for every vertex.