「学习笔记」线段树标记永久化 - yi_fan0305
source link: https://www.cnblogs.com/yifan0305/p/17410471.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
「学习笔记」线段树标记永久化 - yi_fan0305 - 博客园
第一次见到这个词是在 zkw 线段树的课件里见到的。
标记永久化可以避免下传懒惰标记，只需在进行询问时把标记的影响加到答案当中，从而降低程序常数。
洛谷的模板题也证明，确实是小常数。
这三次提交都是递归写法，如果搭配 zkw 线段树，应该会跑得更快。
我们在讲懒标向下递归的过程中，如果当前区间正好等于查询区间，那就直接改懒标和数值，倘若当前区间包含查询区间但不与查询区间相等，那我们只修改值，这些操作与线段树修改操作很像。
inline void modify(int u, int l, int r, int lr, int rr, ll c) {
t[u].val += (rr - lr + 1) * c;
if (lr == l && r == rr) {
t[u].laz += c;
return ;
}
if (rr <= mid) modify(ls, l, mid, lr, rr, c);
else if (lr > mid) modify(rs, mid + 1, r, lr, rr, c);
else {
modify(ls, l, mid, lr, mid, c);
modify(rs, mid + 1, r, mid + 1, rr, c);
}
}
需要注意的是，如果查询的区间横跨左右两个孩子区间，那我们需要将查询区间也从 mid 处分开。
设置好懒标，查询时该如何处理懒标呢？
按照一般的写法，在向下递归时，我们还要用递归把懒标也一起向下传递，而标记永久化则是舍弃了向下传递懒标这个操作，我们在查询时设置一个值，用它来记录沿路的懒标，最后一起统计即可。
为什么要记录沿路的懒标呢？
如果包含该区间的大区间被打上了懒标，则说明这一整个大区间都受到这个懒标的影响，所以把它记录下来。
inline ll query(int u, int l, int r, int lr, int rr, ll add) {
if (lr == l && r == rr) {
return t[u].val + add * t[u].len;
}
ll sum = 0;
if (rr <= mid) {
sum = query(ls, l, mid, lr, rr, add + t[u].laz);
}
else if (lr > mid) {
sum = query(rs, mid + 1, r, lr, rr, add + t[u].laz);
}
else {
sum = query(ls, l, mid, lr, mid, add + t[u].laz)
+ query(rs, mid + 1, r, mid + 1, rr, add + t[u].laz);
}
return sum;
}
最后处理答案时，就是将懒标的和乘上这个区间的长度，add 记录的是懒标和，可以将这个 add 看作是对于这个区间的每个元素一共要增加的值。
- 码量小，不用写
pushdown和pushup。 - 在可持久化线段树上应用该技巧能做到区间修改的效果。
- 适用范围有限,只有当求的东西满足区间贡献独立。比如区间加法。
区间最大值就无法标记永久化。 - 多标记好像也不适用。
总归来说，对于一般的线段树，递归写法就足够了，标记永久化用的较少，对于线段树套线段树这样的应该会用的比较多。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)
const int N = 1e5 + 5;
int n, m;
struct seg_tree {
int len;
ll val, laz;
} t[N << 2];
inline void build(int u, int l, int r) {
t[u].len = r - l + 1, t[u].laz = 0;
if (l == r) {
cin >> t[u].val;
return ;
}
build(ls, l, mid);
build(rs, mid + 1, r);
t[u].val = t[ls].val + t[rs].val;
}
inline void modify(int u, int l, int r, int lr, int rr, ll c) {
t[u].val += (rr - lr + 1) * c;
if (lr == l && r == rr) {
t[u].laz += c;
return ;
}
if (rr <= mid) modify(ls, l, mid, lr, rr, c);
else if (lr > mid) modify(rs, mid + 1, r, lr, rr, c);
else {
modify(ls, l, mid, lr, mid, c);
modify(rs, mid + 1, r, mid + 1, rr, c);
}
}
inline ll query(int u, int l, int r, int lr, int rr, ll add) {
if (lr == l && r == rr) {
return t[u].val + add * t[u].len;
}
ll sum = 0;
if (rr <= mid) {
sum = query(ls, l, mid, lr, rr, add + t[u].laz);
}
else if (lr > mid) {
sum = query(rs, mid + 1, r, lr, rr, add + t[u].laz);
}
else {
sum = query(ls, l, mid, lr, mid, add + t[u].laz)
+ query(rs, mid + 1, r, mid + 1, rr, add + t[u].laz);
}
return sum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
build(1, 1, n);
for (int i = 1, op, x, y; i <= m; ++ i) {
cin >> op >> x >> y;
if (op == 1) {
ll k;
cin >> k;
modify(1, 1, n, x, y, k);
}
else {
cout << query(1, 1, n, x, y, 0) << '\n';
}
}
return 0;
}
__EOF__
Recommend
-
39
学习了一周的线段树和树状数组，深深地体会到了这每种操作几乎都是 \(O(logN)\) 级别的数据结构的美，但是做起题来还是相当痛苦的（特别是一开始只会模板的时候，很难灵活运用线段树的性质）。还好有雨巨大神带入门，视频讲...
-
12
线段树笔记 有这样一类问题，给定一个数列，让你求某段区间内和。如果对某个值或某段区间内的值进行修改后，如何快速的求和。如果线性执行更新操作或求和操作，无疑时间复杂度太大了。那么借助分治的思想，在执行更新区间...
-
5
取消品牌标记，小红书商业笔记不再“商业”？ 新榜 2023-01-10 3 评论...
-
11
点分治适合处理大规模的树上路径信息问题。 给定一棵 nn 个点树和一个整数 kk，求树上两点间的距离小于等于 kk
-
5
「学习笔记」容斥原理 - yi_fan0305 - 博客园 A1A1：学语文的人，
-
13
「学习笔记」线段树 - yi_fan0305 - 博客园 线段树是一棵二叉搜索树，思想与分治很想，把一段区间平分平分再平分，平分到不能平分为...
-
12
「学习笔记」记忆化搜索 - yi_fan0305 - 博客园 由于我一直对搜索情有独钟，因此，如果能写记忆化搜索的绝不会写 for
-
3
「学习笔记」基环树 - yi_fan0305 - 博客园 众所周知，一棵有 nn 个节点的树有 n−1
-
6
「学习笔记」CDQ分治 - yi_fan0305 - 博客园 CDQ 分治的思想最早由 IOI2008 金牌得主陈丹琦在高中时整理并总结，目前这个思想的拓展十...
-
4
前置知识——随机函数# 我们日常用的随机函数为 rand()...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK