线段树通过预存区间和实现单点修改与区间求和均o(log n)，其按覆盖范围建树，根为[0,n−1]，非叶节点[l,r]拆为[l,mid]和[mid+1,r]，叶节点为[i,i]，节点值为对应区间和，数组空间开4×n。
用线段树解决区间动态求和问题，核心是把数组的每个区间信息“预存”进一棵平衡二叉树里，让每次单点修改和任意区间求和都稳定在 O(log n) 时间内完成。它比朴素遍历（O(n)）快得多，也比前缀和（更新 O(n)）更适合频繁修改的场景。
线段树怎么组织数据
它不是按元素顺序存，而是按“覆盖范围”建树：
- 根节点代表整个数组区间，比如 [0, n−1]
- 每个非叶子节点 [l, r] 拆成两个子区间：[l, mid] 和 [mid+1, r]，其中 mid = l + (r − l) / 2（避免整型溢出）
- 叶子节点对应单个下标，如 [i, i]，值就是原数组 arr[i]
- 每个节点存储其对应区间的和，父节点的和 = 左子节点和 + 右子节点和
- 为防越界，数组型线段树一般开 4 × n 空间
Java 实现关键三步
以数组 [1, 3, 5, 7] 为例，构建支持单点更新、区间求和的线段树：
deep-java-review
下载
Java项目代码review工具。分析Git变更+完整调用链路上下文，推断业务需求，进行多维度评分和分类汇总，生成完整PRD文档。包含细粒度Java代码审查清单（Null安全、异常处理、Streams、并发、equals/hashCode、资源管理、API设计、性能、MyBatis/ORM、事务边界、SQL/DD...
- 建树（build）：递归划分区间，到底层赋值，回溯时合并子区间和
- 单点更新（update）：从根向下找到对应叶子，改完后沿路径向上逐层刷新父节点的和
-
区间查询（query）：对查询区间 [ql, qr] 和当前节点区间 [l, r] 分三类处理：
✓ 完全不交 → 返回 0
✓ 完全覆盖 → 直接返回该节点存的和
✓ 部分重叠 → 递归查左右子树，结果相加
为什么不用懒标记？
如果只做单点修改 + 区间求和，不需要懒标记。懒标记是为“区间更新”（如给 [2,5] 全体加 3）优化的。本场景中每次只改一个位置，更新路径唯一、长度仅 log n，直接自底向上 pushUp 就够了——代码更简、不易出错、性能不打折扣。
一段可运行的精简模板
以下为无懒标记、基于数组存储的标准实现：
class SegmentTree {private final int[] tree;
private final int n;
public SegmentTree(int[] arr) {
this.n = arr.length;
this.tree = new int[n * 4];
build(arr, 0, n - 1, 0);
}
private void build(int[] arr, int l, int r, int idx) {
if (l == r) {
tree[idx] = arr[l];
return;
}
int mid = l + (r - l) / 2;
build(arr, l, mid, idx * 2 + 1);
build(arr, mid + 1, r, idx * 2 + 2);
tree[idx] = tree[idx * 2 + 1] + tree[idx * 2 + 2];
}
public void update(int idx, int val) { update(0, n - 1, 0, idx, val); }
private void update(int l, int r, int node, int pos, int val) {
if (l == r) { tree[node] = val; return; }
int mid = l + (r - l) / 2;
if (pos else update(mid + 1, r, node * 2 + 2, pos, val);
tree[node] = tree[node * 2 + 1] + tree[node * 2 + 2];
}
public int query(int ql, int qr) { return query(0, n - 1, 0, ql, qr); }
private int query(int l, int r, int node, int ql, int qr) {
if (qr if (ql int mid = l + (r - l) / 2;
return query(l, mid, node * 2 + 1, ql, qr) +
query(mid + 1, r, node * 2 + 2, ql, qr);
}
}
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
