binary indexed tree

//
// BIT.h
//
// binary indexed tree
//
// INPUT: tree
//
// OUTPUT: query
//
// Time: O(log(2N))
//	
//
#include <algorithm>
#include <vector>
#include <functional>

using namespace std;
template<typename Te, typename Tv>
class bit {
private:
	vector<Tv> raw;
	size_t size;

public:
	bit(const vector<Tv>& vector)
	{
		this->size = vector.size() + 1;
		this->raw.assign(this->size, 0);
		for (int i = 0; i < vector.size(); i++)
			this->update(i, vector[i]);
	}
	void update(Te index, const Tv& value)
	{
		index++;
		while (index <= this->size)
		{
			this->raw[index] += value;
			index += index & (-index);
		}
	}
	Tv sum(Te index)
	{
		index++;
		int result = 0;
		while (index)
		{
			result += this->raw[index];
			index -= index & (-index);
		}
		return result;
	}
	~bit() {}
};