23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: // Fenwick Tree
23dfcca431 2011-02-23        kinaba: //   O(log N) per each operation
23dfcca431 2011-02-23        kinaba: //
23dfcca431 2011-02-23        kinaba: // Verified by
23dfcca431 2011-02-23        kinaba: //   - SRM424 Div1 LV3
34dd53bac9 2012-06-07        kinaba: //   - TCO12 R2C LV2
23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: 
34dd53bac9 2012-06-07        kinaba: template<typename T=LL>
23dfcca431 2011-02-23        kinaba: struct FenwickTree
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	vector<T> x;
34dd53bac9 2012-06-07        kinaba: 	FenwickTree(size_t n) : x(n) {}
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	void incr( int k, const T& a ) { // z[k] += a;
23dfcca431 2011-02-23        kinaba: 		for(; k < x.size(); k|=k+1)
23dfcca431 2011-02-23        kinaba: 			x[k] += a;
23dfcca431 2011-02-23        kinaba: 	}
34dd53bac9 2012-06-07        kinaba: 	T sum(int i, int j) { // Sigma z[i,j) excl.
34dd53bac9 2012-06-07        kinaba: 		return sum_impl(j-1) - sum_impl(i-1);
34dd53bac9 2012-06-07        kinaba: 	}
34dd53bac9 2012-06-07        kinaba: 	T sum_impl(int j) { // Sigma z[0,j] incl.
34dd53bac9 2012-06-07        kinaba: 		T v = T();
34dd53bac9 2012-06-07        kinaba: 		for(; j>=0; j=(j&(j+1))-1)
34dd53bac9 2012-06-07        kinaba: 			v += x[j];
34dd53bac9 2012-06-07        kinaba: 		return v;
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: };