Cod sursa(job #2708983)

Utilizator ArkhamKnightyMarco Vraja ArkhamKnighty Data 19 februarie 2021 16:52:25
Problema Datorii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <fstream>
#define NMAX 100001

using namespace std;

ifstream f("datorii.in");
ofstream o("datorii.out");

int a[NMAX];
int t[4 * NMAX  + 66];

int combine(int x, int y)
{
    return x + y;
}

void build(int v, int tl, int tr)
{
    if(tl == tr)
        t[v] = a[tl];

    else
    {
        int tm = (tl + tr) >> 1;

        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
        t[v] = combine(t[2 * v], t[2 * v + 1]);
    }
}

void update(int v, int tl, int tr, int pos, int val)
{
    if(tl == tr)
        t[v] -= val;

    else
    {
        int tm = (tl + tr) >> 1;

        if (pos <= tm)
            update(2 * v, tl, tm, pos, val);
        else
            update(2 * v + 1, tm + 1, tr, pos, val);

        t[v] = combine(t[2*v], t[2*v+1]);
    }
}

int query(int v, int tl, int tr, int l, int r)
{
    if (l == tl && tr == r)
    {
        //o << "AICI " << l << ' ' << r << "  " << t[v] << '\n';
        return t[v];
    }


    int tm = (tl + tr) >> 1;

    if(r <= tm)
        return query(2 * v, tl, tm, l, r);

    else if(tm < l)
        return query(2 * v + 1, tm + 1, tr, l, r);


    return combine ( query(2 * v, tl, tm, l, tm),
                     query(2 * v + 1, tm + 1, tr, tm + 1, r) );



}

int main()
{
    int n, m, q, x, y;
    f >> n >> m;

    for(int i = 1 ; i <= n ; i++)
        f >> a[i];
    build(1, 1, n);


    for(int i = 1 ; i <= m ; i++)
    {
        f >> q >> x >> y;

        if(q)
            o << query(1, 1, n, x, y) << '\n';

        else
            update(1, 1, n, x, y);
    }

    return 0;
}