Artifact 0057b5a349c301818429793e89ebe0fd539d7f0e
//-------------------------------------------------------------
// 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;
}
};