[线段树系列 #6] 标记永久化
标记永久化是线段树的一个技巧,通常用于对主席树等难以 pushdown 的数据结构进行区间修改
具体思想已经体现在名字里了,我们结合例题稍微讲解一下
例题1
P3372 【模板】线段树 1
线段树区间修改区间查询板子
void modify(ll p, ll l, ll r, ll v) {t[p].sum += (min(t[p].r, r)-max(t[p].l, l)+1)*v;if(l <= t[p].l && t[p].r <= r) {t[p].add += v;return;}ll mid = (t[p].l+t[p].r) >> 1;if(l <= mid) modify(p*2, l, r, v);if(mid < r) modify(p*2+1, l, r, v);
}
ll query(ll p, ll l, ll r, ll ad) {if(l <= t[p].l && t[p].r <= r) return t[p].sum+ad*(t[p].r-t[p].l+1);ll mid = (t[p].l+t[p].r) >> 1, res = 0;if(l <= mid) res += query(p*2, l, r, ad+t[p].add);if(mid < r) res += query(p*2+1, l, r, ad+t[p].add);return res;
}
// 剩余部分与普通线段树一致
可见,每个线段树节点上新增了 \(add\) 值,具体细节很显然,但这没有 pushdown 函数,并且维护了区间修改操作。但是标记永久化不能维护先后顺序(如线段树 2 中的乘加操作)和交换律。
例题2
SP11470 TTM - To the moon
主席树区间修改
void modify(ll &p, ll q, ll l, ll r, ll L, ll R, ll v) {p = ++cnt;t[p] = t[q];t[p].sum += (min(R, r)-max(L, l)+1)*v;if(L <= l && r <= R) {t[p].add += v;return;}ll mid = (l+r) >> 1;if(L <= mid) modify(t[p].l, t[q].l, l, mid, L, R, v);if(mid < R) modify(t[p].r, t[q].r, mid+1, r, L, R, v);
}
ll query(ll p, ll l, ll r, ll L, ll R, ll ad) {if(L <= l && r <= R) return t[p].sum+ad*(r-l+1);ll mid = (l+r) >> 1, res = 0;if(L <= mid) res += query(t[p].l, l, mid, L, R, ad+t[p].add);if(mid < R) res += query(t[p].r, mid+1, r, L, R, ad+t[p].add);return res;
}
和线段树同理
2025.9.29 19:10