什么是 Lazy 线段树？

Lazy 线段树（Lazy Propagation Segment Tree）是线段树（Segment Tree）的一种优化扩展，主要用于高效处理区间更新和区间查询问题。它在普通线段树的基础上引入了“延迟传播”（Lazy Propagation）的机制，通过推迟某些操作的实际执行时间，大幅减少了不必要的计算，从而优化时间复杂度。

普通线段树的局限性

普通线段树在处理区间查询（如求和、求最小值）时非常高效，时间复杂度为 O(logn)。然而，当涉及到区间更新（如将区间内所有元素加一个值）时，如果直接对每个叶子节点逐一修改，时间复杂度会退化为 O(nlogn)，这在数据规模较大时难以接受。

示例：
假设要对区间 [2,5] 的所有元素加 3。普通线段树需要递归分解区间，直到找到所有覆盖的叶子节点进行修改。如果区间长度为 k，则时间复杂度为 O(klogn)。

Lazy 线段树的核心思想

Lazy 线段树通过“延迟更新”来解决上述问题。其核心思想是：

• 延迟标记（Lazy Tag）：在更新某个区间时，不立即更新所有子节点，而是将更新操作记录在当前节点的标记中。

• 按需传播（Propagation）：只有当后续操作（查询或更新）需要访问子节点时，才将标记中的更新操作应用到子节点，并清空当前节点的标记。

类比：想象你有一个任务列表，但暂时不需要全部完成。你可以先记录下这些任务，等到真正需要结果时才去执行。

Lazy 线段树的工作流程

(1) 数据结构
每个线段树节点需要存储两类信息：

• 值（Value）：当前节点覆盖区间的计算结果（如区间和、最小值等）。
• 延迟标记（Lazy Tag）：记录尚未传播到子节点的更新操作（如区间加、区间乘等）。

(2) 关键操作

更新（Update）：
若当前节点区间完全包含在目标区间内，直接更新当前节点的值和延迟标记，无需修改子节点。否则，先将当前节点的延迟标记传播到子节点（称为 push down），再递归更新左右子树。

查询（Query）：
若当前节点区间完全包含在目标区间内，直接返回当前节点的值。否则，先 push down 延迟标记，再递归查询左右子树。

(3) Push Down 的具体步骤
当需要访问子节点时（无论是更新还是查询），必须先将父节点的延迟标记应用到子节点：
根据延迟标记更新子节点的值。
将延迟标记传递给子节点（叠加到子节点原有的标记上）。
清空父节点的延迟标记。

Lazy 线段树的适用场景

Lazy 线段树适用于以下操作：

可合并的区间更新：
例如区间加法
a[l…r]+=x、区间乘法
a[l…r]∗=x，这些操作可以叠加，且顺序不影响结果。

可分解的区间查询：
例如区间求和、区间最小值，结果可以通过子区间的结果合并得到。

常见应用：
动态维护区间和/区间最值，支持区间加减。
区间赋值（如将区间内所有元素设为某个值）。
区间修改与查询的组合问题（如“先加后乘”的混合操作）。

实现注意事项

标记的设计
根据具体问题定义标记类型。例如：
区间加法：标记为一个累积的增量值。
区间赋值：标记为一个目标值和一个标志位。

标记的叠加规则：
若多个更新操作作用在同一节点，需定义标记如何合并。例如：
先加 3，再加 5 ⇒ 合并为加 8。
先加 3，再乘 2 ⇒ 需保留顺序，不能简单合并。

边界条件处理：
确保在叶子节点（区间长度为 1）时不再传播标记。

总结

Lazy 线段树通过延迟传播机制，将区间更新的时间复杂度从 O(nlogn) 优化到 O(logn)，是处理动态区间问题的利器。其核心在于：

延迟标记记录未完成的操作。
按需传播仅在必要时更新子节点。

Lazy 题目实践

LeetCode 2502. 设计内存分配器

参考 灵茶山艾府 的一篇题解

class SegTree {
    private final int[] pre0; // 区间前缀连续 0 的个数
    private final int[] suf0; // 区间后缀连续 0 的个数
    private final int[] max0; // 区间最长连续 0 的个数
    private final int[] todo; // 懒标记

