Cod sursa(job #2396696)

Utilizator Leonard123Mirt Leonard Leonard123 Data 3 aprilie 2019 19:07:03
Problema Arbori indexati binar Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
using namespace std;
#define maxn 100001
ifstream cin("aib.in");
ofstream cout("aib.out");
int N,M,aib[maxn],op,c;

void update(int poz, int val){
    c=0;
    while(poz<=N){
        aib[poz]+=val;
        while(!(poz&(1<<c))) c++;
        poz+=(1<<c);
        c++;
    }
}

int query(int poz){
    int suma=0,c=0;
    while(poz>0){
        suma+=aib[poz];
        while(!(poz&(1<<c))) c++;
        poz-=(1<<c);
        c+=1;
    }
    return suma;
}

int bs(int val){
    int i,step;
    for(step=1; step<N; step<<=1);
    for(i=0; step; step >>=1){
        if(i+step<=N){
            if(val>=aib[i+step]){
                i+=step, val-= aib[i];
                if(!val) return i;
            }
        }
    }
    return -1;
}

void solve(int op){
    int x,y;
    if(op==0){
        cin>>x>>y;
        update(x,y);
    }else if(op==1){
        cin>>x>>y;
        cout<<query(y)-query(x-1)<<'\n';
    }else if(op==2){
        int ok=1;
        cin>>x;
        for(int i=1; i<=N&&ok; i++){
            if(query(i)==x){
                cout<<i<<'\n';
                ok=0;
            }
        }
        if(ok==1)
            cout<<-1<<'\n';
    }
}

int main(){
    int x;
    cin>>N>>M;
    for(int i=1; i<=N; i++){
        cin>>x;
        update(i,x);
    }
    for(int i=1; i<=M; i++){
        cin>>op;
        solve(op);
    }
    return 0;
}