Cod sursa(job #2427497)

Utilizator PrekzursilAndrei Visalon Prekzursil Data 31 mai 2019 22:50:47
Problema Datorii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
using namespace std;
ifstream in("datorii.in");
ofstream out("datorii.out");
int aib[100010], n, m;
int query (int p)
{
    int s=0;
    while (p>0)
    {
        s+=aib[p];
        p-=p&(-p);
    }
    return s;
}
void update (int p, int val)
{
    while (p<=n)
    {
        aib[p]+=val;
        p+=p&(-p);
    }
}
int caut(int val)
{
    int r=0, pas=1<<16;
    if (query(n) < val)
        return -1;
    while (pas != 0)
    {
        if (r + pas <= n && query(r + pas) < val)
            r+=pas;
        pas/=2;
    }
    if (query(r+1) != val)
        r=-1;
    else
        r++;
    return r;
}
int main()
{
    int a, b, cod, nr;
    in>>n>>m;
    for (int i=1; i<=n; i++)
    {
        in>>nr;
        update (i, nr);
    }
    for (int i=1; i<=m; i++)
    {
        in>>cod;
        if (cod==0)
        {
            in>>a>>b;
            update (a, -b);
        }
        if (cod==1)
        {
            in>>a>>b;
            out<<query(b)-query(a-1)<<"\n";
        }
    }
    return 0;
}