Cod sursa(job #1100580)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 7 februarie 2014 00:06:48
Problema Arbori indexati binar Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
using namespace std;
int aib[100005],i,j,n,m,op,a,b;

void update(int poz, int val) {
      while (poz<=n) { aib[poz]+=val; poz+=(poz&(-poz)); }
}

int suma(int poz) {
    int rez=0;
    while (poz>=1) { rez+=aib[poz]; poz-=(poz&(-poz)); }
    return(rez);
}

int main(void) {
    ifstream fin("aib.in");
    ofstream fout("aib.out");
    fin>>n>>m;
    for (i=1; i<=n; ++i) {
                fin>>a;
                update(i,a);
                }
    
    for (i=1; i<=m; ++i) {
        fin>>op;
        if (op==0) {
                   fin>>a>>b;
                   update(a,b);
                   }
        else if (op==1){
                fin>>a>>b;
                fout<<suma(b)-suma(a-1)<<"\n";
                }
        else {
             fin>>a;
             int l=1, r=n, mid;
             bool ok=0;
             while (l<=r) {
                    mid=(l+r)/2;
                    int s=suma(mid);
                    if (s==a) { ok=1; break; }
                      else if (s>a) r=mid-1;
                       else l=mid+1;
                     }
             if (ok) fout<<mid<<"\n"; else fout<<"-1\n";
             }
      }
      
  return(0);
}