每日算法 — 使用java实现线段树：区间查询与懒标记优化

线段树（Segment Tree）是一种基于分治思想的二叉树形数据结构，能够在 $O(\log n)$ 时间内完成区间查询与单点修改。当引入懒标记（Lazy Propagation）机制后，它甚至可以以同样的时间复杂度支持区间批量更新。本文将用 Java 从零实现一个支持区间求和、区间修改的完整线段树，深入讲解其构建、查询、更新的核心逻辑。

一、为什么需要线段树

假设有一个长度为 $n$ 的数组，需要频繁执行以下两种操作：

区间查询：求数组某段区间 $[l, r]$ 的元素之和
区间更新：将区间 $[l, r]$ 内每个元素都加上一个值 $v$

如果用暴力方法，区间查询和区间更新都需要 $O(n)$ 时间。当操作次数达到 $10^5$ 级别时，总时间复杂度将高达 $O(n^2)$，显然不可接受。

方法	单点修改	区间查询	区间修改
暴力遍历	$O(1)$	$O(n)$	$O(n)$
前缀和	不可行	$O(1)$	不可行
线段树	$O(\log n)$	$O(\log n)$	$O(\log n)$（带懒标记）

线段树通过将区间不断二分，把 $O(n)$ 的线性操作优化到 $O(\log n)$ 的对数级别，是处理区间问题的利器。

二、线段树的基本结构

线段树是一棵完全二叉树，每个节点代表数组上的一个区间：

根节点代表整个区间 $[0, n-1]$
每个叶子节点代表一个单点区间 $[i, i]$
每个内部节点的区间等于其左右子节点区间的并集

对于长度为 $n$ 的数组，线段树通常需要 $4n$ 的存储空间（用数组模拟完全二叉树）。

2.1 节点定义

每个节点需要维护以下信息：

sum：当前区间元素之和
lazy：懒标记，表示该区间有待下传的增量

/**
 * 线段树节点
 * 使用数组模拟完全二叉树，每个节点维护区间和与懒标记
 */
class SegmentTree {
    // tree[i] 表示节点i维护的区间和
    private long[] tree;
    // lazy[i] 表示节点i的懒标记（待下传的区间增量）
    private long[] lazy;
    // 原始数组
    private int[] nums;
    // 数组长度
    private int n;

    public SegmentTree(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        // 线段树开4倍空间足够容纳所有节点
        this.tree = new long[n * 4];
        this.lazy = new long[n * 4];
        // 递归构建线段树
        build(0, 0, n - 1);
    }
}

三、线段树的构建

构建过程采用自顶向下的递归方式：

如果是叶子节点（left == right），直接赋值为对应数组元素
否则递归构建左右子树，当前节点的值等于左右子树之和

/**
 * 递归构建线段树
 * @param node  当前节点编号
 * @param left  当前节点代表的区间左端点
 * @param right 当前节点代表的区间右端点
 */
private void build(int node, int left, int right) {
    if (left == right) {
        // 叶子节点，直接赋值
        tree[node] = nums[left];
        return;
    }

    int mid = left + (right - left) / 2;
    int leftChild = node * 2 + 1;
    int rightChild = node * 2 + 2;

    // 递归构建左子树 [left, mid]
    build(leftChild, left, mid);
    // 递归构建右子树 [mid+1, right]
    build(rightChild, mid + 1, right);

    // 当前节点的值 = 左子树 + 右子树
    tree[node] = tree[leftChild] + tree[rightChild];
}

四、区间查询

查询区间 $[queryLeft, queryRight]$ 的和时，从根节点开始递归：

如果当前节点区间完全包含在查询区间内，直接返回该节点的 sum
如果当前节点区间与查询区间无交集，返回 0
否则先下传懒标记，然后递归查询左右子树

/**
 * 对外接口：查询区间 [queryLeft, queryRight] 的和
 */
public long query(int queryLeft, int queryRight) {
    return query(0, 0, n - 1, queryLeft, queryRight);
}

/**
 * 递归查询
 * @param node       当前节点编号
 * @param left       当前节点区间左端点
 * @param right      当前节点区间右端点
 * @param queryLeft  查询区间左端点
 * @param queryRight 查询区间右端点
 */
private long query(int node, int left, int right,
                   int queryLeft, int queryRight) {
    // 当前区间完全在查询区间外
    if (right < queryLeft || left > queryRight) {
        return 0;
    }

    // 当前区间完全包含在查询区间内
    if (queryLeft <= left && right <= queryRight) {
        return tree[node];
    }

    // 下传懒标记，确保子节点数据正确
    pushDown(node, left, right);

    int mid = left + (right - left) / 2;
    int leftChild = node * 2 + 1;
    int rightChild = node * 2 + 2;

    // 递归查询左右子树
    long leftSum = query(leftChild, left, mid, queryLeft, queryRight);
    long rightSum = query(rightChild, mid + 1, right, queryLeft, queryRight);

    return leftSum + rightSum;
}

五、懒标记与区间更新

