每日算法 — 使用java实现线段树：区间查询与懒标记延迟更新

引言

线段树（Segment Tree）是一种用于高效处理区间查询和区间修改问题的二叉树形数据结构。对于长度为 $n$ 的数组，线段树可以在 $O(\log n)$ 时间内完成单点修改、区间求和、区间最值等操作。当涉及区间批量更新时，引入懒标记（Lazy Propagation）技术可将区间修改的时间复杂度同样控制在 $O(\log n)$，避免对区间内每个元素逐一操作。

核心思想

线段树将数组区间递归二分，每个节点代表一个区间并维护该区间的聚合信息（如和、最大值、最小值）。叶节点对应单个元素，内部节点对应合并后的区间信息。

基础实现：区间求和

public class SegmentTree {
    private int n;           // 原数组长度
    private long[] tree;     // 线段树数组（4倍空间）
    private long[] lazy;     // 懒标记数组
    private long[] arr;      // 原数组副本

    public SegmentTree(long[] input) {
        this.n = input.length;
        this.arr = input.clone();
        // 线段树需要4*n的空间保证足够
        this.tree = new long[4 * n];
        this.lazy = new long[4 * n];
        build(1, 0, n - 1);
    }

    // 构建线段树：节点idx代表区间[l, r]
    private void build(int idx, int l, int r) {
        if (l == r) {
            tree[idx] = arr[l];
            return;
        }
        int mid = l + (r - l) / 2;
        build(idx * 2, l, mid);       // 左子树
        build(idx * 2 + 1, mid + 1, r); // 右子树
        tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
    }

    // 单点更新：将位置pos的值增加delta
    public void pointUpdate(int pos, long delta) {
        pointUpdate(1, 0, n - 1, pos, delta);
    }

    private void pointUpdate(int idx, int l, int r, int pos, long delta) {
        if (l == r) {
            tree[idx] += delta;
            return;
        }
        int mid = l + (r - l) / 2;
        if (pos <= mid) {
            pointUpdate(idx * 2, l, mid, pos, delta);
        } else {
            pointUpdate(idx * 2 + 1, mid + 1, r, pos, delta);
        }
        tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
    }

    // 区间查询：查询[ql, qr]的区间和
    public long rangeQuery(int ql, int qr) {
        return rangeQuery(1, 0, n - 1, ql, qr);
    }

    private long rangeQuery(int idx, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return 0; // 无交集
        if (ql <= l && r <= qr) return tree[idx]; // 完全包含

        pushDown(idx, l, r); // 下传懒标记
        int mid = l + (r - l) / 2;
        long leftSum = rangeQuery(idx * 2, l, mid, ql, qr);
        long rightSum = rangeQuery(idx * 2 + 1, mid + 1, r, ql, qr);
        return leftSum + rightSum;
    }
}

懒标记延迟更新：区间批量修改

当需要将区间 $[L, R]$ 内所有元素增加 $val$ 时，利用懒标记避免逐元素修改。

    // 区间更新：将[ul, ur]内所有元素增加val
    public void rangeUpdate(int ul, int ur, long val) {
        rangeUpdate(1, 0, n - 1, ul, ur, val);
    }

    private void rangeUpdate(int idx, int l, int r, int ul, int ur, long val) {
        if (ul > r || ur < l) return; // 无交集
        if (ul <= l && r <= ur) {
            // 当前节点区间完全在更新范围内，打懒标记
            tree[idx] += val * (r - l + 1);
            lazy[idx] += val;
            return;
        }

        pushDown(idx, l, r); // 下传懒标记后再递归
        int mid = l + (r - l) / 2;
        rangeUpdate(idx * 2, l, mid, ul, ur, val);
        rangeUpdate(idx * 2 + 1, mid + 1, r, ul, ur, val);
        tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
    }

    // 下传懒标记：将当前节点的pending更新传递给子节点
    private void pushDown(int idx, int l, int r) {
        if (lazy[idx] != 0 && l != r) {
            int mid = l + (r - l) / 2;
            int leftIdx = idx * 2;
            int rightIdx = idx * 2 + 1;

            // 左子树覆盖[l, mid]
            tree[leftIdx] += lazy[idx] * (mid - l + 1);
            lazy[leftIdx] += lazy[idx];

            // 右子树覆盖[mid+1, r]
            tree[rightIdx] += lazy[idx] * (r - mid);
            lazy[rightIdx] += lazy[idx];

            lazy[idx] = 0; // 清空当前节点懒标记
        }
    }

扩展：区间最值查询（RMQ）

线段树同样适用于区间最值查询，只需将合并逻辑从求和改为取最值。

public class SegmentTreeRMQ {
    private int n;
    private long[] maxTree;
    private long[] minTree;

    public SegmentTreeRMQ(long[] input) {
        this.n = input.length;
        this.maxTree = new long[4 * n];
        this.minTree = new long[4 * n];
        build(1, 0, n - 1, input);
    }

    private void build(int idx, int l, int r, long[] arr) {
        if (l == r) {
            maxTree[idx] = minTree[idx] = arr[l];
            return;
        }
        int mid = l + (r - l) / 2;
        build(idx * 2, l, mid, arr);
        build(idx * 2 + 1, mid + 1, r, arr);
        maxTree[idx] = Math.max(maxTree[idx * 2], maxTree[idx * 2 + 1]);
        minTree[idx] = Math.min(minTree[idx * 2], minTree[idx * 2 + 1]);
    }

    public long queryMax(int ql, int qr) {
        return queryMax(1, 0, n - 1, ql, qr);
    }

    private long queryMax(int idx, int l, int r, int ql, int qr) {
        if (ql > r || qr < l) return Long.MIN_VALUE;
        if (ql <= l && r <= qr) return maxTree[idx];
        int mid = l + (r - l) / 2;
        return Math.max(queryMax(idx * 2, l, mid, ql, qr),
                        queryMax(idx * 2 + 1, mid + 1, r, ql, qr));
    }
}

完整测试用例

public class SegmentTreeDemo {
    public static void main(String[] args) {
        long[] arr = {1, 3, 5, 7, 9, 11};
        SegmentTree st = new SegmentTree(arr);

        // 查询区间[1, 3]的和：3+5+7=15
        System.out.println("Range [1,3] sum: " + st.rangeQuery(1, 3));

        // 将区间[1, 4]每个元素+2
        st.rangeUpdate(1, 4, 2);
        // 数组变为 [1, 5, 7, 9, 11, 11]

        // 再次查询[1, 3]：5+7+9=21
        System.out.println("After update, Range [1,3] sum: " + st.rangeQuery(1, 3));

        // 单点更新：位置2增加3
        st.pointUpdate(2, 3);
        // 数组变为 [1, 5, 10, 9, 11, 11]

        // 查询整个区间
        System.out.println("Total sum: " + st.rangeQuery(0, 5));
    }
}

复杂度分析

线段树与树状数组（Fenwick Tree）相比，支持更丰富的区间操作（如区间最值、区间赋值），但常数因子和空间开销更大。当问题仅涉及区间求和与单点修改时，树状数组是更轻量的选择；一旦涉及区间批量更新或最值查询，线段树便成为不可或缺的工具。