This documentation is automatically generated by online-judge-tools/verification-helper
This project is maintained by tsutaj
// Lazy Segment Tree (遅延評価付きセグメント木)
// 総和バージョン (0-indexed, 区間 add, 区間 sum)
// Verified: AOJ DSL_2_E: Range Add Query (RAQ)
// 最下段のサイズ (元配列のサイズより大きい 2 ベキ)
constexpr ll SIZE = 1LL << 17;
template <typename T>
struct LazySegtree {
T node[2*SIZE], lazy[2*SIZE];
// 初期化
LazySegtree() {}
LazySegtree(vector<T> v) {
for(size_t i=0; i<v.size(); ++i) {
node[SIZE-1+i] = v[i];
}
for(int i=SIZE-2; i>=0; i--) {
node[i] = node[2*i+1] + node[2*i+2];
}
}
// 遅延評価
void lazyUpdate(int a, int b, int k) {
int rng = b - a;
node[k] += lazy[k] * rng;
if(rng > 1) {
lazy[2*k+1] += lazy[k];
lazy[2*k+2] += lazy[k];
}
lazy[k] = 0;
}
// 範囲 [a, b) に x を足す
void add(int a, int b, T x, int l=0, int r=SIZE, int k=0) {
lazyUpdate(l, r, k);
if(b <= l || r <= a) return;
if(a <= l && r <= b) {
lazy[k] += x;
lazyUpdate(l, r, k);
}
else {
int mid = (l + r) / 2;
add(a, b, x, l, mid, 2*k+1);
add(a, b, x, mid, r, 2*k+2);
node[k] = node[2*k+1] + node[2*k+2];
}
}
// 範囲 [a, b) の総和
T sum(int a, int b, int l=0, int r=SIZE, int k=0) {
lazyUpdate(l, r, k);
if(b <= l || r <= a) return 0;
if(a <= l && r <= b) return node[k];
int mid = (l + r) / 2;
T vl = sum(a, b, l, mid, 2*k+1);
T vr = sum(a, b, mid, r, 2*k+2);
return vl + vr;
}
};
#line 1 "structure/old/strc_011_lazysegtree.cpp"
// Lazy Segment Tree (遅延評価付きセグメント木)
// 総和バージョン (0-indexed, 区間 add, 区間 sum)
// Verified: AOJ DSL_2_E: Range Add Query (RAQ)
// 最下段のサイズ (元配列のサイズより大きい 2 ベキ)
constexpr ll SIZE = 1LL << 17;
template <typename T>
struct LazySegtree {
T node[2*SIZE], lazy[2*SIZE];
// 初期化
LazySegtree() {}
LazySegtree(vector<T> v) {
for(size_t i=0; i<v.size(); ++i) {
node[SIZE-1+i] = v[i];
}
for(int i=SIZE-2; i>=0; i--) {
node[i] = node[2*i+1] + node[2*i+2];
}
}
// 遅延評価
void lazyUpdate(int a, int b, int k) {
int rng = b - a;
node[k] += lazy[k] * rng;
if(rng > 1) {
lazy[2*k+1] += lazy[k];
lazy[2*k+2] += lazy[k];
}
lazy[k] = 0;
}
// 範囲 [a, b) に x を足す
void add(int a, int b, T x, int l=0, int r=SIZE, int k=0) {
lazyUpdate(l, r, k);
if(b <= l || r <= a) return;
if(a <= l && r <= b) {
lazy[k] += x;
lazyUpdate(l, r, k);
}
else {
int mid = (l + r) / 2;
add(a, b, x, l, mid, 2*k+1);
add(a, b, x, mid, r, 2*k+2);
node[k] = node[2*k+1] + node[2*k+2];
}
}
// 範囲 [a, b) の総和
T sum(int a, int b, int l=0, int r=SIZE, int k=0) {
lazyUpdate(l, r, k);
if(b <= l || r <= a) return 0;
if(a <= l && r <= b) return node[k];
int mid = (l + r) / 2;
T vl = sum(a, b, l, mid, 2*k+1);
T vr = sum(a, b, mid, r, 2*k+2);
return vl + vr;
}
};