4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: // Fenwick Tree
4fd800b3a8 2011-02-23        kinaba: //   O(log N) per each operation
4fd800b3a8 2011-02-23        kinaba: //
4fd800b3a8 2011-02-23        kinaba: // Verified by
4fd800b3a8 2011-02-23        kinaba: //   - SRM424 Div1 LV3
4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<typename T = LL>
4fd800b3a8 2011-02-23        kinaba: struct FenwickTree
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	vector<T> x;
4fd800b3a8 2011-02-23        kinaba: 	FenwickTree(size_t n, const T& v = T()) : x(n, v) {}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	void incr( int k, const T& a ) { // z[k] += a;
4fd800b3a8 2011-02-23        kinaba: 		for(; k < x.size(); k|=k+1)
4fd800b3a8 2011-02-23        kinaba: 			x[k] += a;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	T sum(int i, int j) { // z[i]+...+z[j] : inclusive
4fd800b3a8 2011-02-23        kinaba: 		if(i)
4fd800b3a8 2011-02-23        kinaba: 			return sum(0, j) - sum(0, i-1);
4fd800b3a8 2011-02-23        kinaba: 		else {
4fd800b3a8 2011-02-23        kinaba: 			T v = T();
4fd800b3a8 2011-02-23        kinaba: 			for(; j>=0; j=(j&(j+1))-1)
4fd800b3a8 2011-02-23        kinaba: 				v += x[j];
4fd800b3a8 2011-02-23        kinaba: 			return v;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };