2941. Dima
and array
Mom gave Dima an array of length n. This array is not ordinary – it
is special. Dima can choose numbers i
and d (1 ≤ i ≤ n, -1000
≤ d ≤ 1000) and magically assign the value d to the element with index i.
While Dima is playing with the array, his mom occasionally
asks him questions: what is the sum of the array elements with indices from f to t inclusive? Dima answers these
questions effortlessly. Can you?
Input. The first
line contains two integers n and q (1 ≤ n ≤ 5·105, 1 ≤ q ≤ 105) – the number of elements in the array and
the total number of operations and
queries.
The
second line contains n integers a1, a2, ..., an
(-1000 ≤ ai ≤
1000) – the
initial state of the array.
Each
of the following lines contains either an operation or a query:
·
If a line begins with the symbol ‘=’,
it denotes an assignment operation, followed by the integers i and d with the constraints specified above.
·
If a line begins with the symbol ‘?’,
it denotes a query, followed by the integers f and t (1 ≤ f, t
≤ n).
Output. For each
query, print the sum of the array elements with indices from f to t
inclusive. Print each answer on a separate line.
|
Sample
input |
Sample
output |
|
3 3 1 2 3 ? 1 3 = 3 2 ? 1 3 |
6 5 |
SOLUTION
data structures – segment
tree
Algorithm analysis
To
solve this problem, it is necessary to implement a segment tree that supports
single element
updates and range sum queries.
Example
Let’s simulate the
queries given
in the example.
Algorithm implementation
Store the
segment tree in the vector SegTree of size 4 * MAX, where MAX is the
maximum number of elements in the array.
#define MAX 500000
vector<int>
SegTree(4*MAX,0);
The BuildTree function constructs the
segment tree. It takes as parameters the array a, the index of the
current tree vertex v, and the boundaries of the segment lpos and
rpos corresponding to vertex v.
void BuildTree(vector<int>&a, int v, int
lpos, int
rpos)
{
If the vertex v
corresponds to a segment consisting of a single element (lpos = rpos), then we have reached a
leaf of the segment tree. In this case, assign the value alpos to this vertex.
if (lpos == rpos) SegTree[v] = a[lpos];
else
{
Compute the midpoint of
the segment mid = (lpos + rpos)
/ 2.
int mid = (lpos + rpos) / 2;
Split the segment [left; right] into two subsegments: [left; mid] and [mid + 1; right]. After that, recursively build the segment tree for each of
these subsegments.
BuildTree(a, 2*v, lpos, mid);
BuildTree(a, 2*v+1, mid + 1, rpos);
Recompute the sum stored in the current vertex of the segment tree.
SegTree[v] = SegTree[2*v] + SegTree[2*v+1];
}
}
The Update
function assigns the value val to the element with index pos. The
vertex v corresponds to the segment [lpos; rpos].
void Update(int v, int
lpos, int
rpos, int pos, int val)
{
If vertex v
corresponds to a segment consisting of a single element (lpos = rpos), then we have reached a
leaf of the segment tree. In this case, assign the value val to this
vertex.
if (lpos == rpos) SegTree[v] = val;
else
{
int mid = (lpos + rpos) / 2;
if (pos <= mid)
Update (2*v, lpos, mid, pos, val);
else
Update (2*v+1, mid+1, rpos, pos, val);
Recompute the sum stored in the
current vertex of the segment tree.
SegTree[v] = SegTree[2*v] + SegTree[2*v+1];
}
}
The Summa
function returns the sum of the array elements on the segment [left; right]. The vertex v corresponds to the segment [lpos; rpos].
int Summa(int v, int
lpos, int rpos, int left, int right)
{
if (left > right) return 0;
If the segment [left; right] completely
coincides with the segment [lpos; rpos] stored in
vertex v, then the function returns the sum value saved in this
vertex.
if ((left == lpos) && (right == rpos))
return SegTree[v];
Compute the midpoint of the segment mid = (lpos + rpos) / 2.
int mid = (lpos + rpos) / 2;
Split the segment [left; right] into two subsegments: [left; mid] and [mid + 1; right]. Recursively compute the
sums on these subsegments and add the obtained values to get the sum for the
original segment.
return Summa(2*v, lpos, mid, left, min(right,mid)) +
Summa(2*v+1, mid+1, rpos, max(left,mid+1), right);
}
The main part
of the program. Read the input data.
scanf("%d
%d",&n,&q);
v.resize(n+1);
for(i = 1; i <= n; i++)
scanf("%d",&v[i]);
scanf("\n");
Using the data from array v, build the segment
tree.
BuildTree(v,1,1,n);
Process the q queries sequentially. Depending on the type of query, we
either update the value of an element or compute the sum over the specified
range.
for(j = 0; j < q; j++)
{
scanf("%c ",&c);
if (c == '=')
{
scanf("%d %d\n",&i,&d);
Update(1,1,n,i,d);
} else
{
scanf("%d %d\n",&f,&t);
printf("%d\n",Summa(1,1,n,f,t));
}
}
Algorithm
implementation – iostream
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> SegTree;
void BuildTree(vector<int>& 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];
}
}
int 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, int 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<int> v;
int n, q, i, d, p, f, t;
char c;
int main(void)
{
cin >> n >> q;
v.resize(n + 1);
SegTree.resize(4 * n + 1);
for (i = 1; i <= n;
i++)
cin >> v[i];
BuildTree(v, 1, 1, n);
for (i = 0; i < q; i++)
{
cin >> c;
if (c == '=')
{
cin
>> p >> d;
update(1, 1, n, p, d);
}
else
{
cin >> f >> t;
cout << Summa(1, 1, n, f, t) << endl;
}
}
return 0;
}
Algorithm
implementation – class
#include <cstdio>
#include <vector>
#define MAX 500000
using namespace std;
class SegmentTree
{
public:
vector<int> SegTree;
int len;
SegmentTree(int n)
{
len = n;
SegTree.resize(4*n);
}
SegmentTree(vector<int> &v)
{
len = (int) v.size();
SegTree.resize(4*len);
BuildTree(v,1,0,len-1);
}
void BuildTree(vector<int>&a,
int v, int tl, int tr)
{
if (tl == tr) SegTree[v] = a[tl];
else
{
int tm = (tl + tr) / 2;
BuildTree(a, v*2, tl, tm);
BuildTree(a, v*2+1, tm+1, tr);
SegTree[v] = SegTree[v*2] + SegTree[v*2+1];
}
}
int Summa(int Left, int Right)
{
return Summa(1,0,len-1,Left,Right);
}
int Summa(int v, int LeftPos, int
RightPos, int Left, int
Right)
{
if (Left > Right) return 0;
if ((Left == LeftPos) && (Right
== RightPos)) return SegTree[v];
int Middle = (LeftPos + RightPos) / 2;
return Summa(v*2, LeftPos, Middle, Left,
min(Right,Middle)) +
Summa(v*2+1,
Middle+1, RightPos, max(Left,Middle+1), Right);
}
void update(int
Position, int NewValue)
{
update(1,0,len-1,Position,NewValue);
}
void update(int v, int LeftPos, int
RightPos,
int Position, int NewValue)
{
if (LeftPos == RightPos) SegTree[v] =
NewValue;
else
{
int Middle = (LeftPos + RightPos) / 2;
if (Position <= Middle)
update (v*2, LeftPos, Middle, Position, NewValue);
else
update (v*2+1, Middle+1, RightPos, Position, NewValue);
SegTree[v] = SegTree[v*2] + SegTree[v*2+1];
}
}
};
vector<int>
v;
int n, q, i, j, d, f, t;
char c;
int main(void)
{
scanf("%d %d\n",&n,&q);
v.resize(n+1);
for(i = 1; i <= n; i++) scanf("%d",&v[i]); scanf("\n");
SegmentTree s(v);
for(j = 0; j < q; j++)
{
scanf("%c ",&c);
if (c == '=')
{
scanf("%d %d\n",&i,&d);
s.update(i,d);
} else
{
scanf("%d %d\n",&f,&t);
printf("%d\n",s.Summa(f,t));
}
}
return 0;
}
Algorithm
implementation – dynamic memory allocation new / delete
#include <cstdio>
#include <algorithm>
using namespace std;
int *SegTree;
void BuildTree(int *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];
}
}
int 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, int 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];
}
}
int n, q, i, j, d, f, t;
char c;
int main(void)
{
scanf("%d %d\n",&n,&q);
int *v = new int[n+1];
for(i = 1; i <= n; i++)
scanf("%d",&v[i]);
scanf("\n");
SegTree = new int[4*n];
BuildTree(v,1,0,n);
delete[] v;
for(j = 0; j < q; j++)
{
scanf("%c ",&c);
if (c == '=')
{
scanf("%d %d\n",&i,&d);
update(1,0,n,i,d);
} else
{
scanf("%d %d\n",&f,&t);
printf("%d\n",Summa(1,0,n,f,t));
}
}
delete[] SegTree;
return 0;
}