1 //------------------------------------------------------------- 1 //------------------------------------------------------------- 2 // Fenwick Tree 2 // Fenwick Tree 3 // O(log N) per each operation 3 // O(log N) per each operation 4 // 4 // 5 // Verified by 5 // Verified by 6 // - SRM424 Div1 LV3 6 // - SRM424 Div1 LV3 > 7 // - TCO12 R2C LV2 7 //------------------------------------------------------------- 8 //------------------------------------------------------------- 8 9 9 template<typename T = LL> | 10 template<typename T=LL> 10 struct FenwickTree 11 struct FenwickTree 11 { 12 { 12 vector<T> x; 13 vector<T> x; 13 FenwickTree(size_t n, const T& v = T()) : x(n, v) {} | 14 FenwickTree(size_t n) : x(n) {} 14 15 15 void incr( int k, const T& a ) { // z[k] += a; 16 void incr( int k, const T& a ) { // z[k] += a; 16 for(; k < x.size(); k|=k+1) 17 for(; k < x.size(); k|=k+1) 17 x[k] += a; 18 x[k] += a; 18 } 19 } > 20 T sum(int i, int j) { // Sigma z[i,j) excl. > 21 return sum_impl(j-1) - sum_impl(i-1); 19 | 22 } 20 T sum(int i, int j) { // z[i]+...+z[j] : inclusive < 21 if(i) < 22 return sum(0, j) - sum(0, i-1); | 23 T sum_impl(int j) { // Sigma z[0,j] incl. 23 else { < 24 T v = T(); | 24 T v = T(); 25 for(; j>=0; j=(j&(j+1))-1) | 25 for(; j>=0; j=(j&(j+1))-1) 26 v += x[j]; | 26 v += x[j]; 27 return v; | 27 return v; 28 } < 29 } 28 } 30 }; 29 };