<p>It turns out this is possible with <span class="math-container">$O(n \log n)$</span> preprocessing time, polylog (<span class="math-container">$O(\log^3 n)$</span>) query time and linear space:<br/></p>
<ol>
<li>Convert the forest into binary trees of logarithmic height.<br/></li>
<li>For each node, compute the cumulative sum at appropriate times such that given time and node, at most <span class="math-container">$O(\log n)$</span> descendants were inserted after the previous sum.<br/></li>
<li>Use a space-efficient way to record the above <span class="math-container">$O(\log n)$</span> descendants.</li>
</ol>
<p>For (1), we can change a tree into a binary tree by adding dummy nodes, and make the depth logarithmic by using a <a href="https://cp-algorithms.com/graph/hld.html" rel="nofollow noreferrer">heavy-light decomposition</a>.  Each node has at most one heavy child, and is reachable using <span class="math-container">$O(\log n)$</span> light edges.  We can then change a heavy path of length <span class="math-container">$k$</span> into a binary tree of depth <span class="math-container">$O(\log k)$</span>, albeit with each original node (and its sum) being the sum of <span class="math-container">$O(\log k)$</span> new nodes.  However, the latter <span class="math-container">$O(\log k)$</span> does not multiply our preprocessing time (or space).  Even online <span class="math-container">$O(\log n)$</span> per element preprocessing time should be possible, albeit with the complication that the heavy-light decomposition need not be constant there.</p>
<p>For (2), we incrementally add nodes, and update the sums.  For each node, have a new sum each time <span class="math-container">$θ(\log n)$</span> (the precise number only affects the constant factors) descendants are added.  Use a data structure such that given time (i.e. given <span class="math-container">$j$</span> for the forest <span class="math-container">$G_j$</span>), in <span class="math-container">$O(\log n)$</span> 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.</p>
<p>For (3), to store the data for the <span class="math-container">$O(\log n)$</span> 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 <span class="math-container">$O(n \log n)$</span> bits rather than just <span class="math-container">$O(n \log n)$</span> pointers.  Because the input has <span class="math-container">$Θ(n)$</span> pointers of <span class="math-container">$Ω(\log n)$</span> bit size (or <span class="math-container">$Θ(n)$</span> RAM words with <span class="math-container">$Ω(\log n)$</span> word size), this is linear space (<span class="math-container">$O(n)$</span> space per convention here, which can be confusing as some other problems default to space in bits).</p>
<p><i>Extensions:</i> 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).</p>

