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
|
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!
|
|
veerendrasd_9:
2019-05-27 12:25:14
use prefix sum array. range sum in O(1) and adding in O(n).
|
|
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 !!
|
|
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. |
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 |