# Cod sursa(job #2592337)

Utilizator Data 1 aprilie 2020 16:29:45 Datorii 40 cpp-64 done Arhiva de probleme 1.29 kb
#include <fstream>

using namespace std;

ifstream cin ("datorii.in");
ofstream cout ("datorii.out");

const int MAX = 1 << 16;

int t[MAX], a, b, poz, val;

void actualizare(int p, int st, int dr)
{
if(st == dr)
{
t[p] += val;
return;
}
int m = (st + dr) / 2;
if(poz <= m)
{
actualizare(2 * p, st, m);
}
else
{
actualizare(2* p + 1, m + 1, dr);
}
t[p] =t[2 * p]+t[2 * p + 1];
}

int interogare(int p, int st, int dr)
{
if(a <= st && dr <= b)
{
return t[p];
}
int m = (st + dr) / 2;
int maxst = 0;
int maxdr = 0;
if(a <= m)
{
maxst = interogare(2 * p, st, m);
}
if(b > m)
{
maxdr = interogare(2 * p + 1, m + 1, dr);
}
return maxst+maxdr;
}

int main()
{
int n, m, cod;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin >> val;

poz = i;
actualizare(1,1,n);
}
for(int i=1; i<=m; i++)
{
cin>>cod;
if(cod==1)
{
cin >>a>>b;
cout<<interogare(1, 1, n)<<"\n";
}
else
{
cin>>poz>>val;
val=-val;
actualizare(1,1,n);
}
}
return 0;
}