Pagini recente » Concursuri Virtuale | Cod sursa (job #1549606)
#include <iostream>
#include <cstdio>
using namespace std;
long long int A[150000][1500],i,j,k,n,m,p,poz,val,s,t;
int main()
{
freopen("datorii.in","r",stdin);
freopen("datorii.out","w",stdout);
scanf("%lli %lli",&n,&m);
for (i=0;i<n;i++)
{
scanf("%lli",&A[0][i]);
}
k=n/2;
for (i=1;(1<<i)<n;i++)
{
for (j=0;j<k;j++)
{
A[i][j]=A[i-1][j*2]+A[i-1][j*2+1];
}
k>>=1;
}
/* for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
cout<<A[i][j]<<" ";
}
cout<<'\n';
}
cout<<'\n';
*/
for (i=1;i<=m;i++)
{
scanf("%lli %lli %lli",&p,&poz,&val);
poz--;
if (p==0)
{
j=0;
while (A[j][poz])
{
A[j][poz]-=val;
j++;
poz>>=1;
}
}
else
{
s=0;
val--;
while (poz<=val)
{
j=0;
t=poz;
while ((t+(1<<(j+1)))<val&&t%2==0)
{
j++;
t>>=1;
}
s+=A[j][t];
poz+=1<<j;
// cout<<s<<" "<<poz<<" ";
}
cout<<s<<'\n';
}
}
/* for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
cout<<A[i][j]<<" ";
}
cout<<'\n';
}
*/
}