CC BY-SA 4.0
2022-07-10T00:25:34.903Z
minor clarification: for the depth reduction, the $O(\log k)$ height binary tree must expose a node of relative size $ε$ at depth $O(\log(ε^{-1}))$
Dmytro Taranovsky
CC BY-SA 4.0
2022-07-12T13:29:52.033Z
Thanks for the thorough answer! I am not sure how you "change a heavy path of length $k$ into a binary tree of depth $O(\log k)$, with each original node (and its sum) being the sum of $O(\log k)$ new nodes". As far as I understand it, in (1) you reduce the problem on general forests to the problem restricted to balanced binary trees, and (2)-(3) solve the problem for balanced binary trees. However I don't understand the reduction in step (1). Can you elaborate on that?
Mathias Rav
CC BY-SA 4.0
2022-07-12T18:51:47.690Z
@MathiasRav The basic step is that for a node $A$ we find a descendant $B$ such that $|T_B|$ and $|T_A|-|T_B|$ are both $Θ(|T_A|)$ ($T$ denotes subtree).  Make $A$ the new parent of $B$.  Nodes on the original $A$ to $B$ path (except $A$ and $B$) will now need to add the sum for $B$ to get the original sum.
Dmytro Taranovsky
CC BY-SA 4.0
2022-07-13T18:51:59.883Z
Thanks for the clarification. I've accepted your answer as I have convinced myself of the details. Both the reduction to balanced binary trees and the left/right bit encoding are really cool ideas that I wouldn't have come up with by myself. Thank you so much!
Mathias Rav
CC BY-SA 4.0
2022-07-09T16:08:15.843Z
2022-07-09T16:08:15.843Z
Dmytro Taranovsky
<p>Thanks to Dmytro Taranovsky for the thorough answer. Here's my attempt to rephrase his answer in my own words.</p>
<p>Without loss of generality, assume that <span class="math-container">$G$</span> consists of a single tree.</p>
<p>First, we reduce the problem to the special case of <span class="math-container">$G$</span> being a balanced binary tree.</p>
<p>Then we solve the problem on a binary tree <span class="math-container">$G$</span>
by augmenting each node <span class="math-container">$A$</span> with subtree size <span class="math-container">$|T_A|$</span>
with a data structure of size <span class="math-container">$\Theta(|T_A|)$</span> bits.
If <span class="math-container">$G$</span> is balanced, then the augmentations use only <span class="math-container">$\Theta(n \log n)$</span> bits extra space,
which is linear in the size of the input.</p>
<hr />
<p>The main idea in the reduction to balanced binary trees
is to obtain a new tree <span class="math-container">$G'$</span> by relinking deep subtrees to higher-up nodes.</p>
<p>If a subtree rooted at node <span class="math-container">$B$</span> has been relinked to an ancestor <span class="math-container">$A$</span>,
and <span class="math-container">$C$</span> is a node on the original <span class="math-container">$A$</span> to <span class="math-container">$B$</span> path,
then a subtree sum query on <span class="math-container">$C$</span> in <span class="math-container">$G'$</span> needs to include the subtree sum of <span class="math-container">$B$</span>
to obtain the subtree sum in the original graph <span class="math-container">$G$</span>.
We can relink the nodes of <span class="math-container">$G$</span> in such a way that any subtree sum on <span class="math-container">$G$</span>
can be computed as <span class="math-container">$O(\log n)$</span> subtree sums on <span class="math-container">$G'$</span>, and
the specific <span class="math-container">$O(\log n)$</span> subtree sums that have to be performed on <span class="math-container">$G'$</span>
for any node of <span class="math-container">$G$</span> are stored implicitly in <span class="math-container">$G'$</span>,
meaning we don't increase the asymptotic space complexity.</p>
<p>The specific relinking works as follows.
Compute a heavy-light decomposition of <span class="math-container">$G$</span>,
which classifies each edge of <span class="math-container">$G$</span> as <em>heavy</em> or <em>light</em>
and decomposes <span class="math-container">$G$</span> into <em>heavy paths</em>.
Each heavy path is relinked into a balanced binary tree as follows.
Let <span class="math-container">$A$</span> be the first node on the heavy path,
let <span class="math-container">$B$</span> be the heavy child of <span class="math-container">$A$</span>,
and let <span class="math-container">$C$</span> be a node on the middle of the heavy path.
If <span class="math-container">$B = C$</span>, then we are done;
otherwise, cut <span class="math-container">$C$</span> off from its parent
and relink it as a child of <span class="math-container">$A$</span>,
and recursively transform the subtrees rooted at <span class="math-container">$B$</span> and <span class="math-container">$C$</span> (which are paths)
into balanced binary trees.
After doing this, each edge of <span class="math-container">$G'$</span> is either a <em>relinked heavy</em> edge,
an <em>original heavy</em> edge, or a <em>light</em> edge,
and the height of the entire tree <span class="math-container">$G'$</span> 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 <span class="math-container">$O(\log n)$</span> subtree sums that have to be performed on <span class="math-container">$G'$</span>
for a node of <span class="math-container">$G$</span>, 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 <span class="math-container">$G'$</span>.</p>
<hr />
<p>The main idea in the solution for balanced binary trees
is to augment each node <span class="math-container">$A$</span> with subtree size <span class="math-container">$|T_A|$</span>
with a list of size <span class="math-container">$\Theta(|T_A|)$</span> bits
that encodes every <span class="math-container">$w$</span>'th answer to a subtree sum of <span class="math-container">$A$</span> explicitly,
where <span class="math-container">$w = \Theta(\log n)$</span> is the word size,
and for each explicitly-stored answer stores another <span class="math-container">$\Theta(w)$</span> bits
that are enough to compute any subtree sum of <span class="math-container">$A$</span> in polylog time beyond the ones stored explicitly.</p>
<p>Specifically, order the subtree nodes <span class="math-container">$T_A$</span> by insertion time
and construct an <em>orientation bit string</em>, which is a <span class="math-container">$|T_A|$</span>-bit string that indicates for each subtree node
whether it is in the left subtree or right subtree of <span class="math-container">$A$</span>.
Group <span class="math-container">$T_A$</span> into blocks of size <span class="math-container">$w$</span>.
For each block, let <span class="math-container">$t$</span> be the insertion time of the first subtree node in the block;
we store the subtree sum of <span class="math-container">$A$</span> at time <span class="math-container">$t-1$</span> 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 <span class="math-container">$\Theta(|T_A|)$</span> bits, as we store <span class="math-container">$\Theta(|T_A|/w)$</span> blocks,
each of size <span class="math-container">$\Theta(w)$</span>, along with a <span class="math-container">$|T_A|$</span>-bit orientation bit string.</p>
<p>A subtree sum query on <span class="math-container">$A$</span> needs to locate the correct block in the sequence of subtree nodes <span class="math-container">$T_A$</span>
and it needs to search the tree for up to <span class="math-container">$w$</span> 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 <span class="math-container">$O(w^2)$</span> time,
as each extra node requires traversing <span class="math-container">$O(w)$</span> edges according to the orientation bit strings.</p>
<p>Once the augmentation for a node <span class="math-container">$A$</span> is computed, partition the list of subtree nodes <span class="math-container">$T_A$</span>
into a list for each child and recursively compute the augmentation in each subtree.
Preprocessing in this way takes <span class="math-container">$O(n \log n)$</span> time and <span class="math-container">$O(n \log n)$</span> bits of space.</p>

