想象你在处理一个班级成绩表，老师要求你频繁完成以下操作：
查询某个区间的最高分（比如3-5号学生的最高分）
更新某位同学的分数（如把第7号同学的分数+10）
如果每次查询都遍历整个数组，更新时再重新计算，数据量大时会直接跪掉。这时候，线段树就是你的救命稻草——它能在O(log n)时间内搞定这些操作！
核心概念讲解
线段树是一棵二叉树，每个节点代表一个区间的聚合信息（比如最大值、和、最小值等）。它的核心思想是分治：
叶子节点存储单个元素值
非叶子节点存储子节点合并的结果（如
node.val = max(left.val, right.val)）建树时间复杂度 O(n)，因为每个点只会被访问一次
查询/更新时间复杂度 O(log n)，通过递归快速定位到目标区间
图示：一个简单的线段树，存储的是区间最大值
C++代码示例
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int tr[N << 2], a[N]; // tr: 线段树数组；a: 原始数组
// 单点更新：将下标x的值增加delta
void update(int u, int l, int r, int x, int delta) {
if (l == r) { // 到达叶子节点，直接更新
tr[u] += delta;
return;
}
int mid = l + r >> 1;
if (x <= mid) update(u << 1, l, mid, x, delta); // 更新左子树
else update(u << 1 | 1, mid + 1, r, x, delta); // 更新右子树
pushup(u); // 向上合并左右子树结果
}
// 区间最大值查询 [L, R]
int query_max(int u, int l, int r, int L, int R) {
if (L <= l && r <= R) return tr[u]; // 当前区间完全包含在查询区间内
int mid = l + r >> 1, res = INT_MIN;
if (L <= mid) res = max(res, query_max(u << 1, l, mid, L, R)); // 查询左子树
if (R > mid) res = max(res, query_max(u << 1 | 1, mid + 1, r, L, R)); // 查询右子树
return res;
}
// 合并子节点信息（最大值场景）
void pushup(int u) {
tr[u] = max(tr[u << 1], tr[u << 1 | 1]);
}
// 建树：初始化线段树
void build(int u, int l, int r) {
if (l == r) { // 叶子节点，存储原数组值
tr[u] = a[l];
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u); // 合并子节点
}
int main() {
int n; cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
build(1, 1, n); // 建树，区间[1,n]
int op, x, y;
while (cin >> op >> x >> y) {
if (op == 1) { // 查询 [x,y] 的最大值
cout << query_max(1, 1, n, x, y) << '\n';
} else { // 将a[x]的值加上y
update(1, 1, n, x, y); // 调用更新函数
}
}
}
代码注释说明
update()：实现单点增量更新，递归找到叶子节点后修改并回溯更新父节点query_max()：查询区间最大值，若当前区间被完全包含则直接返回，否则递归左右子树取最大pushup()：合并子节点信息（此处为取最大值）build()：递归构建初始线段树，叶子节点存储原数组值
算法分析
时间复杂度：
建树：O(n)
查询/更新：O(log n)
空间复杂度：O(4n)（通常开4倍数组防爆）
适用场景：频繁区间查询 + 单点/区间更新的问题（如区间最大值、区间和等）
局限性：不支持动态插入删除（需替罪羊树等特殊结构）
经典例题
洛谷P3374【模板】线段树1
给定长度为n的数组，支持单点修改和区间求和操作。
解题思路：直接套用线段树模板，注意边界条件（如数组是1-indexed）。
推荐练习
进阶：支持区间赋值和懒惰标记
考察带懒标记的线段树优化技巧
结合DP和线段树优化
小结
线段树的核心是「分治」和「懒更新」，是竞赛中区间问题的首选数据结构。本例展示了如何用线段树高效处理区间最大值查询与单点更新，其O(log n)效率在面对百万级数据时仍能稳定发挥。下一期我们将深入讲解懒标记技术——进一步提升线段树的效率！