As we have to calculate sum of fibbonaci of sum of each subset of a subset.

Now , we also know that Fibonacci(A+B)=Fibonacci(A)xFibonacci(B+1)+Fibonacci(A-1)xFibonacci(B).

Let us suppose we have a set {2,3,4,5}

then in segment tree the node containing this set will have 2 nodes one {2,3} for set and other for set {4,5} in segment tree node we are storing three values

- sum of fibbonaci of sum of each subset for example:- node of subset {2,3} will have fib(2)+fib(2+3)+fib(3);
- sum of fibbonaci of sum of each subset + 1 for example:- node of subset {2,3} will have fib(2+1)+fib(2+3+1)+fib(3+1);
- sum of fibbonaci of sum of each subset - 1 for example:- node of subset {2,3} will have fib(2-1)+fib(2+3-1)+fib(3-1);

Now what we have to find these values for {2,3,4,5} from above values of {2,3} and {4,5}

out of all subset {2}+{3}+{2+3} would be equal to sifb of {2,3} and {4}+{5}+{4+5} would be equal to sifb of {4,5} Now we have to find {2+4}+{2+5}+{2+4+5}+{3+4}+{3+5}+{3+4+5}+{2+3+4}+{2+3+5}+{2+3+4+5} for this we use Fibonacci(A+B)=Fibonacci(A)xFibonacci(B+1)+Fibonacci(A-1)xFibonacci(B).

this works as {2+4}+{2+5}+{2+4+5}+{3+4}+{3+5}+{3+4+5}+{2+3+4}+{2+3+5}+{2+3+4+5} can be written as

fib(2)*fib(4+1)+fib(2-1)*fib(4)±-----------+fib(2+3)*fib(4+5+1)+fib(2+3-1)**fib(4+5)*

when we reduce the above equation we find that the above equation is (fib(2)+fib(3)+fib(2+3))(fib(4+1)+fib(5+1)+fib(4+5+1))+(fib(2-1)+fib(3-1)+fib(2+3-1))(fib(4)+fib(5)+fib(4+5))

which is nothing but (sfib({2,3})*sfibp({4,5})+sfibm({2,3})*sfib({4,5}))

so the total sum for interval {2,3,4,5} becomes

sifb of {2,3} + sifb of {4,5} + (sfib({2,3})*sfibp({4,5})+sfibm({2,3})*sfib({4,5}))

Hope Your Doubvt Is Cleared Now