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 a, 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.
|
Sample Input 1 |
Sample Output 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 |
55 1 10 27 |
|
|
|
|
Sample Input 2 |
Sample Output 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 |
45 55 1 10 |
дерево отрезков
Объявим
массив длины 2n. Во вторую его половину занесем последовательность
a1 a2 .... an. Первую половину заполним нулями. Построим по этому
массиву дерево отрезков. При каждой операции типа 2 слева к имеющемуся массиву
будем приписывать новое число (новое число занимает место нуля).
В тестах
количество запрсов типа 2 не превосходит n.
Реализация
алгоритма
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 200010
using namespace
std;
vector<long long> SegTree(4*MAX,0);
void BuildTree(vector<long long>&a, int Vertex,
int LeftPos, int RightPos)
{
if (LeftPos == RightPos)
SegTree[Vertex] =
a[LeftPos];
else
{
int Middle = (LeftPos + RightPos) / 2;
BuildTree(a, 2*Vertex,
LeftPos, Middle);
BuildTree(a,
2*Vertex+1, Middle+1, RightPos);
SegTree[Vertex] =
SegTree[2*Vertex] + SegTree[2*Vertex+1];
}
}
long long
Summa(int Vertex, int
LeftPos, int RightPos,
int Left, int Right)
{
if (Left > Right) return
0;
if ((Left == LeftPos) && (Right == RightPos))
return SegTree[Vertex];
int Middle = (LeftPos + RightPos) / 2;
return Summa(2*Vertex, LeftPos, Middle, Left,
min(Right,Middle)) +
Summa(2*Vertex+1,
Middle+1, RightPos, max(Left,Middle+1), Right);
}
void update(int
Vertex, int LeftPos, int
RightPos,
int Position, long long NewValue)
{
if (LeftPos == RightPos)
SegTree[Vertex] =
NewValue;
else
{
int Middle = (LeftPos + RightPos) / 2;
if (Position <= Middle)
update (2*Vertex,
LeftPos, Middle, Position, NewValue);
else update (2*Vertex+1, Middle+1, RightPos,
Position, NewValue);
SegTree[Vertex] =
SegTree[2*Vertex] + SegTree[2*Vertex+1];
}
}
vector<long long> v;
int n, q, i, j, l, r;
int type, start;
int main(void)
{
scanf("%d",&n);
start = n + 1;
v.resize(start + n);
for(i = 0; i < n; i++)
scanf("%lld",&v[start + i]);
BuildTree(v,1,1,2*n);
scanf("%d",&q);
for(j = 0; j < q; j++)
{
scanf("%d",&type);
if (type == 1)
{
scanf("%d %d",&l,&r);
printf("%lld\n",Summa(1,1,2*n,start-1+l,start-1+r));
} else
{
scanf("%d",&v[--start]);
update(1,1,2*n,start,v[start]);
}
}
return 0;
}