Cod sursa(job #1068578)

Utilizator andy1496Casu-Pop Andrei andy1496 Data 28 decembrie 2013 15:15:09
Problema Arbori indexati binar Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <cstdio>
using namespace std;

int n, m, j, ind;
int op;
int a, s, aib[100009], val;

int zeros(int poz) {

	return (poz ^ (poz - 1)) & poz;

}

void add(int poz, int q) {
	int i;
	for (i = poz; i <= n; i += zeros(i)) {
		aib[i] += q;
	}
}

int sum(int poz) {

	int i;
	int v = 0;
	for (i = poz; i > 0; i -= zeros(i)) {
		v += aib[i];
	}
	return v;
}

int search(int val) {

	int st = 1, dr = n, mid, sums;
	while (st <= dr) {
		mid = (st + dr) >> 1;
		sums = sum(mid);
		if (sums == val) return mid;
		else {
			if (sums > val) dr = mid - 1;
			else st = mid + 1;
		}
	}


	return -1;
}

int main() {

	freopen("aib.in", "r", stdin);
	freopen("aib.out", "w", stdout);


	scanf("%d %d", &n, &m);

	for (j = 1; j <= n; j++) {
		scanf("%d", &a);
		add(j, a);
	}

	for (j = 1; j <= m; j++) {

		scanf("%d %d", &op, &ind);

		if (op == 0) {
			scanf("%d", &val);
			add(ind, val);
		}

		else {
			if (op == 1) { 
				scanf("%d", &val);
				printf("%d\n", sum(val) - sum(ind - 1));

			}
			else printf("%d\n", search(ind));
		}

	}


	return 0;
}