Artifact 5a7c5bc1ec0fdf3078ab4ba75a3c529f9dbc0d2d

• File _lib/dataStructure/fenwickTree.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
• File lib/dataStructure/fenwickTree.cpp
  • 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]

//-------------------------------------------------------------
// 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;
		}
	}
};