Cod sursa(job #969958)

Utilizator Cezar_16Cezar Ghimbas Cezar_16 Data 5 iulie 2013 19:09:53
Problema Arbori indexati binar Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.03 kb
#include<stdio.h>
#include<iostream>
#include<cmath>

template <typename T>
class BinaryIndexedTree {
	public:
		BinaryIndexedTree(int);
		void insert(T,int);
		void modify(int,T);
		T interval_sum(int,int);
		int pos_with_sum(T);
		void display();
		
		int binary_search(int);
		int nr_zeroes(int);
		int Sum(int);
		
	private:
		T *bit;
		int size;
};

template <typename T>
BinaryIndexedTree<T>::BinaryIndexedTree(int d) {
	bit = new T[d];
	size = 0;
}

template<typename T>
void BinaryIndexedTree<T>::insert(T val, int n) {
	size++;
	int copy_s = size;
	while(copy_s <= n) {
		bit[copy_s] += val;
		copy_s += 1<<nr_zeroes(copy_s);
	}
}

template<typename T>
void BinaryIndexedTree<T>::modify(int p, T val) {
	bit[p] += val;
	while(p <= size) {
		p += 1<<nr_zeroes(p);
		if(p <= size)
			bit[p] += val;
	}
}

template<typename T>
T BinaryIndexedTree<T>::interval_sum(int st, int dr) {
	return Sum(dr) - Sum(st - 1);
}

template<typename T>
int BinaryIndexedTree<T>::nr_zeroes(int p) {
	int k = 0;
	for(;(p & (1 << k)) == 0; k++);
	return k;
		
}

template<typename T>
int BinaryIndexedTree<T>::Sum(int p) {
	T s = 0;
	for(; p > 0; p -= 1<<nr_zeroes(p))
		s += bit[p];
	return s;
}

template<typename T>
int BinaryIndexedTree<T>::binary_search(int val) {
    int i, step;
    for (step = 1; step < size; step <<= 1);
    for (i = 1; step; step >>= 1)
        if (i + step <= size && Sum(i + step) <= val)
           i += step;
    if(Sum(i + step) == val)
    	return i;
    return -1;
}


int main() {
	int cod, a, b, N, M, x;
	freopen("aib9.in","r",stdin);
	freopen("aib.out","w",stdout);
	
	scanf("%d %d", &N, &M);
	BinaryIndexedTree<int> bit(N);
	for(int i = 0; i < N; i++) {
		scanf("%d", &x);
		bit.insert(x,N);
	}
	for(int i = 0; i < M; i++) {
	
		scanf("%d", &cod);
		
		if(cod == 0) {
			scanf("%d", &a);
			scanf("%d", &b);
			bit.modify(a,b);
		}
		
		else if(cod == 1) {
			scanf("%d", &a);
			scanf("%d", &b);
			printf("%d\n", bit.interval_sum(a,b));
		}
		
		else if(cod == 2) {
			scanf("%d", &a);
			printf("%d\n", bit.binary_search(a));
		}
	}
	
	return 0;
}