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 `i`th 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.
↵
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 `i`th 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.
