First, consider the case where the input tree T is just a linear list – i.e. each node has at most one child. We can solve this case by building a segment tree S. Each leaf of S corresponds to one node of T, and the internal nodes of S correspond to longer intervals of nodes in T – from some node a to some node b.
Using this segment tree, we can quickly answer the given queries. When we need to update an interval [a, a + l] of nodes in T, we map this interval to O(logn) nodes of S which exactly cover the original interval in T. We store the “last modification time” (the query number) in these O(logn) nodes.
When we want to find the color of a particular node in T, we look at the O(logn) nodes in S which cover it and find the one with the most recent “last modification time”. This tells us which query was the last to update this node.
Let us extend this solution to arbitrary trees T. Now there can be multiple nodes on the same level (i.e. with the same distance to the root). Again, we will build a segment tree S. But this time, each leaf of S corresponds to a level in T, and each internal node corresponds to an interval of levels in T – from level a to level b.
In the linear list case, each leaf of S stored a single number. But now that each leaf of S corresponds to a whole level in T, which might contain more than one node, that won’t be enough. Instead, each leaf v of the segment tree S will contain a smaller nested segment tree Sv. The leaves of Sv will correspond to the individual nodes on this level of T. We can use this nested segment tree to quickly update multiple nodes of T which are on the same level.
What if we want to update multiple levels of T together? That’s where internal nodes of S come in. Consider an internal node v which manages levels a to b. When you look at only these levels of T and ignore all other nodes, the tree T falls apart into a number of subtrees1 – as many as there are nodes in level a. These subtrees of T are what will be managed by the nested segment tree Sv (which is stored in node v of segment tree S). So each leaf of Sv corresponds to one subtree, and each internal node of Sv corresponds to an interval of multiple subtrees.
This allows us to efficiently process queries on the tree T. When we need to update l levels of the subtree under a given vertex a, we split the affected area vertically into O(logn) segments that correspond to nodes of S, and in each segment, we just update some of the subtrees managed by Sv. Analogously, when we want to find the color of a node in T, we find all the nodes v in S which are relevant to it, and then we look in each of the relevant nodes of their nested segment trees, returning the color of the most recent query. This means every query can be completed in O(log2n) time.
Technically, these are not subtrees, because we cut off their descendants below level b. They’re vertex-induced subgraphs of the tree T. We call them subtrees for clarity’s sake.↩