PROBLEM LINK:
Author: Sunny Aggarwal
Tester: Sergey Kulik
Editorialist: Mugurel Ionut Andreica
DIFFICULTY:
MEDIUM
PREREQUISITES:
Fibonacci Numbers, Segment Trees
PROBLEM:
Given an array A consisting of N elements, Chef asked you to process following two types of queries on this array accurately and efficiently.
- C X Y: Change the value of X-th element of array to Y i.e A[X] = Y.
- Q L R: Compute the function F over the subarray defined by the elements of array A in the range L to R, both inclusive.
The function F(S) is defined as F(S)=(\sum_{W\subseteq S}{Fibonacci(Sum(W))})\ modulo\ (10^9+7), where Sum(W) denotes the sum of all the elements in the sub-multiset W and Fibonacci(Z)=the Z-th Fibonacci number.
The function F applied over a subarray [L,R] of the array A is defined as F(S) where S is the multiset consisting of all the elements from the range [L,R] from the array A (i.e. S={A(L), A(L+1), ā¦, AĀ®}).
EXPLANATION:
We can use the following property of Fibonacci numbers: Fibonacci(A+B)=Fibonacci(A)xFibonacci(B+1)+Fibonacci(A-1)xFibonacci(B).
With this property we can use a segment tree in order to efficiently process updates and queries. For each interval corresponding to a node of the segment tree we will store 3 values:
- sfib = sum of the values Fibonacci(Sum(W)) (modulo 10^9+7), for all the sub-multisets W
- sfibm1 = sum of the values Fibonacci(Sum(W) - 1) (modulo 10^9+7), for all the sub-multisets W
- sfibp1 = sum of the values Fibonacci(Sum(W) + 1) (modulo 10^9+7), for all the sub-multisets W
For the leaves of the segment tree we will initialize these values directly. For a leaf node L corresponding to a position i of the array A we will simply set:
- L.sfib = Fibonacci(A[i])
- L.sfibm1 = Fibonacci(A[i] - 1)
- L.sfibp1 = Fibonacci(A[i] + 1)
Since A[i] can be pretty large, we need an efficient method of computing Fibonacci(A[i]) (and, in general, for computing Fibonacci(Y) for Y as large as 10^9). There are multiple methods which can be used for computing these values in O(log(Y)) time. Below you can see one such function which uses memoization:
Fibonacci(y) {
if (y <= 0) return 0;
if (y <= 2) return 1;
if (y in fibonacci_cache) {
return fibonacci_cache[y];
}
int f, b, a;
b = y / 2; // integer division
a = y - b;
f = (Fibonacci(a) * Fibonacci(b + 1) + Fibonacci(a - 1) * Fibonacci(b)) % MOD;
fibonacci_cache[y] = f;
return f;
}
For a non-leaf node node we can use the following function for computing its information based on the information available in its left and right children:
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;
}
Processing an update operation X Y can be done as follows in O(log(N)) time. For the leaf node L corresponding to the position X from the array we reinitialize its values:
- L.sfib = Fibonacci(Y)
- L.sfibm1 = Fibonacci(Y - 1)
- L.sfibp1 = Fibonacci(Y + 1)
Then, for every ancestor of the node L, starting from its parent and going up to the root, we recompute its information using the CombineIntervalInfo function.
Handling a query L R can be done as follows, also in O(log(N)) time. We find the O(log(N)) nodes of the segment tree such that the disjoint union of their intervals is equal to the interval [L,R]. Let these nodes be node(1), ā¦, node(K). If K=1 then the answer is node(K).sfib. Otherwise, we will we compute a tuple ANS containing the same fields sfib, sfibm1 and sfibp1 as the information stored for each segment tree node. We initialize ANS by combining the information from node(1) and node(2). Then, for every 3\leq i\leq K we update ANS by combining its information with that of node(i). At the end, the answer is ANS.sfib.
AUTHORāS, TESTERāS AND EDITORIALISTāS SOLUTIONS:
Authorās solution can be found here.
Testerās solution can be found here.
Editorialistās solution can be found here.
