Let F(n) denote the nth Fibonacci number,

then, F(n) can be found by using the following : F(n) = element 0,0 : A*(B^n). where A is a 2x2 matrix : {{1,1},{0,0}} and B is a 2x2 matrix : {{0,1},{1,1}} element 0,0 means the upper left element of the resulting matrix.

Here is the formal equation if you are interested :

{{F(0),F(1)},{0,0}}*({{0,1},{1,1}}^N) = {{F(N),F(N+1)},{0,0}}

so, you can store A*B^k in every node, whenever you get a range update query, update it by multiplying the existing matrix in the node by B^increment.

Hope this helps

My method uses Binet's Formula. By Binet's Formula, , where . We can use a custom struct to store number of the form . We calculate the answer for α and β separately (on two different segment trees) and then combine them together when we query. Now, each range increment is equivalent to multiplying α^k in a range [l, r] and we can find α^k using binary exponentiation. (divide and conquer) The rest can be easily handled with a lazy propogation segment tree.

I tried the same approach given in the editorial but it's exceeding time limit in test case 11 . What might be the possible reasons Submission. Is it due to excessive creation of matrix objects.