「学习笔记」线段树标记永久化 - yi_fan0305

「学习笔记」线段树标记永久化 - 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 看作是对于这个区间的每个元素一共要增加的值。

1. 码量小，不用写 pushdown 和 pushup。
2. 在可持久化线段树上应用该技巧能做到区间修改的效果。

1. 适用范围有限,只有当求的东西满足区间贡献独立。比如区间加法。
   区间最大值就无法标记永久化。
2. 多标记好像也不适用。

总归来说，对于一般的线段树，递归写法就足够了，标记永久化用的较少，对于线段树套线段树这样的应该会用的比较多。

【模板】线段树 1

#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__