//-------------------------------------------------------------
// Fenwick Tree
//   O(log N) per each operation
//
// Verified by
//   - SRM424 Div1 LV3
//   - TCO12 R2C LV2
//-------------------------------------------------------------

template<typename T=LL>
struct FenwickTree
{
	vector<T> x;
	FenwickTree(size_t n) : x(n) {}

	void incr( int k, const T& a ) { // z[k] += a;
		for(; k < x.size(); k|=k+1)
			x[k] += a;
	}
	T sum(int i, int j) { // Sigma z[i,j) excl.
		return sum_impl(j-1) - sum_impl(i-1);
	}
	T sum_impl(int j) { // Sigma z[0,j] incl.
		T v = T();
		for(; j>=0; j=(j&(j+1))-1)
			v += x[j];
		return v;
	}
};
