第一次見到這個詞是在 zkw 線段樹的課件里見到的。
(資料圖片)
標記永久化可以避免下傳懶惰標記，只需在進行詢問時把標記的影響加到答案當中，從而降低程序常數(shù)。
洛谷的模板題也證明，確實是小常數(shù)。這三次提交都是遞歸寫法，如果搭配 zkw 線段樹，應該會跑得更快。
具體操作我們在講懶標向下遞歸的過程中，如果當前區(qū)間正好等于查詢區(qū)間，那就直接改懶標和數(shù)值，倘若當前區(qū)間包含查詢區(qū)間但不與查詢區(qū)間相等，那我們只修改值，這些操作與線段樹修改操作很像。
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);}}需要注意的是，如果查詢的區(qū)間橫跨左右兩個孩子區(qū)間，那我們需要將查詢區(qū)間也從 mid處分開。
設置好懶標，查詢時該如何處理懶標呢？按照一般的寫法，在向下遞歸時，我們還要用遞歸把懶標也一起向下傳遞，而標記永久化則是舍棄了向下傳遞懶標這個操作，我們在查詢時設置一個值，用它來記錄沿路的懶標，最后一起統(tǒng)計即可。為什么要記錄沿路的懶標呢？如果包含該區(qū)間的大區(qū)間被打上了懶標，則說明這一整個大區(qū)間都受到這個懶標的影響，所以把它記錄下來。
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;}最后處理答案時，就是將懶標的和乘上這個區(qū)間的長度，add記錄的是懶標和，可以將這個 add看作是對于這個區(qū)間的每個元素一共要增加的值。
好處：
碼量小，不用寫pushdown和 pushup。在可持久化線段樹上應用該技巧能做到區(qū)間修改的效果。壞處：
適用范圍有限,只有當求的東西滿足區(qū)間貢獻獨立。比如區(qū)間加法。區(qū)間最大值就無法標記永久化。多標記好像也不適用。總歸來說，對于一般的線段樹，遞歸寫法就足夠了，標記永久化用的較少，對于線段樹套線段樹這樣的應該會用的比較多。
例題【模板】線段樹 1
#include 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;} 標簽：
