In the april challenge 2016, FIBQ question , i was reading the editorial , and i am not able to understand the logic behind the ComibeintervalInfo function ,basically the logic of how they computing the values in each node of segmented tree.
CombineIntervalInfo(left, right, node) {
node.sfib = (left.sfib + right.sfib + left.sfib * right.sfibp1 + left.sfibm1 * right.sfib) % MOD;
node.sfibm1 = (left.sfibm1 + right.sfibm1 + left.sfib * right.sfib + left.sfibm1 * right.sfibm1) % MOD;
node.sfibp1 = (left.sfibp1 + right.sfibp1 + left.sfibp1 * right.sfibp1 + left.sfib * right.sfib) % MOD;
}
someone plz give deep explanation for this. thank you !
1 Like
I also don’t understand editorial approach
what i used is here…
| 1 1 | | f(1) | | 1 0 |
A = | | , F = | | , I = | |
| 1 0 | | f(0) | | 0 1 |
f(a,b) = f(a)+f(b)+f(a+b)
=( A^(a-1)+A^(b-1)+A^( (a+b) -1 ) )*F
= ( A^a +A^b + A^(a+b) )*A^(-1)*F
= ( A^a +A^b + A^a*A^b )*A^(-1)*F
= [ A^a + { I + A^a }*A^b ] *A^(-1)*F
= [ {I+ A^a} + { I + A^a }*A^b -I] *A^(-1)*F // add I and subtract I
= [ {I+ A^a} { I + A^b } -I] *A^(-1)*F
| b11 b12|
suppose {I+ A^a} { I + A^b } = B = | |
|b21 b22|
then final ans = b12 //you can under stand by trying out multiply and subtract as I have mentioned in original approach and b12, they are exactly same..just check out
***Happy coding***
My solution
This is what I understood from the editorial, it is not clear for me as well,
Leaf nodes are given, if array is [a, b, c], the leaf nodes are F(a), F(b) & F© [where F(x) is xth Fibonacci number]
The next upper level sfib, will have F(a) + F(b) + F(a+b), Let me know if you don’t understand this step,
The next upper level's sfib = (F(a) + F(b) + F(a+b)) + (F(c)) + (F(a) + F(b) + F(a+b))*(F(c+1)) + (F(a-1) + F(b-1) + F(a+b-1))*(F(c))
= F(a) + F(b) + F(c) + F(a+b) + F(a)F(c+1) + F(b)F(c+1) + F(a+b)F(c+1) + F(a-1)F(c) + F(b-1)F(c) + F(a+b-1)F(c)
= F(a) + F(b) + F(c) + F(a+b) + (F(a)F(c+1) + F(a-1)F(c)) + (F(b)F(c+1) + F(b-1)F(c)) + (F(a+b)F(c+1) + F(a+b-1)F(c))
= F(a) + F(b) + F(c) + F(a+b) + F(a+c) + F(b+c) + F(a+b+c)
= Required ans for subset a,b,c
Hope this helps
1 Like
In the given an array ‘a’ starting with starting index as 1 , you are given input values.
Q L R
L -> lower limit of index of array ‘a’
R -> upper limit of index of array ‘b’
For the calculation of ‘F’ , you have to perform the sum of summations of three types :
-
sum of all individual terms of fibonacci series whose index values are elements of array ‘a’ and the indices of array ‘a’ for this purpose are within the range of ‘l’ and ‘r’ (both inclusive).
-
sum of pairs of the fibonacci series whose indices is the sum of pair of values of elements of array ‘a’ with above mentioned details.
-
sum of elements of array ‘a’ with indices within the range and the obtained result is used to evaluate the fibonacci series term with index equal to the summation mentioned at the start of line.
Note : evaluate 3 when difference between l and r is greater than 1.
F = sum(fib[individual terms]) + sum(fib[pair terms]) + sum(fib[sumall])
For ex:
3 5
1 2 3
Array a = {1,2,3}
Q 1 2
F = fib[a[1]] + fib[a[2]] + fib[a[1]+a[2]] = fib[1] + fib[2] + fib[1+2] = fib[1] + fib[2] + fib[3]
Q 2 3
F = fib[a[2]] + fib[a[3]] + fib[a[2]+a[3]] = fib[2] + fib[3] + fib[5]
C 1 2
a[1] = 2
Q 1 2
F = fib[a[1]] + fib[a[2]] + fib[a[1]+a[2]] = fib[2] + fib[2] + fib[2+2] = fib[2] + fib[2] + fib[4]
Q 1 3
F = fib[a[1]] + fib[a[2]] + fib[a[3]] + fib[a[1]+a[2]] + fib[a[1]+a[3]] + fib[a[2]+a[3]] + fib[a[1]+a[2]+a[3]] =
fib[2] + fib[2] + fib[3] + fib[2+2] + fib[2+3] + fib[2+3] + fib[2+2+3] =
fib[2] + fib[2] + fib[3] + fib[4] + fib[5] + fib[5] + fib[7]
@rcsldav , plz explain what does f(a,b) signify…?? where did you find the property fib(a,b) = f(a)+f(b)+f(a+b) ??
@vinayb21 , i know this , but i not understanding how they compute it by using the function mentioned in my question .!
You can see my editorial, I used matrix exponentiation.
So all the rules are related matrix multiplication and Combinatorics.
1 Like
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 
3 Likes
yeah, i understood now. thanks a lot…
nice approach @ashok1113… nice editorial too…
1 Like
@killjee can you elaborate your answer,in terms that a newcomer can understand?