This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// 0-indexed Binary Indexed Tree (BIT) // Verified: AOJ DSL_2_B: Range Sum Query (intのみ) template <typename T> struct zeroIndexedBIT{ private: vector<T> array; int n; public: // 初期化 (適当) zeroIndexedBIT() : array(10, 0), n(10) {} zeroIndexedBIT(int _n) : array(_n, 0), n(_n) {} // 他のクラスで BIT を呼び出すときに便利なので作った void resize(int _n) { array.resize(_n); n = _n; } // 0番目から i番目までの累積和を求める T sum(int i) { T s = 0; for(int k=i; k>=0; k = (k&(k+1)) - 1) s += array[k]; return s; } // [i, j] の要素の総和 T sum(int i, int j) { T ret_i = sum(i-1); T ret_j = sum(j); return ret_j - ret_i; } // i 番目に 要素 x を追加 void add(int i, T x) { for(int k=i; k<n; k |= k+1) array[k] += x; } };
#line 1 "structure/strc_005_bit_zero_indexed.cpp" // 0-indexed Binary Indexed Tree (BIT) // Verified: AOJ DSL_2_B: Range Sum Query (intのみ) template <typename T> struct zeroIndexedBIT{ private: vector<T> array; int n; public: // 初期化 (適当) zeroIndexedBIT() : array(10, 0), n(10) {} zeroIndexedBIT(int _n) : array(_n, 0), n(_n) {} // 他のクラスで BIT を呼び出すときに便利なので作った void resize(int _n) { array.resize(_n); n = _n; } // 0番目から i番目までの累積和を求める T sum(int i) { T s = 0; for(int k=i; k>=0; k = (k&(k+1)) - 1) s += array[k]; return s; } // [i, j] の要素の総和 T sum(int i, int j) { T ret_i = sum(i-1); T ret_j = sum(j); return ret_j - ret_i; } // i 番目に 要素 x を追加 void add(int i, T x) { for(int k=i; k<n; k |= k+1) array[k] += x; } };