线段树 II 之 懒惰标记
前置知识：线段树 I – ztr 的小窝 (ztrztr.top)
懒惰标志 Lazy Tag
懒惰标志，是维持线段树的区间修改查询的复杂度在 $O(\log n)$ 级别的一个方法。
正常的区间修改查询的复杂度可以说是 $O(n)$ 级别的，因为每次修改一个，需要一直传到叶子节点为止。
但是我们发现，如果这样的话，修改的复杂度会很高，堪比暴力。我们需要想一个办法来解决。
那么这里我们可以引入 Lazy Tag。
比如一个数组 $1, 2, 3, 4, 5, 6$，我们要对区间 $[2,5]$ 加一，如果暴力的话是直接遍历把，每一位加一。
如果不用 Lazy Tag，那么线段树也要递归到叶子节点去修改，常数甚至比暴力还高。
但是，我们发现，如果递归找到一个合适的区间，比如说我们递归到了 $[4,5]$，这时我们完全没必要继续往下遍历，只用修改这个区间，然后回溯的时候就可以自动修改上层的区间。
那我们还要不要往下呢？这时候我们可以让 $lazy[i]$ 的值增加修改量，然后再修改儿子节点，就行了，没必要继续往下。
查询的时候，我们也再递归前先 push_down 一下，把现在的这个线段的儿子更新一下。
注意一下 push_down 的最后要清空 laze[i]，因为已经用不上了。
如果操作有好几种，需要注意先乘再加，必然会有一些问题。
小技巧
有些题目，比如说 GSS4 – Can you answer these queries IV – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)，如果想要用 Lazy Tag，有点难做，至少我没有想出来。
这个时候，我们发现开放最多做 $6$ 次，那么我们可以以退为进，直接暴力，然后如果不是 $1$ 或者 $0$ 就开放。
线段树 2 代码
#include <bits/stdc++.h>
using namespace std;
/*
*/
#define int long long
int n, m, mod;
int a[1000005], seg[1000005], mult[1000005], addt[1000005];
void build(int l, int r, int nw) {
mult[nw] = 1;
if (l == r) {
seg[nw] = a[l];
return;
}
int mid = (l + r) / 2;
build(l, mid, nw * 2);
build(mid + 1, r, nw * 2 + 1);
seg[nw] = (seg[nw * 2] + seg[nw * 2 + 1]) % mod;
}
void push_down(int len, int nw) {
mult[nw * 2] = (mult[nw] * mult[nw * 2]) % mod;
mult[nw * 2 + 1] = (mult[nw] * mult[nw * 2 + 1]) % mod;
addt[nw * 2] = (mult[nw] * addt[nw * 2]) % mod;
addt[nw * 2 + 1] = (mult[nw] * addt[nw * 2 + 1]) % mod;
seg[nw * 2] = (seg[nw * 2] * mult[nw]) % mod;
seg[nw * 2 + 1] = (seg[nw * 2 + 1] * mult[nw]) % mod;
mult[nw] = 1;
addt[nw * 2] = (addt[nw] + addt[nw * 2]) % mod;
addt[nw * 2 + 1] = (addt[nw] + addt[nw * 2 + 1]) % mod;
seg[nw * 2] = (seg[nw * 2] + addt[nw] * (len - len / 2)) % mod;
seg[nw * 2 + 1] = (seg[nw * 2 + 1] + addt[nw] * (len / 2)) % mod;
addt[nw] = 0;
}
void add(int l, int r, int nl, int nr, int nw, int z) {
if (nr < l || nl > r) return;
if (nr <= r && nl >= l) {
seg[nw] = ((nr - nl + 1) * z + seg[nw]) % mod;
addt[nw] = (z + addt[nw]) % mod;
return;
}
if (addt[nw] || mult[nw] != 1) push_down(nr - nl + 1, nw);
int mid = (nl + nr) / 2;
add(l, r, nl, mid, nw * 2, z);
add(l, r, mid + 1, nr, nw * 2 + 1, z);
seg[nw] = (seg[nw * 2] + seg[nw * 2 + 1]) % mod;
}
void mul(int l, int r, int nl, int nr, int nw, int z) {
if (nr < l || nl > r) return;
if (nr <= r && nl >= l) {
seg[nw] = (seg[nw] * z) % mod;
// if (nl < nr) {
mult[nw] = (mult[nw] * z) % mod;
addt[nw] = (addt[nw] * z) % mod;
// }
return;
}
if (addt[nw] || mult[nw] != 1)push_down(nr - nl + 1, nw);
int mid = (nl + nr) / 2;
mul(l, r, nl, mid, nw * 2, z);
mul(l, r, mid + 1, nr, nw * 2 + 1, z);
seg[nw] = (seg[nw * 2] + seg[nw * 2 + 1]) % mod;
}
int query(int l, int r, int nl, int nr, int nw) {
// cout << l << " " << r << " " << nl << " " << nr << " " << nw << " " << seg[nw] << "\n";
if (nr < l || nl > r) return 0;
if (nr <= r && nl >= l) {
return seg[nw];
}
if (addt[nw] || mult[nw] != 1) push_down(nr - nl + 1, nw);
int mid = (nl + nr) / 2;
int lc = query(l, r, nl, mid, nw * 2) % mod;
int rc = query(l, r, mid + 1, nr, nw * 2 + 1) % mod;
return (lc + rc) % mod;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m >> mod;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
}
// cout << 1;
build(1, n, 1);
for (int i = 1; i <= m; i ++) {
int op; cin >> op;
// for (int i = 1; seg[i]; i ++) {
// cout << seg[i] << " ";
// }
// cout << "\n";
if (op == 1) {
int x, y, k; cin >> x >> y >> k;
mul(x, y, 1, n, 1, k);
} else if (op == 2) {
int x, y, k; cin >> x >> y >> k;
add(x, y, 1, n, 1, k);
} else {
int x,y;
cin >> x >> y;
cout << query(x, y, 1, n, 1) % mod << "\n";
}
}
return 0;
}
GSS4 – Can you answer these queries IV – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <bits/stdc++.h>
using namespace std;
/*
*/
#define int long long
int n, m;
const int mod = 1e9+7;int a[1000005], seg[1000005], lazy[1000005], seg2[1000005], tag[1000005];
void push_up(int nw) {
seg[nw] = seg[nw * 2] + seg[nw * 2 + 1];
tag[nw] = max(tag[nw * 2], tag[nw * 2 + 1]);
}
void build(int l, int r, int nw) {
if (l == r) {
seg[nw] = tag[nw] = a[l];
//Leaf node.
// cout << "[Debug] Finded leaf node " << nw << "\n";
return;
}
int mid = (l + r) / 2;
// cout << "11\n";
build(l, mid, nw * 2);
build(mid + 1, r, nw * 2 + 1);
// seg[nw] = seg[nw * 2] + seg[nw * 2 + 1];
push_up(nw);
//update
}
void sqr(int l, int r, int nl, int nr, int nw) {
// cout << nl << " " << nr << " " << seg[nw] << "\n";
if (nr < l || nl > r) return;
if (nl == nr) {
seg[nw] = floor(sqrt(seg[nw]));
tag[nw] = seg[nw];
return;
}
int mid = (nl + nr) / 2;
if (tag[nw * 2] > 1) sqr(l, r, nl, mid, nw * 2);
if (tag[nw * 2 + 1] > 1) sqr(l, r, mid + 1, nr, nw * 2 + 1);
// seg[nw] = seg[nw * 2] + seg[nw * 2 + 1];
push_up(nw);
}
int query(int l, int r, int nl, int nr, int nw) {
// cout << l << " " << r << " " << nl << " " << nr << " " << nw << " " << seg[nw] << "\n";
// if (nr < l || nl > r) return 0;
if (nr <= r && nl >= l) {
return seg[nw];
}
int mid = (nl + nr) / 2;
int lc = 0, rc = 0;
if (l <= mid) lc = query(l, r, nl, mid, nw * 2);
if (r > mid) rc = query(l, r, mid + 1, nr, nw * 2 + 1);
return lc + rc;
push_up(nw);
}
void printseg() {
for (int i = 1; seg[i]; i ++) cout << tag[i] << " ";
cout << "\n";
}
void solve() {
for (int i = 1; i <= n; i ++) {
cin >> a[i];
}
build(1, n, 1);
cin >> m;
// cout << m << "\n";
for (int i = 1; i <= m; i ++) {
int op; cin >> op;
if (op == 0) {
int x, y, z; cin >> x>> y;
if (x > y) swap(x, y);
sqr(x, y, 1, n, 1);
} else{
int x, y; cin >> x >> y;
if (x > y) swap(x, y);
cout << query(x, y, 1, n, 1) << "\n";
}
// printseg();
}
}
int cnt = 0;
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
while (cin >> n) {
cout << "Case #" << ++cnt << ":\n";
solve();
cout << "\n";
}
}