Cod sursa(job #461360)

Utilizator the1dragonIonita Alexandru the1dragon Data 6 iunie 2010 15:40:24
Problema Arbori indexati binar Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<stdio.h>
#define N_MAX 102400

int arb[2*N_MAX];
int n, m, n2;

int interogare2(int val, int st, int dr, int poz)
{
	if (arb[poz] < val)
		return -1;
	if (st==dr)
	{
		if (arb[poz] == val)
			return st;
		else 
			return -1;
	}
	if (arb[poz*2] >= val)
		return interogare2(val, st, (st+dr)/2, poz*2);
	else
		return interogare2(val-arb[poz*2], (st+dr)/2 +1, dr, poz*2+1);
}

int interogare(int a, int b, int st, int dr, int poz)
{
	if ((a<= st) && (dr <= b))
		return arb[poz];
	if ((b < st) || (a > dr))
		return 0;
	return interogare(a, b, st, (st+dr)/2, poz*2) + interogare(a, b, (st+dr)/2+1, dr, poz*2+1);
}

void adauga(int unde, int val)
{
	arb[unde]+=val;
	if (unde > 1)
		adauga(unde/2, val);
}

inline int pozitie(int unde)
{
	return n2+unde-1;
}

int main()
{
	freopen("aib.in", "r", stdin);
	freopen("aib.out", "w", stdout);
	
	int i, a, b, tip;
	scanf("%d %d", &n, &m);
	n2=1;
	while (n2 < n)
	{
		n2 = n2 << 1;
	}
	for (i=1; i<=n; i++)
	{
		scanf("%d", &a);
		adauga(pozitie(i), a);
	}
	for (i=1; i<=m; i++)
	{
		scanf("%d", &tip);
		switch (tip)
		{
			case 0:
				scanf("%d %d", &a, &b);
				adauga(pozitie(a), b);
				break;
			case 1:
				scanf("%d %d", &a, &b);
				printf("%d\n", interogare(a, b, 1, n2, 1));
				break;
			case 2:
				scanf("%d", &a);
				printf("%d\n", interogare2(a, 1, n2, 1));
				break;
		}
	}
	
	fclose(stdout);
	return 0;	
}