Skip to content

Subtree Queries via Flattening

Subtree maps to a contiguous range in the flat array, enabling BIT range queries

The Problem

You have a rooted tree with \(n\) nodes, each holding a value \(w[v]\). You need to support two operations:

  1. Update: change the value of node \(v\) to \(x\).
  2. Query: return the sum of all values in the subtree rooted at \(v\).

Up to \(q = 2 \times 10^5\) operations, \(n \leq 2 \times 10^5\).

A naive approach recomputes each subtree sum by DFS — \(O(n)\) per query, \(O(nq)\) total. That's \(4 \times 10^{10}\) operations. Not happening.

The Reduction: Flatten the tree into an array using DFS ordering. Every subtree becomes a contiguous range. Subtree sum becomes range sum. Use a Binary Indexed Tree (BIT) for \(O(\log n)\) per operation.

The Setup: From Tree to Array

From the previous lesson, you know that a DFS ordering assigns each node a position \(tin[v]\) such that the subtree of \(v\) occupies positions \([tin[v], tout[v]]\) as a contiguous block.

Build a flat array \(A\) where \(A[tin[v]] = w[v]\). Now:

  • Subtree sum of \(v\) = sum of \(A[tin[v] \ldots tout[v]]\) = a range sum query.
  • Update node \(v\) = change \(A[tin[v]]\) = a point update.

Range sum with point updates? That's exactly what a BIT (Fenwick tree) or segment tree does in \(O(\log n)\) per operation.

We use BIT/segment tree as a black box here. If you haven't seen them, all you need to know: a BIT supports point update and prefix sum, each in \(O(\log n)\). Range sum \([l, r]\) = \(prefixSum(r) - prefixSum(l-1)\).

Trace: 7-Node Tree

Same tree as last lesson, now with values:

         1 (w=3)
       / | \
      2  3  4
    (w=5)(w=2)(w=7)
     / \    |
    5   6   7
  (w=1)(w=4)(w=6)

Step 1: Compute DFS ordering (timer starts at 1 here for 1-indexed BIT):

Node tin tout Value
1 1 7 3
2 2 4 5
5 3 3 1
6 4 4 4
3 5 5 2
4 6 7 7
7 7 7 6

Step 2: Build flat array \(A\):

Position 1 2 3 4 5 6 7
Node 1 2 5 6 3 4 7
Value 3 5 1 4 2 7 6

Step 3: Build BIT on this array (just insert each value with a point update).

Answering Queries

Query: subtree sum of node 2.

Subtree of 2 occupies \([tin[2], tout[2]] = [2, 4]\).

\(\text{sum}(2, 4) = prefixSum(4) - prefixSum(1) = (3+5+1+4) - (3) = 10\).

Manual check: subtree of 2 contains nodes {2, 5, 6} with values {5, 1, 4}. Sum = 10. Correct.

Query: subtree sum of node 4.

\([tin[4], tout[4]] = [6, 7]\).

\(\text{sum}(6, 7) = prefixSum(7) - prefixSum(5) = 28 - 15 = 13\).

Manual check: subtree of 4 = {4, 7}, values {7, 6}. Sum = 13. Correct.

Query: subtree sum of node 1 (entire tree).

\([1, 7]\). \(prefixSum(7) = 3+5+1+4+2+7+6 = 28\). Correct — that's the sum of all values.

Update: change value of node 5 from 1 to 10.

Point update at position \(tin[5] = 3\): add \(10 - 1 = 9\) to position 3 in the BIT.

Now the flat array is: \([3, 5, 10, 4, 2, 7, 6]\).

Query: subtree sum of node 2 after the update.

\(\text{sum}(2, 4) = prefixSum(4) - prefixSum(1) = (3+5+10+4) - (3) = 19\).

Manual check: {5, 10, 4}. Sum = 19. Correct.

Beyond Sum: Any Aggregate

The same flattening works for any associative operation:

  • Subtree min/max: use a segment tree instead of BIT (segment trees handle min/max; BIT handles only sum).
  • Subtree count of nodes with value > x: use a merge sort tree or persistent segment tree on the flat array.
  • Subtree XOR: BIT works, since XOR is associative and has an inverse.

The pattern is always the same: flatten, then apply the right array data structure.

The Code

int timer = 0;
vector<int> adjacency[200005];
int entryTime[200005], exitTime[200005];
long long nodeValue[200005];
long long bit[200005];
int numNodes, numQueries;

void dfs(int node, int parent) {
    entryTime[node] = ++timer;
    for (int child : adjacency[node]) {
        if (child != parent) {
            dfs(child, node);
        }
    }
    exitTime[node] = timer;
}

void update(int position, long long delta) {
    for (; position <= numNodes; position += position & (-position))
        bit[position] += delta;
}

long long prefixSum(int position) {
    long long total = 0;
    for (; position > 0; position -= position & (-position))
        total += bit[position];
    return total;
}

long long subtreeSum(int node) {
    return prefixSum(exitTime[node]) - prefixSum(entryTime[node] - 1);
}

Complexity: \(O(n \log n)\) preprocessing, \(O(\log n)\) per update or query.

What You Just Did

You reduced a tree problem to an array problem. That's the entire technique:

  1. Flatten (DFS ordering).
  2. Map tree operations to array operations (subtree → range, node update → point update).
  3. Use an off-the-shelf array data structure (BIT, segment tree).

This is a reduction in the formal sense. You didn't invent a new tree data structure — you mapped to a solved problem. The ability to spot these reductions is what separates competitive programmers who struggle with tree problems from those who solve them in minutes.

Try It

Predict before running: If every node has value 1, what does the subtree sum of node \(v\) return? It returns the number of nodes in the subtree of \(v\) — the subtree size.

Challenge: How would you handle "find the minimum value in the subtree of \(v\)"? You can't use a BIT for min queries (BIT requires an inverse operation). Use a segment tree on the flat array with range minimum query.

Challenge 2: What if the tree is not rooted? Pick any node as root (typically node 1), run DFS, and the same technique works. The choice of root affects which subtrees you can query, but the flattening still produces contiguous segments.

Edge Cases to Watch For

  • Negative values and large updates: The BIT stores cumulative sums; if values swing between large positive and negative, intermediate sums can overflow int. Use long long for the BIT array.
  • Off-by-one in the flat range: Whether the subtree range is \([tin[v], tout[v]]\) or \([tin[v], tout[v])\) depends on your DFS convention (inclusive vs exclusive tout). Getting this wrong includes a neighbor's subtree or excludes the node itself.

For the Curious — What IS a Segment Tree? We use segment trees as a black box here — a data structure supporting range queries and point updates in \(O(\log n)\). But a segment tree is itself a binary tree built over an array: the root covers range \([0, n)\), the left child covers \([0, n/2)\), the right covers \([n/2, n)\), recursively. Each internal node stores the aggregate (sum, min, max) of its range. The node at position \(x\) has children at \(2x\) and \(2x+1\) — the same implicit tree structure as a binary heap. An array of size \(n\) needs a segment tree of size \(\sim 2n\).

Problems

Problem Link Difficulty
CSES — Subtree Queries cses.fi/problemset/task/1137 Medium
CSES — Path Queries cses.fi/problemset/task/1138 Medium
CF 620E — New Year Tree codeforces.com/problemset/problem/620/E Hard