5.1 懒标记的核心思想

当需要给区间 $[l, r]$ 内每个元素加上 $v$ 时，如果直接遍历到每个叶子节点修改，时间复杂度是 $O(n)$。

懒标记的巧妙之处在于：如果某个节点代表的区间完全包含在更新区间内，我们不需要立刻更新到叶子节点，而是：

更新该节点的 sum 值（加上 $v \times \text{区间长度}$）
在该节点上打上一个标记 lazy += v，表示”我的子树还有 $v$ 的增量没下传”
等到后续查询或更新需要访问子节点时，再将标记下传

这种”延迟处理”的策略，使得单次区间更新最多访问 $O(\log n)$ 个节点。

5.2 懒标记的下传（Push Down）

当需要访问某个节点的子节点时，必须先将该节点的懒标记下传给子节点：

/**
 * 懒标记下传
 * 将当前节点的懒标记传递给左右子节点
 * @param node  当前节点编号
 * @param left  当前节点区间左端点
 * @param right 当前节点区间右端点
 */
private void pushDown(int node, int left, int right) {
    if (lazy[node] == 0) {
        // 没有待下传的标记
        return;
    }

    int mid = left + (right - left) / 2;
    int leftChild = node * 2 + 1;
    int rightChild = node * 2 + 2;

    // 左子节点区间长度 = mid - left + 1
    long leftRange = mid - left + 1;
    // 右子节点区间长度 = right - mid
    long rightRange = right - mid;

    // 更新左子节点的sum和lazy
    tree[leftChild] += lazy[node] * leftRange;
    lazy[leftChild] += lazy[node];

    // 更新右子节点的sum和lazy
    tree[rightChild] += lazy[node] * rightRange;
    lazy[rightChild] += lazy[node];

    // 清除当前节点的懒标记
    lazy[node] = 0;
}

5.3 区间更新

/**
 * 对外接口：将区间 [updateLeft, updateRight] 内每个元素加上 value
 */
public void updateRange(int updateLeft, int updateRight, long value) {
    updateRange(0, 0, n - 1, updateLeft, updateRight, value);
}

/**
 * 递归区间更新
 * @param node        当前节点编号
 * @param left        当前节点区间左端点
 * @param right       当前节点区间右端点
 * @param updateLeft  更新区间左端点
 * @param updateRight 更新区间右端点
 * @param value       增量值
 */
private void updateRange(int node, int left, int right,
                         int updateLeft, int updateRight, long value) {
    // 当前区间完全在更新区间外
    if (right < updateLeft || left > updateRight) {
        return;
    }

    // 当前区间完全包含在更新区间内，打懒标记
    if (updateLeft <= left && right <= updateRight) {
        tree[node] += value * (right - left + 1);
        lazy[node] += value;
        return;
    }

    // 下传懒标记
    pushDown(node, left, right);

    int mid = left + (right - left) / 2;
    int leftChild = node * 2 + 1;
    int rightChild = node * 2 + 2;

    // 递归更新左右子树
    updateRange(leftChild, left, mid, updateLeft, updateRight, value);
    updateRange(rightChild, mid + 1, right, updateLeft, updateRight, value);

    // 更新当前节点的值
    tree[node] = tree[leftChild] + tree[rightChild];
}

六、单点更新

单点更新是区间更新的特例，但实现更简洁：

/**
 * 对外接口：单点更新，将索引 index 的元素更新为 value
 * 注意：这里是赋值操作，不是累加
 */
public void updatePoint(int index, long value) {
    updatePoint(0, 0, n - 1, index, value);
}

private void updatePoint(int node, int left, int right,
                         int index, long value) {
    if (left == right) {
        tree[node] = value;
        return;
    }

    pushDown(node, left, right);

    int mid = left + (right - left) / 2;
    int leftChild = node * 2 + 1;
    int rightChild = node * 2 + 2;

    if (index <= mid) {
        updatePoint(leftChild, left, mid, index, value);
    } else {
        updatePoint(rightChild, mid + 1, right, index, value);
    }

    tree[node] = tree[leftChild] + tree[rightChild];
}

七、完整代码与演示

/**
 * 线段树完整实现
 * 支持：区间查询、区间批量更新（懒标记）、单点更新
 * 时间复杂度：所有操作均为 O(log n)
 */
public class SegmentTree {

    private long[] tree;   // 区间和
    private long[] lazy;   // 懒标记
    private int[] nums;    // 原始数组
    private int n;

    public SegmentTree(int[] nums) {
        this.nums = nums;
        this.n = nums.length;
        this.tree = new long[n * 4];
        this.lazy = new long[n * 4];
        build(0, 0, n - 1);
    }

    // 构建线段树
    private void build(int node, int left, int right) {
        if (left == right) {
            tree[node] = nums[left];
            return;
        }
        int mid = left + (right - left) / 2;
        int lc = node * 2 + 1;
        int rc = node * 2 + 2;
        build(lc, left, mid);
        build(rc, mid + 1, right);
        tree[node] = tree[lc] + tree[rc];
    }

