@rohitangira
Consider a segment tree “tree” where all nodes hold some matrix. Like I said in my previous comment, let us store in the leaf node, M^x where x is the corresponding element and M = [[1,1],[1,0]].
Now for a node which is not a leaf, we simply need tree + tree[right] + tree.tree[right], where left and right are the left and right child respectively. We keep doing this recursively and build the segment tree.
Now for updating, we will update only one element and not a range. So we update a leaf node, and make sure to update all the ancestors of this leaf node. In other words, we are rebuilding the segment tree for every update. Also note, after using the array element initially to build the segment tree, the array is not needed anywhere else in the code. So actually when updating the array, we can only update the segment tree because all further computations will be held by the segment tree.
For query, I followed the basic segment tree propagation method (not lazy) to create a dummy matrix which will hold the data for the range query. This matrix will contain the final result. We only output the [1][0] element of this matrix. For further details, please read my code here and my earlier post. Cheers!
let array= [n1,n2,n3…nn];
A=(1+sqrt(5))/2 and B=(1-sqrt(5))/2
thus from a derivation i found Sum of all fibonacci multiset is=> 1/sqrt(5)*[(1+A^n1)(1+A^n2)…(1+A^nn)-(1+B^n1)(1+B^n2)…(1+B^nn)]
with this fetch takes O(1) time.
because:suppose x1=(1+A^n1) and y1=(1+A^n1) similarly x2=(1+A^n1)(1+A^n2) and y2=(1+B^n1)(1+B^n2).
Thus if we make an array of x and y such as
X=[x1,x1x2,x1x2x3,x1x2x3x4, to xn] and
Y=[y1,y1y2,y1y2y3,y1y2y3y4, to yn]
thus for Q 1 5 we take (X5-Y5)/sqrt(5); thus happens in O(1) time. And to build this array we take O(n) time… I want to know why this approach is not suitable here??? I have no clue whatsoever!!! I was getting wrong ans for this. I used long double for storing all double values!! can some one help??
please give link to your code
could someone pls explain the reasoning/intuition behind the combineIntervalInfo() routine.
may be not solvable also in given time or either lazy propogation also required ?
can you explain solution idea…if this problem has range update also?
Those who want proof of Fib(A+B) (Fibonacci shifting property) here it is!
Excellent problem ,Poor editorial , with no explanation for Combineintervalinfo function…!! , it feels like like editorial wants us to digest us the solution without any explanation…!!
2 Likes
can anyone explain what we store in the node.sfibm1 and node.sfibp1 of a non-leaf node? I am able to understand what we store in node.sfib… but can’t able to understand the other two values stored… plz reply…
They are the sum over the same Fibonacci values as for node.sfib, but decreased by 1 (for node.sfibm1) or increased by 1 (for node.sfibp1). For instance, if node.sfib is Fibonacci(7)+Fibonacci(3)+Fibonacci(10), then node.sfibm1=Fibonacci(7-1)+Fibonacci(3-1)+Fibonacci(10-1) and node.sfibp1=Fibonacci(7+1)+Fibonacci(3+1)+Fibonacci(10+1).
thanks… for reply i have figured out
Thank you Sir, for such a neat code. Wish everyone would write code of this clarity. (Y)