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
23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        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;
23dfcca431 2011-02-23        kinaba: 	FenwickTree(size_t n, const T& v = T()) : x(n, v) {}
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: 	}
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	T sum(int i, int j) { // z[i]+...+z[j] : inclusive
23dfcca431 2011-02-23        kinaba: 		if(i)
23dfcca431 2011-02-23        kinaba: 			return sum(0, j) - sum(0, i-1);
23dfcca431 2011-02-23        kinaba: 		else {
23dfcca431 2011-02-23        kinaba: 			T v = T();
23dfcca431 2011-02-23        kinaba: 			for(; j>=0; j=(j&(j+1))-1)
23dfcca431 2011-02-23        kinaba: 				v += x[j];
23dfcca431 2011-02-23        kinaba: 			return v;
23dfcca431 2011-02-23        kinaba: 		}
23dfcca431 2011-02-23        kinaba: 	}
23dfcca431 2011-02-23        kinaba: };