All Tracks Data Structures Advanced Data Structures Segment Trees Problem

Zeus and Fibonacci
Tag(s):

Data Structures, Hard, Matrix Exponentiation, Segment Trees

Problem
Editorial
Analytics

You are given an array $$A$$ consisting of $$N$$ integers. You have to process two types of queries on this array.
Type 1: Change the $$i$$th element to $$X$$
Type 2: Given $$l$$ and $$r$$, calculate: $$$\sum_{i=l}^{r} \sum_{j=i}^{r} Fib ( \sum_{k=i}^{j} A_k ) $$$

Note: $$Fib(i)$$ is the $$i $$th Fibonacci number. $$Fib(0)=0 \space.\space Fib(1)=1 $$

Input

First line contains an integer $$ N$$.
Next line contains $$N$$ space separated integers denoting array $$A$$.
Next line contains the integer $$Q$$.
Next $$Q$$ lines are of the following format:
$$1 \space i \space X$$ : for type 1 query
$$2 \space l \space r$$ : for type 2 query

Output

For each type 2 query output the answer modulo $$10^9+7$$ on a new line.

Constraints

$$1 ≤ N,Q ≤ 10^5$$
$$1 ≤ A[i],x ≤ 10^9$$
$$1 ≤ l,r,i ≤ N $$
$$l ≤ r $$

SAMPLE INPUT
3
1 2 3
2
2 1 2
2 1 3
SAMPLE OUTPUT
4
19
Explanation

Query 1:
possible subarrays : (1),(2),(1,2)
Corresponding sums : 1 ,2 ,3
Corresponding fibonacci: 1 , 1, 2
Sum of fibnoacci : 1 + 1+2=4
output : 4%(10^9+7)=4
Query 2:
possible subarrays : (1),(2),(3),(1,2),(2,3),(1,2,3)
Corresponding sums : 1,2,3,3,5,6
Corresponding fibonacci: 1,1,2,2,5,8
Sum of fibnoacci : 19
output : 19%(10^9+7)=19

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

November Circuits

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications