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
Aditya Bahuguna:
20130613 21:15:58
@Muh. Aunorafiq...long long fits everything in :) 

Muh. Aunorafiq Musa:
20130609 19:49:24
is the return value of op1 possible to use unsigned long long in C ?


Dominik Kempa:
20130518 18:50:30
Some testcases have Q > 10^5. 

Mitch Schwartz:
20130428 12:33:30
I think the test data was modified after my submission (I was the first solver), although I guess there's a small possibility it wasn't and my 0.01 was just really lucky with server instability  submitting the same exact code over and over now hasn't gotten 0.01 again, the best was 0.02.

Added by:  Gowri Sundaram 
Date:  20130411 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 