懒标记
2026-06-20 13:31:23
发布于：浙江
8阅读
0回复
0点赞
1. push_down：标记下传（最关键）
触发时机：递归进入左右子树之前必须调用。
作用：把父节点的延迟修改下放给左右孩子，更新孩子的区间值 + 叠加孩子懒标记，父节点标记清零。
cpp
运行
// node当前节点，l、r当前区间左右边界
void push_down(int node, int l, int r) {
if (lazy[node] == 0 || l == r) return; // 无标记/叶子无需下传
int mid = (l + r) / 2;
int ls = node * 2, rs = node * 2 + 1;
// 更新左子树
tree[ls] += lazy[node] * (mid - l + 1);
lazy[ls] += lazy[node];
// 更新右子树
tree[rs] += lazy[node] * (r - mid);
lazy[rs] += lazy[node];
lazy[node] = 0; // 清空父节点标记
}
2. update：区间修改（区间加 v）
cpp
运行
// 修改[L,R]全部加v，当前节点管[l,r]
void update(int node, int l, int r, int L, int R, int v) {
if (R < l || r < L) return; // 无交集，直接返回
if (L <= l && r <= R) { // 完全覆盖：偷懒，打标记
tree[node] += v * (r - l + 1);
lazy[node] += v;
return;
}
// 不完全覆盖：必须先下传旧标记，再递归子树
push_down(node, l, r);
int mid = (l + r) / 2;
update(node*2, l, mid, L, R, v);
update(node*2+1, mid+1, r, L, R, v);
tree[node] = tree[node*2] + tree[node*2+1]; // 合并子树结果
}
3. query：区间查询（查询区间和）
cpp
运行
int query(int node, int l, int r, int L, int R) {
if (R < l || r < L) return 0;
if (L <= l && r <= R) return tree[node];
// 要访问子节点，先下传标记
push_down(node, l, r);
int mid = (l + r) / 2;
return query(node*2,l,mid,L,R) + query(node*2+1,mid+1,r,L,R);
}
有帮助，赞一个