Java线段树入门详解（从零开始掌握区间查询与更新的高效数据结构）

例如，对于数组 [1, 3, 5, 7, 9, 11]，线段树可以快速回答“区间 [1,4] 的和是多少？”或“将区间 [2,5] 所有元素加 2”这类问题，时间复杂度仅为 O(log n)。

线段树的基本操作

线段树主要支持两种操作：

• 区间查询（Range Query）：如求区间和、最大值等。
• 区间更新（Range Update）：如给某段区间所有元素加上一个值。

为了高效处理区间更新，我们通常使用一种叫懒标记（Lazy Propagation）的技术，避免每次更新都递归到底层。

Java实现线段树（支持区间求和与区间加法）

下面是一个完整的 Java 线段树实现，包含构建、查询和带懒标记的区间更新功能。

public class SegmentTree {    private long[] tree;      // 线段树数组    private long[] lazy;      // 懒标记数组    private int n;            // 原数组长度    // 构造函数：根据原数组构建线段树    public SegmentTree(int[] arr) {        this.n = arr.length;        this.tree = new long[4 * n];  // 通常开4倍空间        this.lazy = new long[4 * n];        build(arr, 0, 0, n - 1);    }    // 递归构建线段树    private void build(int[] arr, int node, int start, int end) {        if (start == end) {            tree[node] = arr[start];        } else {            int mid = (start + end) / 2;            build(arr, 2 * node + 1, start, mid);            build(arr, 2 * node + 2, mid + 1, end);            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];        }    }    // 区间查询：[l, r]    public long query(int l, int r) {        return query(0, 0, n - 1, l, r);    }    private long query(int node, int start, int end, int l, int r) {        // 先处理懒标记        if (lazy[node] != 0) {            tree[node] += (end - start + 1) * lazy[node];            if (start != end) {                lazy[2 * node + 1] += lazy[node];                lazy[2 * node + 2] += lazy[node];            }            lazy[node] = 0;        }        if (r < start || end < l) {            return 0; // 无交集        }        if (l <= start && end <= r) {            return tree[node]; // 完全包含        }        int mid = (start + end) / 2;        long leftSum = query(2 * node + 1, start, mid, l, r);        long rightSum = query(2 * node + 2, mid + 1, end, l, r);        return leftSum + rightSum;    }    // 区间更新：将 [l, r] 每个元素加上 val    public void update(int l, int r, int val) {        update(0, 0, n - 1, l, r, val);    }    private void update(int node, int start, int end, int l, int r, int val) {        // 先处理当前节点的懒标记        if (lazy[node] != 0) {            tree[node] += (end - start + 1) * lazy[node];            if (start != end) {                lazy[2 * node + 1] += lazy[node];                lazy[2 * node + 2] += lazy[node];            }            lazy[node] = 0;        }        if (r < start || end < l) {            return; // 无交集        }        if (l <= start && end <= r) {            // 当前区间完全被覆盖            tree[node] += (long)(end - start + 1) * val;            if (start != end) {                lazy[2 * node + 1] += val;                lazy[2 * node + 2] += val;            }            return;        }        int mid = (start + end) / 2;        update(2 * node + 1, start, mid, l, r, val);        update(2 * node + 2, mid + 1, end, l, r, val);        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];    }}

如何使用这个线段树？

下面是一个简单的使用示例：

public class Main {    public static void main(String[] args) {        int[] arr = {1, 3, 5, 7, 9, 11};        SegmentTree st = new SegmentTree(arr);        // 查询区间 [1, 3] 的和：3 + 5 + 7 = 15        System.out.println(st.query(1, 3)); // 输出 15        // 将区间 [0, 2] 每个元素加 2        st.update(0, 2, 2);        // 再次查询 [1, 3]：(3+2) + (5+2) + 7 = 5 + 7 + 7 = 19        System.out.println(st.query(1, 3)); // 输出 19    }}

为什么需要懒标记？

如果没有懒标记，每次区间更新都要递归到所有叶子节点，时间复杂度退化为 O(n)。而懒标记的思想是“延迟更新”——只在真正需要访问子节点时才把更新操作下传，从而保证每次操作都是 O(log n)。

总结

通过本教程，你已经掌握了：

• 什么是Java线段树
• 如何实现支持区间查询和区间更新的线段树
• 懒标记的作用与实现原理

线段树是解决区间问题的强大工具，在 LeetCode、Codeforces 等平台的算法题中频繁出现。建议你动手敲一遍代码，加深理解！

希望这篇教程能帮助你顺利入门线段树。如果你觉得有用，欢迎分享给更多学习 Java语言线段树 的朋友！