RANGESUM - Range Sum


Problem Statement

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
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

karthik_vg: 2017-11-03 05:23:07

never use accumalate in c++ it costed me 3 WA.

amulyagaur: 2017-08-16 07:30:10

AC in 1 go!

anantct7: 2017-07-30 10:23:08

Really Nice question...Prefix sum would do it :p

jaykay12: 2017-06-17 08:40:49

Nice Question. Use Prefix Sum. O(1) for both Queries. :) Finally AC.

sas1905: 2017-06-06 01:51:20

O(1) query processing..!! No need of BIT..!!


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