Cod sursa(job #503936)
#include <fstream>
using namespace std;
ifstream fin("datorii.in");
ofstream fout("datorii.out");
const int maxn=15001;
int i,N,M,cod,a,b,S,A[maxn],Arb[4*maxn];
void update(int k, int st, int dr)
{
if(st==dr)
{
Arb[k]=A[st];
return;
}
int m=st+(dr-st)/2;
if(a<=m) update(2*k,st,m);
else update(2*k+1,m+1,dr);
Arb[k]=Arb[2*k]+Arb[2*k+1];
}
void caut(int k, int st, int dr)
{
if(a<=st && dr<=b)
{
S+=Arb[k];
return;
}
int m=st+(dr-st)/2;
if(a<=m) caut(2*k,st,m);
if(b>m) caut(2*k+1,m+1,dr);
}
int main()
{
fin >> N >> M;
for(i=1;i<=N;i++)
{
fin >> A[i];
a=i; b=A[i];
update(1,1,N);
}
for(i=1;i<=M;i++)
{
fin >> cod >> a >> b;
if(cod==0)
{
A[a]-=b;
update(1,1,N);
}
else // cod == 1
{
S=0;
caut(1,1,N);
fout << S << endl;
}
}
//for(i=1;i<=N;i++) fout << A[i] << " ";
}