懒标记

ㅤㅤㅤㅤㅤ

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);
}

有帮助，赞一个

去预览

0/2000

全部评论 1

ssss
%?

2026-06-20 来自广东
0

全部评论 1

热门讨论