Cod sursa(job #2176067)

Utilizator SenibelanMales Sebastian Senibelan Data 16 martie 2018 20:44:05
Problema Arbori indexati binar Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>

using namespace std;

ifstream in("aib.in");
ofstream out("aib.out");

const int NMAX = 100005;
int N, M;
int V[NMAX], AIB[NMAX];

int zeros(int x){
    return (((x ^ (x - 1)) & x));
}

void Update(int position, int number){
    for(int i = position; i <= N; i += zeros(i))
        AIB[i] += number;
}

int Compute(int position){
    int sum = 0;
    for(int i = position; i >= 1; i -= zeros(i))
        sum += AIB[i];
    return sum;
}

int Search(int k){
    int i;
    for(i = 1; i < N; i <<= 1);

    for(int power = i, add = 0; power >= 1; power >>= 1){
        if(power + add <= N)
            if(AIB[power + add] <= k){
                add += power;
                k -= AIB[add];
                if(!k) return add;
            }
    }
    return -1;
}


void Read(){
    in >> N >> M;
    for(int i = 1; i <= N; ++i){
        int nr;
        in >> nr;
        Update(i, nr);
    }
}


void SolveAndPrint(){
    while(M){
        int op, a;
        in >> op >> a;
        if(op != 2){
            int b;
            in >> b;
            if(op == 0)
                Update(a, b);
            else
                out << Compute(b) - Compute(a - 1) << "\n";
        }
        else
            out << Search(a) << "\n";
        M--;
    }
}

int main(){
    Read();
    SolveAndPrint();
    return 0;
}