Subtrees and paths
A tree traversal array contains the nodes of a rooted tree in the order in which a depth-first search from the root node visits them. For example, in the tree
a depth-first search proceeds as follows:
Hence, the corresponding tree traversal array is as follows:
Subtree queries
Each subtree of a tree corresponds to a subarray of the tree traversal array such that the first element of the subarray is the root node. For example, the following subarray contains the nodes of the subtree of node $4$:
Using this fact, we can efficiently process queries that are related to subtrees of a tree. As an example, consider a problem where each node is assigned a value, and our task is to support the following queries:
- update the value of a node
- calculate the sum of values in the subtree of a node
Consider the following tree where the blue numbers are the values of the nodes. For example, the sum of the subtree of node $4$ is $3+4+3+1=11$.
The idea is to construct a tree traversal array that contains three values for each node: the identifier of the node, the size of the subtree, and the value of the node. For example, the array for the above tree is as follows:
Using this array, we can calculate the sum of values in any subtree by first finding out the size of the subtree and then the values of the corresponding nodes. For example, the values in the subtree of node $4$ can be found as follows:
To answer the queries efficiently, it suffices to store the values of the nodes in a binary indexed or segment tree. After this, we can both update a value and calculate the sum of values in $O(\log n)$ time.
Path queries
Using a tree traversal array, we can also efficiently calculate sums of values on paths from the root node to any node of the tree. Consider a problem where our task is to support the following queries:
- change the value of a node
- calculate the sum of values on a path from the root to a node
For example, in the following tree, the sum of values from the root node to node 7 is $4+5+5=14$:
We can solve this problem like before, but now each value in the last row of the array is the sum of values on a path from the root to the node. For example, the following array corresponds to the above tree:
\begin{tikzpicture}[scale=0.7] \draw (0,1) grid (9,-2);
\node[left] at (-1,0.5) {node id}; \node[left] at (-1,-0.5) {subtree size}; \node[left] at (-1,-1.5) {path sum};
\node at (0.5,0.5) {1}; \node at (1.5,0.5) {2}; \node at (2.5,0.5) {6}; \node at (3.5,0.5) {3}; \node at (4.5,0.5) {4}; \node at (5.5,0.5) {7}; \node at (6.5,0.5) {8}; \node at (7.5,0.5) {9}; \node at (8.5,0.5) {5};
\node at (0.5,-0.5) {9}; \node at (1.5,-0.5) {2}; \node at (2.5,-0.5) {1}; \node at (3.5,-0.5) {1}; \node at (4.5,-0.5) {4}; \node at (5.5,-0.5) {1}; \node at (6.5,-0.5) {1}; \node at (7.5,-0.5) {1}; \node at (8.5,-0.5) {1};
\node at (0.5,-1.5) {4}; \node at (1.5,-1.5) {9}; \node at (2.5,-1.5) {12}; \node at (3.5,-1.5) {7}; \node at (4.5,-1.5) {9}; \node at (5.5,-1.5) {14}; \node at (6.5,-1.5) {12}; \node at (7.5,-1.5) {10}; \node at (8.5,-1.5) {6}; \end{tikzpicture}
When the value of a node increases by $x$, the sums of all nodes in its subtree increase by $x$. For example, if the value of node 4 increases by 1, the array changes as follows:
Thus, to support both the operations, we should be able to increase all values in a range and retrieve a single value. This can be done in $O(\log n)$ time using a binary indexed or segment tree (see Chapter 9.4).