第一次见到这个词是在 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
。坏处:
总归来说,对于一般的线段树,递归写法就足够了,标记永久化用的较少,对于线段树套线段树这样的应该会用的比较多。
【模板】线段树 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; }