# Cod sursa(job #928632)

Utilizator Data 26 martie 2013 16:26:16 Datorii 100 cpp done Arhiva de probleme 1.27 kb
``````#include <fstream>
using namespace std;

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

const int INF  = (1<<29);

int n,x[15010],i,j,a[40100],m,op,p,q;

int build(int i, int li, int ls) {
if(li > ls)
return -INF;

if(li == ls) {
a[i] = x[li];
return a[i];
}

a[i] =
build(2*i  , li,         (li+ls)/2 )
+ build(2*i+1, (li+ls)/2+1,  ls        )
;
return a[i];
}

int chg(int i, int li, int ls, int v, int pos) {
if(pos < li || pos > ls) {
return a[i];
}
if(li == ls && li == pos) {
a[i] -= v;
return a[i];
}
return a[i] = chg(2*i, li, (li+ls)/2, v, pos) + chg(2*i+1, (li+ls)/2+1, ls, v, pos);
}

int query(int i, int li, int ls, int qi, int qs) {
if(qs < li || qi > ls)
return 0;
if(li >= qi && ls <= qs)
return a[i];
return query(2*i, li, (li+ls)/2, qi, qs) + query(2*i+1, (li+ls)/2+1, ls, qi, qs);
}

int main() {
in>>n>>m;
for(i=1; i<=n; i++) {
in>>x[i];
}
build(1, 1, n);
for(i=1; i<=m; i++) {
in>>op>>p>>q;
if(op == 1) {
out<<query(1, 1, n, p, q)<<'\n';
} else {
chg(1, 1, n, q, p);
}
}
return 0;
}``````