This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// 次の2つのクエリに対応するBIT
// ・[a, b) の要素全てに x を加えるクエリ
// ・[a, b) の和を計算するクエリ
// Verified: POJ 3468 (A Simple Problem with Integers)
template <typename U>
class BIT_sec {
public:
int n;
BIT<U> bit0, bit1;
BIT_sec(int n_) {
n = n_;
bit0 = BIT<U>(n);
bit1 = BIT<U>(n);
}
// 最初に要素を追加するときはこっち
void add(int i, int x) {
bit0.add(i, x);
}
// [l, r] の全要素に x を加える
void add(int l, int r, U x) {
bit0.add(l, -x * (l-1));
bit1.add(l, x);
bit0.add(r+1, x*r);
bit1.add(r+1, -x);
}
U sum(int l, int r) {
U res = 0;
res += bit0.sum(r) + bit1.sum(r) * r;
res -= bit0.sum(l-1) + bit1.sum(l-1) * (l-1);
return res;
}
};
#line 1 "structure/strc_004_bit_sec.cpp"
// 次の2つのクエリに対応するBIT
// ・[a, b) の要素全てに x を加えるクエリ
// ・[a, b) の和を計算するクエリ
// Verified: POJ 3468 (A Simple Problem with Integers)
template <typename U>
class BIT_sec {
public:
int n;
BIT<U> bit0, bit1;
BIT_sec(int n_) {
n = n_;
bit0 = BIT<U>(n);
bit1 = BIT<U>(n);
}
// 最初に要素を追加するときはこっち
void add(int i, int x) {
bit0.add(i, x);
}
// [l, r] の全要素に x を加える
void add(int l, int r, U x) {
bit0.add(l, -x * (l-1));
bit1.add(l, x);
bit0.add(r+1, x*r);
bit1.add(r+1, -x);
}
U sum(int l, int r) {
U res = 0;
res += bit0.sum(r) + bit1.sum(r) * r;
res -= bit0.sum(l-1) + bit1.sum(l-1) * (l-1);
return res;
}
};