Aladdin And The Return Journey

<code class="python">
# Pre-define some functions
Initialize(T):
	Treat T as a rooted tree, and let node 0 be the root
	Construct the LCA (lowest common ancestor) data structure on T
 
# PreOrderTraversal(i,A) populates the array A with the
#  pre-order-traversal for the sub-tree rooted in node i
def PreOrderTraversal(i,A):
	A.push(i)
	for each child j of i:
		PreOrderTraversal(j,A)
 
# lca(i,j) returns the lowest common ancestor of i and j
def lca(i,j):
	...
 
# If B is an array, update(B,i,j,v) increments B[i..j] by value v (using a Fenwick Tree)
def update(B,i,j,v);
	...
 
### MAIN ALGORITHM BEGINS HERE
solve(T,v[]):
	let N = |T| 		#(the number of nodes in T)
	let A[0..N-1] be an array
	let B[0..N-1] be an array
 
	# initialization
	call Initialize(T)
	call PreOrderTraversal(0,A)
	for all i = 0..N-1
		Set B[i] = v[i]
 
	for each query:
		if query is type "Update i,new_v":
			Let L be the index (integer) so that A[L] = i (the index corresponding to node i in A)
			Let R be the largest index such that A[R] is a descendant of i
			# Note: A[L..R] now precisely contains the sub-tree rooted in i
 
			Let v_change := v[i] - new_v
			update(B,L,R, v_change)
			Set v[i] = new_v
		else (query is type "Count i,j"):
			Let c := lca(i,j)
			Let sum_ic = B[i] - B[c] + v[c]		# sum(i,c) = sum(i,0) - sum(i,c) + v[c]
			Let sum_jc = B[j] - B[c] + v[c]		# sum(j,c) = ... (similarly)
			Let ans = sum_ic + sum_jc - v[c]	# sum(i,j) = sum(i,c) + sum(j,c) - v[c]
 
			Print (ans)
		</code>

Review

Summary

This is a beautiful illustration of many Data Structures on Trees. To solve this problem, you need knowledge of:

• The Lowest Common Ancestor data structure
• Prefix Sums and Range Queries
• Pre-Order-Traversal
• Fenwick Trees

These ideas allow you to (eventually) reduce the problem into a "range query" problem on a simple array. There are quite a few non-trivial "reductions" (problem transformations) needed to get there, but in the end, it is quite a neat solution!

First, we assume the tree is rooted, and that node $0$ is the root of the tree. This makes the problem easier to conceptualize and solve (because there are many data structures and techniques to solve problems on rooted trees).

The next "reduction" is to notice that, for rooted trees, the query $sum(i,j)$ (finding the number of genies on the path from $i$ to $j$) can be reduced to finding the answer to queries $sum(i,c)$ and $sum(j,c)$, where $c$ is an "ancestor" of both $i$ and $j$ (it is actually the "Lowest Common Ancestor" or $lca(i,j)$). These types of queries are easier to handle (because they are always concerning parents and children, or ancestors and descendants, rather than arbitrary nodes / paths). And the well-known LCA data structure makes it a routine task to find $c$ whenever we need to!

The precise formula is:

(where $v_c$ is the current number of genies on node $c$). The last subtraction of $v_c$ is to avoid double-counting it.

Next, we notice that queries of the form $sum(i,c)$ (where $c$ is an ancestor of $i$) can be reduced to finding the queries $sum(i,0)$ and $sum(c,0)$, where $0$ is the root of the tree. There are only $O(N)$ queries of the form $sum(i,0)$, so this is much more manageable.

The precise formula is:

So, putting together the above two formulas, we can see that all queries $sum(i,j)$ can be solved by:

(where this formula only depends on queries from nodes to the root.)

