PROBLEM LINK:
Author: Sunny Aggarwal
Tester: Vasya Antoniuk
Editorialist: Pushkar Mishra
DIFFICULTY:
Medium
PREREQUISITES:
Data Structures, Graph
PROBLEM:
Given is a rooted tree. There are two types of operation on this tree. The first operation is of the form U x k. It requires us to add (k+d)^{th} fibonacci number to all the nodes in the subtree of X at depth d (for all valid d's). The second operation is of the form Q x. It asks us to report the value of node X. Handle both the queries.
EXPLANATION:
There are are two approaches to this question. In this editorial, we discuss the one is based on caching of update operations. The other one can be found in setter’s solution.
Caching of updates/queries is a very powerful technique. It works on two principles:
- We break the updates down into \sqrt{N} blocks, where N is the number of nodes in the tree.
- After processing one block of \sqrt{N} updates, we should be able to remake the data structure we are maintaining (graph or tree or anything other way of representing data) quickly. Quickly normally means linear or quasi-linear time.
- For the queries that need to be answered, we should be able to quickly calculate the answer for them inclusive of the updates that are in the current block. We should be able to iterate over the updates and find the answer quickly, preferably in constant time or so.
Let’s see how we can get these 3 factors to work in this problem. We will maintain a buffer vector called updates which stores at most \sqrt{N} pairs of the form (x, k) which tells us that U x k operation had been called. Once the buffer becomes \sqrt{N} long we remake the entire tree structure.
We begin by having an array fib[i] which holds the i^{th} fibonacci. This array should be at least 2*10^5 in length since K can at max be 10^5. We maintain an array val[i] which holds the value of node i inclusive of the updates just before the ones currently in the buffer. To answer a particular query Q x at any given point in time, we first take ans = val[x]; then we iterate over the updates in the buffer to see which updates affect x. If some update does, we add the appropriate fibonacci number as per the specification in the update to our answer variable ans. Then we simply output ans.
The part that is left in this algorithm is to describe how to know whether a particular update in the buffer affects a query node or not, if it does then what fibonacci number is to be added, and how to remake the val array quickly.
We start with the first two things, i.e., checking whether an update in the buffer affects the query node or not and what fibonacci number to add if it does. For this, we need to quickly determine whether a node lies within the subtree of another node or not. There is a very standard technique to do this: in-out linearisation of the tree. While doing a DFS of the tree, we can map the subtree of a node to a specific range in the array. If the range of a node x lies within the range of another node y then x lies in the subtree of y. Thus, if we prebuild this structure for the tree, then we can determine in constant time which updates in the buffer affect the query node. For an update that affects the query node, how can we know which fibonacci number to be added. We can do this by keeping another array depth[i] which gives the depth of the i^{th} node (depth of root is 0). Now, if an update U x_1 k affects a query node x_2, then the fibonacci number to be added to the query answer is fib[k + depth[x_2] - depth[x_1]].
We have everything in place now. All we need to do is find a way to rebuild the tree after the buffer reaches length \sqrt{N}. The rebuild routine will be very similar to a DFS function. We just have to work a way out to propagate an update at a node down to its subtree. Fibonacci numbers have a very interesting recurrence. Let’s have an array node\_update. In this array, node\_update[v] is a list k's from all those updates that exist in the buffer that were for node v (i.e., updates of the form U v k). Let’s say we have p, q stored at a particular node v. This means we have to add fib[p]+fib[q] to val[v]. For the children of v, we need to add ((fib[p-1]+fib[p]) + (fib[q-1]+fib[q])).
Analogously, for the grand-children, we need to add ((fib[p]+fib[p+1]) + (fib[q]+fib[q+1])).
This leads us to an important observation:
((fib[p-1]+fib[p]) + (fib[q-1]+fib[q])) = ((fib[p]+fib[p]) + (fib[p-1]+fib[q-1]))
((fib[p]+fib[p+1]) + (fib[q]+fib[q+1])) = ((fib[p+1]+fib[q+1]) + (fib[p]+fib[q]))
Essentially, all we need to pass on to the children of v is the sum of fibonacci numbers at v and the sum of fibonacci numbers which are one before the fibonacci numbers at v. This gives us the way to rebuild the val array. Here is the pseudocode:
//v is the node we are currently at in the recursion
//current is the value that needs to be added here
//prev is the value that was added to the parent of this node
rebuild(v, current, prev)
{
//this value stores the sum of fibonacci numbers which
//are one before the fibonacci numbers at v
upd = 0;
for(i = 0 to node_update[v].size()-1)
{
//adding update values at this node to current
current += fib[node_update[v][i]];
upd += fib[node_update[v][i]-1];
}
//adding current to val[v]
val[v] += current;
//preparing new_current and new_prev
new_current = current + upd + prev;
new_prev = current
for(c = children of v)
{
//recursively building children
rebuild(c, new_current, new_prev);
}
//now that val[v] has been updated, clear the
//backlog for next block of updates.
node_update[v].clear();
}
The rebuild function is just a modified DFS; it is \mathcal{O}(N). It is called as rebuild(1,0,0). Since, this is done at most \sqrt{N} times, the complexity of this is \mathcal{O}(N \sqrt{N}). Each query can be answered in \mathcal{O}(\sqrt{N}) since it only requires constant number of operations per update operation stored in the buffer (which at max has \sqrt{N} updates). Thus, net complexity is \mathcal{O}(N \sqrt{N}).
The editorialist’s program follows the editorial. Please see for implementation details.
COMPLEXITY:
\mathcal{O}(N \sqrt{N})
SAMPLE SOLUTIONS:
[Author] Will be uploaded soon.
[Tester] Will be uploaded soon.
[Editorialist] Will be uploaded soon.
