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;
}
};