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
kabiyal: 2021-09-11 21:58:07

It's a great problem. In case of don't knowing segment tree then no worry. You can use prefix sum to solve this though the implementation is little bit tricky rather than using lazy propagation of seg tree(trivial).

Last edit: 2021-09-11 22:00:35
sharath1999: 2020-10-01 22:38:26

If you wanna do it with segment tree just input the array into segment tree in reverse and add elements in the end

stunner2k18: 2019-10-31 14:28:34

AC in one Go!

Can anyone tell how to do it with segment tree.. I mean its adding a new node every time we get 1 as our query choice...so how we update the whole tree with that......??

Last edit: 2019-10-31 14:34:45
veerendrasd_9: 2019-05-27 12:25:14

use prefix sum array. range sum in O(1) and adding in O(n).
range queries are most efficient in segment trees but for range sum we can use prefix array is most efficient due to easy implimentation.

julkas: 2018-12-27 13:44:28

Without ... :). Not so bad!

mag1x_: 2018-06-23 12:12:25

Take input array invert it and prefix sum :)

vivek_dwivedi: 2018-06-13 21:05:01

Need some help !!
I am getting WA constantly my algo is of o(1) are there any tricky test cases that i am missing ! @admin please help

phewww ! done after so long time and many WA . I dont know what was wrong i just re-wrote whole code ! .. Good question though

Last edit: 2018-06-19 07:14:10
king_cat: 2018-05-14 09:29:57

Use long long int!!

gamapro: 2018-04-17 20:23:40

Never use printf, it cause me 5 WRONG ANSWER

dipankar12: 2018-04-01 19:07:46

sqrt+dcmp works


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