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

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

	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) { // z[i]+...+z[j] : inclusive
		if(i)
			return sum(0, j) - sum(0, i-1);
		else {
			T v = T();
			for(; j>=0; j=(j&(j+1))-1)
				v += x[j];
			return v;
		}
	}
};
