Cod sursa(job #530683)
#include <stdio.h>
#include <string.h>
#define LSB(x) x&(-x)
int N,M,x,y,i,sw;
int v[100002];
inline void update(int pos,int value)
{
while(pos<=N)
{
v[pos]+=value;
pos+=LSB(pos);
}
}
inline int query(int pos)
{
int sum=0;
while(pos>0)
{
sum+=v[pos];
pos-=LSB(pos);
}
return sum;
}
inline int BS(int sum,int L,int R)
{
int M=(L+R)/2,aux;
if(L<=R)
{
aux=query(M);
if(sum<aux) return BS(sum,L,M);
else
if(sum>aux) return BS(sum,M+1,R);
else return M;
}
else return -1;
}
int main()
{
freopen("aib.in","r",stdin);
freopen("aib.out","w",stdout);
scanf("%d%d",&N,&M);
memset(v,0,sizeof(v));
for(i=1;i<=N;i++)
{
scanf("%d",&x);
update(i,x);
}
for(i=1;i<=M;i++)
{
scanf("%d",&sw);
if(sw==0)
{
scanf("%d%d",&x,&y);
update(x,y);
}
else
if(sw==1)
{
scanf("%d%d",&x,&y);
printf("%d\n",query(y)-query(x-1));
}
else
{
scanf("%d",&x);
printf("%d\n",BS(x,1,N));
}
}
return 0;
}