FIBQ - editorial

editorial
, , , , ,
21

Those who want proof of Fib(A+B) (Fibonacci shifting property) here it is!

22

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…

23

Can this be solved using the golden ratio?

24

To partially answer your question: the interval multisets are not generated, it’s not necessary. CombineIntervalInfo will calculate the correct answer, but I don’t understand how. Specifically I don’t understand how “F(A+B) = F(A).F(B+1) + F(A-1).F(B)” can be applied to Sum(F(Sum(s))) for s in multisets.

Here is an example where I computed the combination of [3, 4] and [1,2] and then [3, 4, 1, 2] separately, just to confirm it works: https://i.imgur.com/UwakZCg.jpg

25

Can anyone explain how they are finding the sum of individual subsets in a given range?

26

please give link to your code

27

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?

28

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
29

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

30

thanks… for reply i have figured out

31

Thank you Sir, for such a neat code. Wish everyone would write code of this clarity. (Y)