Artifact 5a7c5bc1ec0fdf3078ab4ba75a3c529f9dbc0d2d
//-------------------------------------------------------------
// 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;
}
}
};