Binary Indexed Tree

BIT.h

#pragma once

#include <vector>

template<class T>
class BIT {
public:
	explicit BIT(size_t N=1) : _bit(N) {}
	void add(size_t i, T val) {
		while (i < _bit.size()){
			_bit[i] += val;
			i += i & -i;
		}
	}
	T sum(size_t i) {
		T ret = 0;
		while(i>0){
			ret += _bit[i];
			i &= (i - 1);
		}
		return ret;
	}
private:
	std::vector<T> _bit;
};