CC BY-SA 4.0
2022-07-13T19:35:06.453Z
2022-07-13T19:35:06.453Z
Mathias Rav
<p>Consider a forest <span class="math-container">$G$</span> of <span class="math-container">$n$</span> vertices <span class="math-container">$v_1, \dots, v_n$</span> arranged left to right with edges from child to parent always going to the left, i.e. if the parent of vertex <span class="math-container">$v_i$</span> is <span class="math-container">$v_j$</span>, then <span class="math-container">$j &lt; i$</span>.
Additionally, each vertex <span class="math-container">$v_i$</span> is associated with a value <span class="math-container">$f(v_i) \in \mathbb{N}$</span>.</p>
<p>We are interested in computing subtree sums in the family of forests <span class="math-container">$G_0, \dots, G_n$</span> that arise when <span class="math-container">$G$</span> is built incrementally by adding the vertices in order <span class="math-container">$v_1, v_2, \dots, v_n$</span>, i.e. <span class="math-container">$G_i$</span> has vertex set <span class="math-container">$V_i = \{v_1, \dots, v_i\}$</span> and the edges from <span class="math-container">$G$</span> that connect vertices in <span class="math-container">$V_i$</span>.</p>
<p>The specific <em>subtree sum query</em> is the following: Given a vertex <span class="math-container">$v_i$</span> and forest <span class="math-container">$G_j$</span>, what is the sum of vertex values in the subtree of <span class="math-container">$G_j$</span> rooted at <span class="math-container">$v_i$</span>?</p>
<p><strong>Is there a <span class="math-container">$O(n)$</span>-space data structure that solves the <em>subtree sum query</em> in polylogarithmic query time?</strong></p>
<p><a href="https://i.sstatic.net/B2hLE.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/B2hLE.png" alt="f(v1)=4,f(v2)=8,f(v3)=3,f(v4)=7,f(v5)=11,E={(v2,v1),(v3,v2),(v4,v2),(v5,v4)}, answer to query Subtree-Sum(v2,G3) = f(v2) + f(v3) = 8 + 3 = 11" /></a></p>
<p>In other words, <span class="math-container">$G_i$</span> is built from <span class="math-container">$G_{i-1}$</span> by adding vertex <span class="math-container">$v_i$</span>, which is either a root (has no outgoing edge) or a non-root (has an edge to some vertex <span class="math-container">$v_j$</span> with <span class="math-container">$1 \le j &lt; i$</span>), and the problem can be considered as a static partially-persistent incremental forest with subtree sum queries.</p>
<p>There are <span class="math-container">$\Theta(n^2)$</span> possible queries, and it is straightforward to precompute the answers in <span class="math-container">$O(n^2)$</span> time and <span class="math-container">$O(n^2)$</span> space so that each query takes constant time.</p>
<p>By preprocessing <span class="math-container">$G$</span> using the <a href="https://en.wikipedia.org/wiki/Euler_tour_technique" rel="nofollow noreferrer">Euler tour technique</a>, each vertex <span class="math-container">$v_i$</span> can be associated with the discover time <span class="math-container">$d_i$</span> and finish time <span class="math-container">$f_i$</span> in an Euler tour of <span class="math-container">$G$</span> so that for any <span class="math-container">$i, j$</span>, <span class="math-container">$v_i$</span> is an ancestor of <span class="math-container">$v_j$</span> in <span class="math-container">$G$</span> if and only if <span class="math-container">$d_i \le d_j \le f_j \le f_i$</span>. Then the subtree sum query can be answered in linear time with a data structure using linear space by visiting the vertices <span class="math-container">$v_i, \dots, v_j$</span> and summing up the values <span class="math-container">$f(v_k)$</span> where <span class="math-container">$i \le k \le j$</span> and <span class="math-container">$v_i$</span> is an ancestor of <span class="math-container">$v_k$</span>.</p>
<p><a href="https://i.sstatic.net/tgUdE.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/tgUdE.png" alt="Euler tour numbers of an example graph" /></a></p>
<p>If either the vertex <span class="math-container">$v_i$</span> is fixed or a specific forest <span class="math-container">$G_j$</span> is fixed, the number of queries drops to <span class="math-container">$\Theta(n)$</span>, which permits a trivial linear-space, constant-time solution.</p>
<p>As an example of a constant-time solution for a specific forest <span class="math-container">$G_j$</span>, consider constructing an array <span class="math-container">$A_j$</span> of size <span class="math-container">$O(n)$</span> that has the value of each vertex <span class="math-container">$v_i$</span> in <span class="math-container">$G_j$</span> at <span class="math-container">$G_j[d_i]$</span> and zeros everywhere else. Then the subtree sum of <span class="math-container">$v_i$</span> in <span class="math-container">$G_j$</span> is equal to the subarray sum <span class="math-container">$A_j[d_i] + ... + A_j[f_i]$</span>. By precomputing the prefix sum of the array <span class="math-container">$A_j$</span>, the subarray sum can be computed in constant time for any vertex <span class="math-container">$v_i$</span>.</p>
<hr />
<p>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 <span class="math-container">$P \subset \mathbb{N} \times \mathbb{N}$</span> by mapping each vertex <span class="math-container">$v_i$</span> to the point <span class="math-container">$(d_i, i) \in P$</span> with associated value <span class="math-container">$f(v_i)$</span>, where <span class="math-container">$d_i$</span> is the discover time in the Euler tour of <span class="math-container">$G$</span>. Then the subtree sum query for <span class="math-container">$v_i$</span> and <span class="math-container">$G_j$</span> can be answered using 2d three-sided range sum on <span class="math-container">$P$</span> as the sum over points <span class="math-container">$(d, t) \in P$</span> inside the three-sided range <span class="math-container">$d_i \le d \le f_i$</span> and <span class="math-container">$t \le j$</span>.</p>
<p><a href="https://i.sstatic.net/Ps8ki.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Ps8ki.png" alt="graphical example of reduction to 2d orthogonal range searching" /></a></p>
<p>However, when the problem is reduced to orthogonal range searching, the tree structure in <span class="math-container">$G$</span> 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 <span class="math-container">$O(n \log n)$</span> space and polylog query time, or using a kd-tree it is possible to obtain <span class="math-container">$O(n)$</span> space and <span class="math-container">$O(\sqrt n)$</span> query time.</p>
<hr />
<p>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 <span class="math-container">$A_j$</span> from the constant-time solution sketched previously can be stored in a balanced search tree (BST) augmented to support subarray sums in <span class="math-container">$O(\log n)$</span> time, and <span class="math-container">$A_{j+1}$</span> can be built from <span class="math-container">$A_j$</span> by inserting the value for <span class="math-container">$v_{j+1}$</span> at position <span class="math-container">$d_{j+1}$</span>. By applying standard partial persistence techniques to the BST that stores the array, an <span class="math-container">$O(n \log n)$</span> space data structure arises that can compute the subarray sum of any <span class="math-container">$A_j$</span> in <span class="math-container">$O(\log n)$</span> time.</p>

