Cod sursa(job #3373935)

Utilizator MateiDiaconuDiaconu Matei Stefan MateiDiaconu Data 8 noiembrie 2026 11:34:42
Problema Datorii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <iostream>

using namespace std;

#define MAXN 15000

int v[MAXN];
int aint[2 * MAXN];

inline int leftChild(int node){
    return node + 1;
}
inline int rightChild(int node, int nleft, int mid){
    return node + 2 * (mid - nleft + 1);
}

void build(int node, int nleft, int nright){
    if(nleft == nright){
        aint[node] = v[nleft];
        return;
    }

    int mid = (nleft + nright) / 2;

    build(leftChild(node), nleft, mid);
    build(rightChild(node, nleft, mid), mid + 1, nright);
    aint[node] = aint[leftChild(node)] + aint[rightChild(node, nleft, mid)];
}

int query(int node, int nleft, int nright, int qleft, int qright){
    if(qleft <= nleft && qright >= nright){
        return aint[node];
    }

    int rez = 0, mid = (nleft + nright) / 2;

    if(qleft <= mid){
        rez += query(leftChild(node), nleft, mid, qleft, qright);
    }
    if(qright > mid){
        rez += query(rightChild(node, nleft, mid), mid + 1, nright, qleft, qright);
    }
    return rez;
}

void update(int node, int nleft, int nright, int pos, int val){
    aint[node] -= val;

    if(nleft == nright){
        return;
    }

    int mid = (nleft + nright) / 2;

    if(pos <= mid){
        update(leftChild(node), nleft, mid, pos, val);
    }
    else{
        update(rightChild(node, nleft, mid), mid + 1, nright, pos, val);
    }
}

int main() {
    FILE *fin, *fout;
    fin = fopen("datorii.in", "r");
    fout = fopen("datorii.out", "w");

    int n, m, i, op, a, b;

    fscanf(fin, "%d%d", &n, &m);

    for(i = 0; i < n; i++){
        fscanf(fin, "%d", &v[i]);
    }

    build(0, 0, n - 1);

    for(i = 0; i < m; i++){
        fscanf(fin, "%d%d%d", &op, &a, &b);

        if(op == 0){
            update(0, 0, n - 1, a - 1, b);
        }
        else{
            fprintf(fout, "%d\n", query(0, 0, n - 1, a - 1, b - 1));
        }
    }

    fclose(fin);
    fclose(fout);
    return 0;
}