I wanted to share standard but very handy trick, which allows to convert a range of problems with queries on sub-trees of a rooted tree to a problem of range queries on an array.

For example, if we have a tree with values on each vertex i: -10^9 <= x_i <= 10^9, and for queries we want to get a sum of all values in ith sub-tree, or to change the value in the given vertex to y. This is possible with online queries in O(qlogn) with this approach.

Now, to the conversion. First, we need to reindex the tree in a way, that would make all indices of every sub-tree form a continuous segment on integers. And there's a known classic way to do this: we should start pre-order DFS on a tree, which is simply a DFS with global timer t, where each time we enter a vertex v, we assign its new_id[v] = t, and increment the timer. As a quick proof, let's note that when we enter a vertex v we get the first accessible number and every v's child u (not necessarily direct child) is visited immediately after v and strictly before any proper ancestor of v. Which must mean that indices in a sub-tree of v form a continuous integer segment. This, of course, computes in O(n)

Alongside the tour, we should keep the sizes of each sub-tree, so that we could calculate which segment of indices corresponds to given vertex. It's easy to see, that for a vertex v its sub-tree segment is new_id[v] + sz[v] - 1.

Here's a code snippet for this process:

vector<vector<int>> g;
vector<int> sz, new_id;
int t = 0;

void reindex(int v, int p) {
    sz[v] = 1;
    new_id[v] = t++;
    for (auto u : g[v]) {
        if (u != p) {
            reindex(u, v);
            sz[v] += sz[u];
        }
    }
}

After this we can simply convert our tree to an array of values, that are assigned to vertices, where every value will be placed on a new index. That's it! There's a lot of structures, that allow further tinkering with such setup: block decomposition, segment tree, BIT, etc. For example, the problem described in the second paragraph can be solved with standard Fenwick Tree.

If you have any thoughts on how to expand this idea, or if you have some problems, that can be solved with this trick: tell me in the comments, it's very appreciated!

This article was lightly redacted to eliminate grammar/wording/styling mistakes with the ChatGPT o3 model.