    // 懒标记下传
    private void pushDown(int node, int left, int right) {
        if (lazy[node] == 0) return;
        int mid = left + (right - left) / 2;
        int lc = node * 2 + 1;
        int rc = node * 2 + 2;
        long leftLen = mid - left + 1;
        long rightLen = right - mid;
        tree[lc] += lazy[node] * leftLen;
        lazy[lc] += lazy[node];
        tree[rc] += lazy[node] * rightLen;
        lazy[rc] += lazy[node];
        lazy[node] = 0;
    }

    // 区间更新 [ul, ur] += value
    public void updateRange(int ul, int ur, long value) {
        updateRange(0, 0, n - 1, ul, ur, value);
    }

    private void updateRange(int node, int left, int right,
                             int ul, int ur, long value) {
        if (right < ul || left > ur) return;
        if (ul <= left && right <= ur) {
            tree[node] += value * (right - left + 1);
            lazy[node] += value;
            return;
        }
        pushDown(node, left, right);
        int mid = left + (right - left) / 2;
        int lc = node * 2 + 1;
        int rc = node * 2 + 2;
        updateRange(lc, left, mid, ul, ur, value);
        updateRange(rc, mid + 1, right, ul, ur, value);
        tree[node] = tree[lc] + tree[rc];
    }

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

    private long query(int node, int left, int right,
                       int ql, int qr) {
        if (right < ql || left > qr) return 0;
        if (ql <= left && right <= qr) return tree[node];
        pushDown(node, left, right);
        int mid = left + (right - left) / 2;
        int lc = node * 2 + 1;
        int rc = node * 2 + 2;
        return query(lc, left, mid, ql, qr)
             + query(rc, mid + 1, right, ql, qr);
    }

    // 单点更新
    public void updatePoint(int index, long value) {
        updatePoint(0, 0, n - 1, index, value);
    }

    private void updatePoint(int node, int left, int right,
                             int index, long value) {
        if (left == right) {
            tree[node] = value;
            return;
        }
        pushDown(node, left, right);
        int mid = left + (right - left) / 2;
        int lc = node * 2 + 1;
        int rc = node * 2 + 2;
        if (index <= mid) {
            updatePoint(lc, left, mid, index, value);
        } else {
            updatePoint(rc, mid + 1, right, index, value);
        }
        tree[node] = tree[lc] + tree[rc];
    }

    // 主程序演示
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        SegmentTree st = new SegmentTree(arr);

        System.out.println("初始数组: [1, 3, 5, 7, 9, 11]");
        System.out.println("区间 [0, 2] 的和 = " + st.query(0, 2)); // 1+3+5 = 9
        System.out.println("区间 [2, 5] 的和 = " + st.query(2, 5)); // 5+7+9+11 = 32

        System.out.println("\n将区间 [1, 4] 每个元素加 10");
        st.updateRange(1, 4, 10);
        // 数组变为 [1, 13, 15, 17, 19, 11]
        System.out.println("区间 [0, 5] 的和 = " + st.query(0, 5)); // 1+13+15+17+19+11 = 76
        System.out.println("区间 [1, 3] 的和 = " + st.query(1, 3)); // 13+15+17 = 45

        System.out.println("\n将索引 2 更新为 100");
        st.updatePoint(2, 100);
        System.out.println("区间 [0, 5] 的和 = " + st.query(0, 5)); // 1+13+100+17+19+11 = 161
    }
}

八、复杂度分析

操作	时间复杂度	空间复杂度	说明
构建	$O(n)$	$O(4n)$	每个节点访问一次
区间查询	$O(\log n)$	$O(1)$ 额外	最多访问 $4 \log n$ 个节点
区间更新	$O(\log n)$	$O(1)$ 额外	懒标记减少不必要的递归
单点更新	$O(\log n)$	$O(1)$ 额外	从根走到叶子

九、扩展与应用场景

线段树的变形非常灵活，除了区间求和，还可以支持：

区间最值：维护 max 或 min 代替 sum
区间覆盖：懒标记记录覆盖值而非增量
区间乘加混合：维护乘法标记和加法标记
二维线段树：处理矩阵区间问题
动态开点线段树：节点按需创建，节省空间

典型应用场景：

日程冲突检测：区间覆盖查询
温度统计系统：实时区间求和/最值
游戏技能伤害范围计算：范围内单位属性批量修改
股票区间统计：某段时间内的成交量总和

十、总结

线段树是区间问题的”瑞士军刀”，其核心设计思想有三点：

分治建树：将区间二分，构建完全二叉树结构，使树高控制在 $O(\log n)$
懒标记延迟：区间更新时不急于修改到叶子，而是先打标记，需要时再下传，保证 $O(\log n)$ 的更新效率
信息合并：每个节点维护区间聚合信息（和、最大值等），查询时合并子树结果

掌握线段树后，你将能优雅地解决大量区间查询与修改问题，这是算法面试和工程实践中的高频考点。

Tagged with: 二叉树分治区间查询懒标记线段树