# Cod sursa(job #283668)

Utilizator Data 19 martie 2009 15:08:34 Arbori indexati binar 100 cpp done Arhiva educationala 1.58 kb
``````#include <cstdio>

using namespace std;

#define FIN "aib.in"
#define FOUT "aib.out"
#define MAX_N 100015

int N, M;
int A[MAX_N];
int aib[MAX_N];

scanf("%d %d", &N, &M);
for (int i = 1; i <= N; ++i)
scanf("%d", &A[i]);
}

void update(int pos, int val) {
while (pos <= N) {
aib[pos] += val;
pos += (pos ^ (pos - 1)) & pos;
}
}

int query1(int pos) {
int ret = 0;

while (pos > 0) {
ret += aib[pos];
pos -= (pos ^ (pos - 1)) & pos;
}

return ret;
}

int query2(int val) {
int step, pos, tmp = val;
for (step = 1; (step << 1) <= N; step <<= 1);
for (pos = 0; step; step >>= 1)
if (pos + step <= N && aib[pos + step] < tmp) {
pos += step;
tmp -= aib[pos];
}
++pos;
if (1 <= pos && pos <= N && query1(pos) == val)
return pos;
else
return -1;
}

void solve() {
for (int i = 1; i <= N; ++i)
update(i, A[i]);

for (int i = 1; i <= M; ++i) {
int tip, a, b;
scanf("%d", &tip);
if (tip == 0) {
scanf("%d %d", &a, &b);
update(a, b);
A[a] += b;
}
else if (tip == 1) {
scanf("%d %d", &a, &b);
printf("%d\n", query1(b) - query1(a - 1));
}
else {
scanf("%d", &a);
printf("%d\n", query2(a));
}
}
}

int main() {
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);