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