RANGESUM - Range Sum
You are initially given an array of N integers (1 ≤ N ≤ 105). 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 a1, a2, a3.... an, you need to return the following sum : al + al+1 + al+2 ... + ar.
(ii) Operation 2 : Op2(x)
You are given a single integer x (|x| ≤ 109). Add this element to the beginning of the array. After this operation, x will now become a1, the old a1 will now become a2, and so on. The size of the array will increase by 1.
Input
The first line contains a single integer N (1 ≤ N ≤ 105), the number of elements initially in the array.
This is followed by a line containing N space separated integers, a1 a2 ... aN. (|ai| ≤ 109)
The next line contains a single integer Q, the number of operations you will be asked to perform. (1 ≤ Q ≤ 105)
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 : al + al+1 ... + ar
2 x : Carry out operation 2 with the argument x. (|x| ≤ 109)
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
|
baranowski:
2016-01-06 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:
2015-12-03 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:
2015-08-29 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: 2016-10-07 09:30:22 |
|
Abhilash:
2015-06-23 12:49:34
easy |
|
pingal tirkey:
2015-05-23 18:33:22
Be careful I assumed numbers in array to be positive which caused me 6 WA!
|
|
saanc:
2014-11-04 05:25:57
some test files have q>100000.Problem setter should not do this |
|
maniAC:
2014-08-19 11:02:56
Use long long !. |
|
nikhil_nihal:
2014-07-20 00:42:28
getting WA in 5th running...
|
|
RIVU DAS:
2014-03-17 04:59:47
Learnt a lot!! |
|
ping_of_death:
2014-02-20 22:00:44
Nice problem ....a lot to learn in arrey implementation ... |
Added by: | Gowri Sundaram |
Date: | 2013-04-11 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |