Medium · Euler Tour Flattening
Understand → Visualise → Practice.
A rooted tree is given by values and parents. Return the sum of every queried node's subtree.
In DFS order, each subtree occupies a contiguous block of positions. With prefix sums over that order, a subtree sum is one subtraction.
Run DFS from the root; give each node a position tin and note tout, the position after its last descendant.
Lay the values out in DFS order and build prefix sums.
The subtree sum of v is prefix[tout[v]] − prefix[tin[v]].
O(n + q) time and O(n) space.
Recomputing each subtree by recursion per query is O(n) per query.
Read the full guide first: Fenwick Trees and Segment Trees.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.