Preprocess to Update-Query in Subtree

In this tutorial, we will learn how to preprocess a given tree to update a node and query in a subtree using a data structure like segment tree.

We know there are well known data-structures to update and query in subarray of an array. We can use all of them to query in a subtree. Let's see how we'll do that!

Problem Setup

Suppose we have a tree with 7 nodes and the tree looks like the following:

Example tree with 7 nodes showing the hierarchical structure

Let's assume there is a value written in every node. For example, the numbers are as following:

The Challenge

For example, a tree having node 2 as root is the subtree of the mentioned tree.

Subtree rooted at node 2, containing nodes 2, 5, and 6

So, for an example, if we want to get the maximum value among that subtree, we need to find the maximum value among the nodes 2, 6 and 5.

The Solution: DFS Preprocessing

But there is a solution! Let's traverse the tree by DFS fashion and write the traversal order on these nodes.

Tree with DFS traversal order marked on each node

Now back to the query part, the candidate nodes of the query are highlighted as follows:

Formula and Implementation

DFS Implementation:

How we can traverse the tree in DFS fashion and find subtree size:

int traversalOrder = 0;
int sz[Max];
int order[Max];
vector<int> adj[Max];

int dfs(int u) {
    order[u] = ++traversalOrder;
    sz[u] = 1;

    for(int v : adj[u]) {
        if (!order[v]) {
            sz[u] += dfs(v);
        }
    }
    return sz[u];
}

Range Query Function:

Getting traversal order range for a subtree:

pair<int, int> getRange(int root) {
    int rootTraversalOrder = order[root];
    int l = rootTraversalOrder;
    int r = rootTraversalOrder + sz[root] - 1;
    return {l, r};
}

Applications

Complexity Analysis

Key Takeaways