So we are only concerned with answering queries of the form $sum(i,0)$. Now, let's pretend we already know $sum(i,0)$ for all nodes $i$. If an "update" query comes on some node $i$ for some value $v$, which of the answers will change? Well, for a node $x$, if $x$ is a child or descendant of node $i$, then $sum(x,0)$ will change (because $i$ is on the path from $x$ to $0$). And if $x$ is NOT a descendant of $i$, then $sum(x,0)$ will NOT change. So, when an update query comes, we want to update precisely all of the nodes in the sub-tree of $i$. And when a "count" query comes, we just want to lookup the answer for the given node.

We can actually do this fairly efficiently. Consider the "Pre-Order-Traversal" array $A$ of the tree. That is, $A$ is a "permutation" of the numbers $0$ through $N-1$ defined recursively by a depth-first-search.

The key observation about the array $A$ is that, for a given node $i$, all of its descendants will appear consecutively (next to each other) in this array. So, when an "update" query comes in, since we would like to update all descendants of the node $i$, it is equivalent to updating all the nodes in a contiguous sub-array of $A$. So we do precisely that. We construct another array $B[ ]$ so that $B[k] := sum(A[k],0)$ (the number of genies on the path from node $A[k]$ to node 0). Whenever we want to update some node $i$, we find its index in $A$, and we find the indices of all its children in $A$. This defines a range $L,R$ of indices. We then increment/decrement the corresponding values in the $B$ array: $B[L..R]$ with a range update.

Lastly, in order to efficiently perform these range updates and range queries on the $B$ array, we must avoid "explicitly" storing the data. Instead, we construct a Fenwick Tree to represent $B$. A Fenwick Tree can support range updates and single-point queries (which is precisely what we need) in $O(\lg N)$ time. This is sufficient.

As long as we can maintain the $B[ ]$ array with a Fenwick Tree, we can answer a query $sum(i,j)$ using the formula above:

where $c := lca(i,j)$ and $B[ ]$ can be computed from the Fenwick Tree. This yields an overall $O(N \lg N)$ solution.

1. Assume the tree is rooted at node $0$. Without loss of generality.

2. For a pair of nodes $i$ and $j$, let $c$ denote $lca(i,j)$. Then $sum(i,j) = sum(i,c) + sum(c,j) - v_c$. This shows that we can reduce queries on arbitrary paths to queries on "ancestor-descendant" paths.

3. For a pair of nodes $i$ and $c$ (where $c$ is an ancestor of $i$). Then $sum(i,c) = sum(i,0) - sum(c,0) + v_c$. This shows that we can reduce all queries into those dealing with the root node.

4. Suppose we somehow "store" $sum(i,0)$ for all nodes $i$. When an "update" query comes for a specific node, we have to update exactly those nodes that are descendants of the changing node. Moreover, we increment/decrement all of these nodes by the same amount. This can be seen by inspection. If $v_i$ is changing, then $sum(x,0)$ changes for some node $x$ if and only if $x$ is in the sub-tree of $i$.

5. Consider the Pre-Order-Traversal array of the tree. For any node $i$, all the descendants of $i$ (including $i$ itself) will appear consecutively in this array. This makes the problem of "updating a sub-tree" into the problem of "updating a contiguous sub-array". The latter problem is much easier to solve.

6. Suppose we "relabel" the nodes according to their Pre-Order-Traversal, and we construct an array $B$ so that $B[i] = sum(i,0)$. Then to "update" a node, we simply have to update a contiguous range in $B$. This can be done with a Fenwick Tree. This was the last step in the algorithm. Above we do not "relabel" the nodes, but instead of use new labelling (according to the Pre-Order-Traversal) as indices into the $B$ array (these are equivalent definitions).

7. The entire problem can be solved in $O(\lg N)$ time per query.

8. This problem requires a lot of prior knowledge. We needed to recognize that we should transform the tree into a rooted tree. We need to know about the Lowest Common Ancestor, Fenwick Trees, Prefix Sums, and Pre-Order-Traversal Array -- all non-trivial data structures. This was not an easy problem to solve without knowing about all of these things.

9. Turning the tree into a rooted tree is an example of a problem transformation.