    public SegTree(int n) {
        int size = 2 << (32 - Integer.numberOfLeadingZeros(n - 1));
        pre0 = new int[size];
        suf0 = new int[size];
        max0 = new int[size];
        todo = new int[size];
        build(1, 0, n - 1);
    }

    // 把 [ql, qr] 都置为 v
    public void update(int o, int l, int r, int ql, int qr, int v) {
        if (ql <= l && r <= qr) {
            do_(o, l, r, v);
            return;
        }
        spread(o, l, r);
        int m = (l + r) / 2;
        int lo = o * 2;
        int ro = lo + 1;
        if (ql <= m) {
            update(lo, l, m, ql, qr, v);
        }
        if (m < qr) {
            update(ro, m + 1, r, ql, qr, v);
        }

        // 合并左右子树的信息
        pre0[o] = pre0[lo];
        if (pre0[lo] == m - l + 1) {
            pre0[o] += pre0[ro]; // 和右子树的 pre0 拼起来
        }
        suf0[o] = suf0[ro];
        if (suf0[ro] == r - m) {
            suf0[o] += suf0[lo]; // 和左子树的 suf0 拼起来
        }
        max0[o] = Math.max(Math.max(max0[lo], max0[ro]), suf0[lo] + pre0[ro]);
    }

    // 线段树二分，找最左边的区间左端点，满足区间全为 0 且长度 >= size
    // 如果不存在这样的区间，返回 -1
    public int findFirst(int o, int l, int r, int size) {
        if (max0[o] < size) {
            return -1;
        }
        if (l == r) {
            return l;
        }
        spread(o, l, r);
        int m = (l + r) / 2;
        int lo = o * 2;
        int ro = lo + 1;
        int idx = findFirst(lo, l, m, size); // 递归左子树
        if (idx < 0) {
            // 左子树的后缀 0 个数 + 右子树的前缀 0 个数 >= size
            if (suf0[lo] + pre0[ro] >= size) {
                return m - suf0[lo] + 1;
            }
            idx = findFirst(ro, m + 1, r, size); // 递归右子树
        }
        return idx;
    }

    // 初始化线段树
    private void build(int o, int l, int r) {
        do_(o, l, r, -1);
        if (l == r) {
            return;
        }
        int m = (l + r) / 2;
        build(o * 2, l, m);
        build(o * 2 + 1, m + 1, r);
    }

    private void do_(int i, int l, int r, int v) {
        int size = v <= 0 ? r - l + 1 : 0;
        pre0[i] = suf0[i] = max0[i] = size;
        todo[i] = v;
    }

    // 下传懒标记
    private void spread(int o, int l, int r) {
        int v = todo[o];
        if (v != -1) {
            int m = (l + r) / 2;
            do_(o * 2, l, m, v);
            do_(o * 2 + 1, m + 1, r, v);
            todo[o] = -1;
        }
    }
}

class Allocator {
    private final int n;
    private final SegTree tree;
    private final Map<Integer, List<int[]>> blocks = new HashMap<>();

    public Allocator(int n) {
        this.n = n;
        this.tree = new SegTree(n);
    }

    public int allocate(int size, int mID) {
        int i = tree.findFirst(1, 0, n - 1, size);
        if (i < 0) { // 无法分配内存
            return -1;
        }
        // 分配内存 [i, i+size-1]
        blocks.computeIfAbsent(mID, k -> new ArrayList<>()).add(new int[]{i, i + size - 1});
        tree.update(1, 0, n - 1, i, i + size - 1, 1);
        return i;
    }

    public int freeMemory(int mID) {
        int ans = 0;
        List<int[]> list = blocks.get(mID);
        if (list != null) {
            for (int[] range : list) {
                ans += range[1] - range[0] + 1;
                tree.update(1, 0, n - 1, range[0], range[1], 0); // 释放内存
            }
            blocks.remove(mID);
        }
        return ans;
    }
}

作者：灵茶山艾府
链接：https://leetcode.cn/problems/design-memory-allocator/description/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。