Differences From Artifact [5a7c5bc1ec0fdf30]:
- 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]
To Artifact [0057b5a349c30181]:
- File
lib/dataStructure/fenwickTree.cpp
- 2012-06-07 14:24:24 - part of checkin [34dd53bac9] on branch trunk - TCO12-2C (user: kinaba) [annotate]
1 1 //-------------------------------------------------------------
2 2 // Fenwick Tree
3 3 // O(log N) per each operation
4 4 //
5 5 // Verified by
6 6 // - SRM424 Div1 LV3
7 +// - TCO12 R2C LV2
7 8 //-------------------------------------------------------------
8 9
9 -template<typename T = LL>
10 +template<typename T=LL>
10 11 struct FenwickTree
11 12 {
12 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 16 void incr( int k, const T& a ) { // z[k] += a;
16 17 for(; k < x.size(); k|=k+1)
17 18 x[k] += a;
18 19 }
19 -
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 - else {
24 - T v = T();
25 - for(; j>=0; j=(j&(j+1))-1)
26 - v += x[j];
27 - return v;
28 - }
20 + T sum(int i, int j) { // Sigma z[i,j) excl.
21 + return sum_impl(j-1) - sum_impl(i-1);
22 + }
23 + T sum_impl(int j) { // Sigma z[0,j] incl.
24 + T v = T();
25 + for(; j>=0; j=(j&(j+1))-1)
26 + v += x[j];
27 + return v;
29 28 }
30 29 };