<ds.data-structures><tree>
O(n)-space, polylog-time subtree sums in incremental forests?
Mathias Rav
# O(n)-space, polylog-time subtree sums in incremental forests?

(Asked by: username_0 on 2022-06-07)

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?**

[![f(v1)=4,f(v2)=8,f(v3)=3,f(v4)=7,f(v5)=11,E={(v2,v1),(v3,v2),(v4,v2),(v5,v4)}, answer to query Subtree-Sum(v2,G3) = f(v2) + f(v3) = 8 + 3 = 11](https://i.sstatic.net/B2hLE.png)](https://i.sstatic.net/B2hLE.png)

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](https://en.wikipedia.org/wiki/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$.

[![Euler tour numbers of an example graph](https://i.sstatic.net/tgUdE.png)](https://i.sstatic.net/tgUdE.png)

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$.

[![graphical example of reduction to 2d orthogonal range searching](https://i.sstatic.net/Ps8ki.png)](https://i.sstatic.net/Ps8ki.png)

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.

**Tags:** ds.data-structures, tree

---

## 2 answers

### Answer by username_1 on 2022-07-09. Score: 4 | Accepted answer

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](https://cp-algorithms.com/graph/hld.html). 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).

> **Comments:**
> **username_1**: minor clarification: for the depth reduction, the $O(\log k)$ height binary tree must expose a node of relative size $ε$ at depth $O(\log(ε^{-1}))$  
> **username_0**: Thanks for the thorough answer! I am not sure how you "change a heavy path of length $k$ into a binary tree of depth $O(\log k)$, with each original node (and its sum) being the sum of $O(\log k)$ new nodes". As far as I understand it, in (1) you reduce the problem on general forests to the problem restricted to balanced binary trees, and (2)-(3) solve the problem for balanced binary trees. However I don't understand the reduction in step (1). Can you elaborate on that?  
> **username_1**: @MathiasRav The basic step is that for a node $A$ we find a descendant $B$ such that $|T_B|$ and $|T_A|-|T_B|$ are both $Θ(|T_A|)$ ($T$ denotes subtree).  Make $A$ the new parent of $B$.  Nodes on the original $A$ to $B$ path (except $A$ and $B$) will now need to add the sum for $B$ to get the original sum.  
> **username_0**: Thanks for the clarification. I've accepted your answer as I have convinced myself of the details. Both the reduction to balanced binary trees and the left/right bit encoding are really cool ideas that I wouldn't have come up with by myself. Thank you so much!  

---

### Answer by username_0 on 2022-07-13. Score: 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.


---

