Cod sursa(job #2612332)

Utilizator CryshanaGanea Carina Cryshana Data 8 mai 2020 21:00:27
Problema Datorii Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

struct node{
    node* st = nullptr;
    node* dr = nullptr;
    int a, b, val;
};

inline void constr( node* p, int a, int b, int* v) {
    if( a < b ){
        p->st = new node;
        constr( p->st, a, ( a + b ) / 2, v);
        p->dr = new node;
        constr ( p->dr, (a+b)/2 + 1, b, v);
        p->val = p->st->val + p->dr->val;
    } else{
        p->val = v[a];
    }
    p->a = a;
    p->b = b;
}

inline void schimbare_val(node* p, int a, int val){
    if( p -> a != p -> b ){
        if (a <= ( p -> a + p-> b) / 2)
            schimbare_val( p-> st, a, val);
        else
            schimbare_val(p->dr, a, val);
        p-> val = p -> st-> val + p-> dr-> val;
    } else{
        p-> val -= val;
    }
}

inline int interogare( node * p, int a, int b ){
    if( p-> a == a && p-> b == b)
        return p-> val;
    int mij = (p->a + p->b) / 2;
    if( mij >= b){
        return interogare( p->st, a, b);
    }
    if( mij < a){
        return interogare( p->dr, a, b);
    }
    return interogare( p->st, a, mij)+ interogare( p->dr, mij+1, b);
}

/*void distrug( node * p){
    if( p-> st != nullptr)
        distrug( p->st);
    if( p-> dr != nullptr)
        distrug( p->dr);
    delete(p);
}*/

int main()
{
    ifstream in ("datorii.in");
    ofstream out ("datorii.out");
    int N, M;
    in >> N >> M;
    int v[N];
    node * arb = new node;
    for( int i = 0; i < N; i++){
        in >> v[i];
    }
    int q, a, b;
    constr( arb, 0, N-1, v);
    while( M != 0){
        in >> q >> a >> b;
        if( q == 0){
            schimbare_val ( arb, a-1, b);
        }
        else{
            out << interogare(arb, a-1, b-1) << "\n";
        }
        M--;
    }
    //distrug(arb);
    return 0;
}