This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// Binary Indexed Tree (BIT) // Verified: AOJ DSL_2_B: Range Sum Query (intのみ) template <typename T> struct BIT{ private: vector<T> array; int n; public: // 初期化 BIT() {} BIT(int _n) : array(_n + 1, 0), n(_n) {} // 1番目から i番目までの累積和を求める T sum(int i) { T s = 0; while(i > 0) { s += array[i]; i -= i & -i; // LSB 減算 } 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) { while(i <= n) { array[i] += x; i += i & -i; // LSB 加算 } } };
#line 1 "structure/strc_002_bit.cpp" // Binary Indexed Tree (BIT) // Verified: AOJ DSL_2_B: Range Sum Query (intのみ) template <typename T> struct BIT{ private: vector<T> array; int n; public: // 初期化 BIT() {} BIT(int _n) : array(_n + 1, 0), n(_n) {} // 1番目から i番目までの累積和を求める T sum(int i) { T s = 0; while(i > 0) { s += array[i]; i -= i & -i; // LSB 減算 } 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) { while(i <= n) { array[i] += x; i += i & -i; // LSB 加算 } } };