CFTREE - Editorial

Author: Sunny Aggarwal
Tester: Vasya Antoniuk
Editorialist: Pushkar Mishra

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];
}

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:

4 Likes

My complexity for the question was 4nsqrt(n) but i kept getting tle. Can anybody please explain why?

Here is my solution

https://www.codechef.com/viewsolution/9232499

Edit: time limit is such a joke on this problem. When I changed the buffer size from sqrt(n) to 400, it got AC.Here is the ac solution .I only changed the line { if(ct==sqrt(m)) => if(ct==400) }

https://www.codechef.com/viewsolution/9236613

1 Like

keep getting WA with my SQRT decomposition approach. Link
Anyone, can help me with getting it accepted?

BTW, solutions are NOT available! Please, fix the problem.

Can you fix the solutions links?

“AccessDenied”

Author, Tester solution not visible like previous contest editorials

2 Likes

There exists a simpler Nlogn solution using segment trees and the identity f(m+n)=f(m)*f(n+1)+f(m-1)*f(n) .
See the following code for implementation of the same :


[1]

[1]: https://www.codechef.com/viewsolution/9232139
7 Likes

In Rebuild function,for every node you iterate over node_update list.Then how can be rebuild() done in O(N)??

No link to submit the solutions on practice page. Please fix it.

tried using hld and matrix exponentiation, but unable to implement in given time.

Same here Naveen I too tried forming segment trees with chains but messed it up in between. A great problem btw and a really nice editorial as well.

@rednivrug15 I found your solution elegant. But i couldn’t get the idea behind ‘offset’ and the tree recurrence. Can you please explain it ?

Hello Guys !
Can someone tell me what is wrong with my code… I am getting WA But running time is under constraint.
Thanks!!

https://www.codechef.com/viewsolution/9230143

1 Like

@sgoel01 how did you manage to submit? the submission is still closed to me.

It is not. Either try relogin or delete cache. If none of it works, use this link to submit: https://www.codechef.com/submit/CFTREE or open from codechef ide directly.

Can anyone tell similar problems?

This approach is quite Nice, I feel…

And I haven’t ever heard of it!!

why some people have taken offset in fabonacci ?

as

int offset = 100005 or 100020;
fib[offset]=0;
fib[offset+1]=1;

for( int i=offset-1; i>=0; i-- ) {
fib[i]=(fib[i+2]-fib[i+1]);
if( fib[i]<0)
fib[i] += mod;
}

for( int i=offset+2; i<3*N; ++i ) {
fib[i]=( fib[i-1]+fib[i-2]);
if( fib[i]>=mod )
fib[i]-=mod;
}

I think this problem can also be solved using segment tree with lazy propagation.

1 Like

Can somebody explain to me Meteora’s solution. It is elegant but i didn’t get the part with range update…and the reason for keeping 2 BITs.
here is the solution link . Also can anyone explain the way she has queried the tree. It appears that start and end value of a subtree is being updated in the bits. BUt the way it has been done is still cryptic to me.