10. Arbitrary queries $sum(i,j)$ were too hard to solve. Instead we repeatedly simplified our queries. By using the LCA of $i$ and $j$ (denoted by $c$), we could simplify $sum(i,j)$ into queries of the form $sum(i,c)$ and $sum(j,c)$. Taking this one step further, we were able to simplify all the queries into forms $sum(i,0)$, $sum(j,0)$ and $sum(c,0)$. This made our task much easier to solve.

11. Although not explicitly stated above, it is helpful to clearly write down the formulas that we get after each simplification. This helps to avoid bugs later on!

• The First Rule of Tree Problems: Pick an arbitrary root! This appears very often because "rooted" trees have much more structure and symmetry than un-rooted trees. Often-times the root doesn't matter. Sometimes the root matters, or sometimes you have to "try" all nodes as the root.

• Whenever you encounter problems that relate to "paths on a rooted tree", it is very likely that the LCA data structure will be useful. Why? Because every path from $i$ to $j$ can be partitioned into two paths, one from $i$ to $c$ and one from $c$ to $j$ where $c$ is the LCA of $i$ and $j$. And these kinds of paths are easier to deal with.

• Whenever you encounter problems that relate to querying/updating "sub-trees of a rooted tree", it might be possible that the Pre-Order-Traversal Array will be useful! Why? Because the Pre-Order-Traversal Array has the property that all nodes in a given sub-tree occur consecutively in the array. This makes it easier to perform range-updates, range-queries, and even "splitting" and "merging" sub-trees (i.e.: if we treat them like linked lists)! Arrays are much easier to deal with than trees (see some of the Related Problems below).

• Trees / Querying Paths on a Tree / Lowest Common Ancestor (LCA)

• Trees / Querying Sub-Trees of a Tree / DFS Ordering / Pre-Order-Traversal

• Data Structures / Range Queries / Fenwick Trees and Segment Trees

• Prefix Sums / Prefix Sums on a Tree / Sums of Ancestor Paths

• Range Queries on a Tree / Heavy-Light Decomposition (HLD)

Static Version of the Problem. What if there were no "update" queries. What if you were simply given the number of genies at the beginning, and you had to only answer queries of the form $sum(i,j)$? Can you find a way to answer all queries in $O(1)$ time with $O(N)$ pre-processing?

Range Updates and Point Queries. Given an array $B$, we want to support "range updates" (i.e.: increment $B[i..j]$ by a value $v$) and "point queries" (i.e.: find the value of $B[i]$ for some $i$). Explain how one would use a Fenwick Tree to solve this problem. (Note: This is a simplified version of the problem we faced here.)

Point Updates and Range Queries. Given an array $B$, we want to support "point updates" (i.e.: increment $B[i]$ by a value $v$) and "range queries" (i.e.: find the value of $B[i..j]$). Explain how one would use a Fenwick Tree to solve this problem. How is this similar/different to the previous problem?

Range Updates and Range Queries. Given an array $B$, we want to support "range updates" (i.e.: increment $B[i..j]$ by a value $v$) and "range queries" (i.e.: find the value of $B[i..j]$). How would you solve this problem? Can you still use Fenwick Trees to solve it? Explain how you would use Segment Trees or Range Trees to solve this problem.

Update all parents of a node. We used the Pre-Order-Traversal array (along with a Fenwick Tree) to allow us to "update an entire sub-tree" and to "query a single node". What if we wanted to support the following queries: a) "increment a node $i$ and all it's ancestors/parents by a value $v$", and b) "count the value of any node $i$"? How might we solve this problem? Is there any way to reduce this problem to the previous one? Can we still use the Pre-Order-Traversal array? Can we still use Fenwick Trees? Can we rephrase this problem in terms of sub-trees?

Heavy-Light Decomposition. Learn about the Heavy-Light Decomposition Data Structure. This data structure decomposes a tree into disjoint paths that go from ancestors to descendants; each path can be treated as an "array" (which you can use a Fenwick Tree on). Can you solve the current problem using Heavy-Light Decomposition?

SPOJ 14932. Lowest Common Ancestor (LCA) Practice with LCA

(More to come later.)