RANGESUM  Range Sum
Problem Statement
You are initially given an array of N integers ( 1<=N<=10^{5} ). Given this array, you have to perform 2 kinds of operations :
(i) Operation 1 : Op1( l, r )
You are given 2 integers l and r. ( 1 <= l <= r <= current size of the array ). You need to return the sum of all the elements with indices between l and r ( both inclusive ). That is, if the elements currently in the array are a_{1}, a_{2}, a_{3}.... a_{n}, you need to return the following sum : a_{l} + a_{l+1} + a_{l+2} ... + a_{r}.
(ii) Operation 2 : Op2( x )
You are given a single integer x ( x <= 10^{9} ). Add this element to the beginning of the array. After this operation, x will now become a_{1}, the old a_{1} will now become a_{2}, and so on. The size of the array will increase by 1.
Input
The first line contains a single integer N ( 1 <= N <= 10^{5} ), the number of elements initially in the array.
This is followed by a line containing N space separated integers, a_{1} a_{2} .... a_{N}. ( a_{i} <= 10^{9} )
The next line contains a single integer Q, the number of operations you will be asked to perform. ( 1 <= Q <= 10^{5} )
Q lines of input follow. Each such line starts with either the number 1 or the number 2. This indicates the type of operation that you are required to perform. The format of these queries are as follows :
1 l r : Carry out operation 1 with arguments l and r. ( 1 <= l <= r <= current size of the array )
That is, return the sum of the following array elements : a_{l} + a_{l+1} ... + a_{r}
2 x : Carry out operation 2 with the argument x. ( x <= 10^{9} )
That is, add the value x at the beginning of the array.
Output
For each query of type 1, output the return value on a new line. No output needs to be printed for queries of type 2.
Example
Input #1: 10
1 2 3 4 5 6 7 8 9 10
4
1 1 10
1 1 1
1 10 10
1 2 7
Output #1:
55
1
10
27
Input #2:
5
6 7 8 9 10
9
2 5
2 4
1 2 7
2 3
2 2
2 1
1 1 10
1 1 1
1 10 10
Output #2:
45
55
1
10
hide comments
naruto09:
20160328 05:27:15
awesome problem..learned something new..;) 

Divyaanand Sinha:
20160107 13:46:18
Is the array sorted? 

baranowski:
20160106 13:33:28
This is driving me crazy... Nice O(n+q) solution in C++, and I'm getting TLE around test case #5. 

hodobox:
20151203 20:49:39
Nice problem :) can be done with O(1) for both querries, and then you can just take the reversed array from input and process it all as type 2 querry :P 

dwij28:
20150829 16:40:21
O(1) for all queries. AC. A few months back I would have never solved this question. Time helps us evolve and get better .. :) Last edit: 20161007 09:30:22 

kumar saurav sinha:
20150624 16:54:52
AC in first attempt :D........ good question though....... 

Abhilash:
20150623 12:49:34
easy 

pingal tirkey:
20150523 18:33:22
Be careful I assumed numbers in array to be positive which caused me 6 WA!


:.Mohib.::
20141225 20:46:34
AC in first attempt.... :) 

saanc:
20141104 05:25:57
some test files have q>100000.Problem setter should not do this 
Added by:  Gowri Sundaram 
Date:  20130411 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 