O(n)-space, polylog-time subtree sums in incremental forests?

Question

Consider a forest $G$ of $n$ vertices $v_1, \dots, v_n$ arranged left to right with edges from child to parent always going to the left, i.e. if the parent of vertex $v_i$ is $v_j$, then $j < i$. Additionally, each vertex $v_i$ is associated with a value $f(v_i) \in \mathbb{N}$.

We are interested in computing subtree sums in the family of forests $G_0, \dots, G_n$ that arise when $G$ is built incrementally by adding the vertices in order $v_1, v_2, \dots, v_n$, i.e. $G_i$ has vertex set $V_i = \{v_1, \dots, v_i\}$ and the edges from $G$ that connect vertices in $V_i$.

The specific subtree sum query is the following: Given a vertex $v_i$ and forest $G_j$, what is the sum of vertex values in the subtree of $G_j$ rooted at $v_i$?

Is there a $O(n)$-space data structure that solves the subtree sum query in polylogarithmic query time?

In other words, $G_i$ is built from $G_{i-1}$ by adding vertex $v_i$, which is either a root (has no outgoing edge) or a non-root (has an edge to some vertex $v_j$ with $1 \le j < i$), and the problem can be considered as a static partially-persistent incremental forest with subtree sum queries.

There are $\Theta(n^2)$ possible queries, and it is straightforward to precompute the answers in $O(n^2)$ time and $O(n^2)$ space so that each query takes constant time.

By preprocessing $G$ using the Euler tour technique, each vertex $v_i$ can be associated with the discover time $d_i$ and finish time $f_i$ in an Euler tour of $G$ so that for any $i, j$, $v_i$ is an ancestor of $v_j$ in $G$ if and only if $d_i \le d_j \le f_j \le f_i$. Then the subtree sum query can be answered in linear time with a data structure using linear space by visiting the vertices $v_i, \dots, v_j$ and summing up the values $f(v_k)$ where $i \le k \le j$ and $v_i$ is an ancestor of $v_k$.

If either the vertex $v_i$ is fixed or a specific forest $G_j$ is fixed, the number of queries drops to $\Theta(n)$, which permits a trivial linear-space, constant-time solution.

As an example of a constant-time solution for a specific forest $G_j$, consider constructing an array $A_j$ of size $O(n)$ that has the value of each vertex $v_i$ in $G_j$ at $G_j[d_i]$ and zeros everywhere else. Then the subtree sum of $v_i$ in $G_j$ is equal to the subarray sum $A_j[d_i] + ... + A_j[f_i]$. By precomputing the prefix sum of the array $A_j$, the subarray sum can be computed in constant time for any vertex $v_i$.

---

For sublinear query times, the problem can be reduced to 2d orthogonal range searching by using the Euler tour technique as follows. Construct the point set $P \subset \mathbb{N} \times \mathbb{N}$ by mapping each vertex $v_i$ to the point $(d_i, i) \in P$ with associated value $f(v_i)$, where $d_i$ is the discover time in the Euler tour of $G$. Then the subtree sum query for $v_i$ and $G_j$ can be answered using 2d three-sided range sum on $P$ as the sum over points $(d, t) \in P$ inside the three-sided range $d_i \le d \le f_i$ and $t \le j$.

However, when the problem is reduced to orthogonal range searching, the tree structure in $G$ is lost, and the underlying data structure for 2d three-sided range sum on arbitrary point sets does not permit a solution using linear space and polylogarithmic query time. Using standard range searching techniques it is possible to obtain $O(n \log n)$ space and polylog query time, or using a kd-tree it is possible to obtain $O(n)$ space and $O(\sqrt n)$ query time.

---

Another approach to achieve polylogarithmic query times is to apply standard partial persistence techniques to a data structure for the dynamic subtree sum problem. E.g. the array $A_j$ from the constant-time solution sketched previously can be stored in a balanced search tree (BST) augmented to support subarray sums in $O(\log n)$ time, and $A_{j+1}$ can be built from $A_j$ by inserting the value for $v_{j+1}$ at position $d_{j+1}$. By applying standard partial persistence techniques to the BST that stores the array, an $O(n \log n)$ space data structure arises that can compute the subarray sum of any $A_j$ in $O(\log n)$ time.

Answer 1

It turns out this is possible with $O(n \log n)$ preprocessing time, polylog ($O(\log^3 n)$) query time and linear space:

1. Convert the forest into binary trees of logarithmic height.
   
2. For each node, compute the cumulative sum at appropriate times such that given time and node, at most $O(\log n)$ descendants were inserted after the previous sum.
   
3. Use a space-efficient way to record the above $O(\log n)$ descendants.

For (1), we can change a tree into a binary tree by adding dummy nodes, and make the depth logarithmic by using a heavy-light decomposition. Each node has at most one heavy child, and is reachable using $O(\log n)$ light edges. We can then change a heavy path of length $k$ into a binary tree of depth $O(\log k)$, albeit with each original node (and its sum) being the sum of $O(\log k)$ new nodes. However, the latter $O(\log k)$ does not multiply our preprocessing time (or space). Even online $O(\log n)$ per element preprocessing time should be possible, albeit with the complication that the heavy-light decomposition need not be constant there.

For (2), we incrementally add nodes, and update the sums. For each node, have a new sum each time $θ(\log n)$ (the precise number only affects the constant factors) descendants are added. Use a data structure such that given time (i.e. given $j$ for the forest $G_j$), in $O(\log n)$ time we can find the record for the previous sum for the node. The record will contain the sum and the data for the next step, including the link to the next record for the node.

For (3), to store the data for the $O(\log n)$ descendants, we only store, in order, whether the descendant came from the left or the right subtree, plus for each child, a pointer and an offset to get the corresponding data for the child. We can then traverse the subtree and look up the nodes. In effect, we store $O(n \log n)$ bits rather than just $O(n \log n)$ pointers. Because the input has $Θ(n)$ pointers of $Ω(\log n)$ bit size (or $Θ(n)$ RAM words with $Ω(\log n)$ word size), this is linear space ($O(n)$ space per convention here, which can be confusing as some other problems default to space in bits).

Extensions: The algorithm can also be adapted for the extension in which a new child can be the root of an existing tree. We can also allow removal of leaf elements. However, allowing repeated detachments and attachments of trees is tricky given the interaction with depth reduction (though my intuition is that it is still possible in linear space and polylog update and query time, even for the online version).

Answer 2

Thanks to Dmytro Taranovsky for the thorough answer. Here's my attempt to rephrase his answer in my own words.

Without loss of generality, assume that $G$ consists of a single tree.

First, we reduce the problem to the special case of $G$ being a balanced binary tree.

Then we solve the problem on a binary tree $G$ by augmenting each node $A$ with subtree size $|T_A|$ with a data structure of size $\Theta(|T_A|)$ bits. If $G$ is balanced, then the augmentations use only $\Theta(n \log n)$ bits extra space, which is linear in the size of the input.

---

The main idea in the reduction to balanced binary trees is to obtain a new tree $G'$ by relinking deep subtrees to higher-up nodes.

If a subtree rooted at node $B$ has been relinked to an ancestor $A$, and $C$ is a node on the original $A$ to $B$ path, then a subtree sum query on $C$ in $G'$ needs to include the subtree sum of $B$ to obtain the subtree sum in the original graph $G$. We can relink the nodes of $G$ in such a way that any subtree sum on $G$ can be computed as $O(\log n)$ subtree sums on $G'$, and the specific $O(\log n)$ subtree sums that have to be performed on $G'$ for any node of $G$ are stored implicitly in $G'$, meaning we don't increase the asymptotic space complexity.

The specific relinking works as follows. Compute a heavy-light decomposition of $G$, which classifies each edge of $G$ as heavy or light and decomposes $G$ into heavy paths. Each heavy path is relinked into a balanced binary tree as follows. Let $A$ be the first node on the heavy path, let $B$ be the heavy child of $A$, and let $C$ be a node on the middle of the heavy path. If $B = C$, then we are done; otherwise, cut $C$ off from its parent and relink it as a child of $A$, and recursively transform the subtrees rooted at $B$ and $C$ (which are paths) into balanced binary trees. After doing this, each edge of $G'$ is either a relinked heavy edge, an original heavy edge, or a light edge, and the height of the entire tree $G'$ is now logarithmic. Insert dummy nodes to turn the tree into a binary tree without increasing the asymptotic height of the tree. To obtain the specific $O(\log n)$ subtree sums that have to be performed on $G'$ for a node of $G$, keep following parent pointers until a light edge is encountered. When an original heavy edge is traversed, the sibling is a relinked heavy child, which is one of the additional subtree sums that have to be performed on $G'$.

---

The main idea in the solution for balanced binary trees is to augment each node $A$ with subtree size $|T_A|$ with a list of size $\Theta(|T_A|)$ bits that encodes every $w$'th answer to a subtree sum of $A$ explicitly, where $w = \Theta(\log n)$ is the word size, and for each explicitly-stored answer stores another $\Theta(w)$ bits that are enough to compute any subtree sum of $A$ in polylog time beyond the ones stored explicitly.

Specifically, order the subtree nodes $T_A$ by insertion time and construct an orientation bit string, which is a $|T_A|$-bit string that indicates for each subtree node whether it is in the left subtree or right subtree of $A$. Group $T_A$ into blocks of size $w$. For each block, let $t$ be the insertion time of the first subtree node in the block; we store the subtree sum of $A$ at time $t-1$ explicitly, and in addition we store where in the left child's and right child's orientation bit string this block starts. The size of the augmentation is $\Theta(|T_A|)$ bits, as we store $\Theta(|T_A|/w)$ blocks, each of size $\Theta(w)$, along with a $|T_A|$-bit orientation bit string.

A subtree sum query on $A$ needs to locate the correct block in the sequence of subtree nodes $T_A$ and it needs to search the tree for up to $w$ extra nodes to add to the explicit answer stored with the block. This search is guided by the orientation bit strings and can be done in $O(w^2)$ time, as each extra node requires traversing $O(w)$ edges according to the orientation bit strings.

Once the augmentation for a node $A$ is computed, partition the list of subtree nodes $T_A$ into a list for each child and recursively compute the augmentation in each subtree. Preprocessing in this way takes $O(n \log n)$ time and $O(n \log n)$ bits of space.