Cod sursa(job #188499)

Utilizator c_iulyanCretu Iulian c_iulyan Data 8 mai 2008 19:02:15
Problema Arbori indexati binar Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include<cstdio>
long n,m,t[100005];
long long q;
using namespace std;

void upd(long i,long x)
{
for(;i<=n;i+=i&-i)
   t[i]+=x;
}

long long ask(long i)
{
long long s=0;
for(;i;i-=i&-i)
   s+=t[i];
return s;
}

void binsh(long long x)
{
long l=1,r=n;
while(l<=r)
   {
   long m=(l+r)/2;
   if(x==ask(m))
      {
      printf("%ld\n",m);
      return;
      }
   if(x<ask(m))
      r=m-1;
   else
      l=m+1;
   }
}

void rd()
{
scanf("%ld%ld",&n,&m);
long i,x,y,p;
for(i=1;i<=n;i++)
   {
   scanf("%ld",&x);
   upd(i,x);
   }

for(i=1;i<=m;i++)
   {
   scanf("%ld",&p);
   if(p==0)
      {
      scanf("%ld%ld",&x,&y);
      upd(x,y);
      }
   else if(p==1)
      {
      scanf("%ld%ld",&x,&y);
      printf("%lld\n",ask(y)-ask(x-1));
      }
   else
      {
      scanf("%lld",&q);
      binsh(q);
      }
   }
}

int main()
{
freopen("aib.in","r",stdin);
freopen("aib.out","w",stdout);

rd();

return 0;
}