如果你也有类似的经历，恭喜你，你不是一个人。线段树被誉为“数据结构的分水岭”——迈过去，区间问题对你来说将如履平地；迈不过去，你可能会在“能看懂但写不出来”的泥潭里挣扎很久。
本文用 C++ 作为实现语言，从零开始，手撕一份“拿来就能改，改了就能用”的线段树代码模板。全文约2000字，包含基础版、懒标记版、以及 C++ 特有的封装技巧。读完这篇，希望你能自信地说出：“线段树，不过如此。”
一、线段树到底难在哪儿？
在动笔之前，我们先复盘一下线段树让初学者自闭的几个核心痛点：
1. 递归的“递”与“归”容易乱
线段树基于完全二叉树，建树、更新、查询都采用递归写法。很多人能理解“递下去”，但回溯时的合并（pushUp）和标记下推（pushDown）的顺序一多，大脑就栈溢出了。
2. 边界条件极其敏感
以区间 [l, r] 为例，mid = (l + r) / 2 后，左孩子区间是 [l, mid]，右孩子是 [mid+1, r]。如果写成 [l, mid-1] 和 [mid, r]，要么漏掉元素，要么死递归。这种错误肉眼很难发现。
3. 懒标记的“借贷”逻辑
区间更新如果不加懒标记，复杂度会退化为 O(n)。懒标记的本质是“先欠着，等需要时再还”。但“什么时候下传、下传给谁、下传后如何清除”这三个问题，至少能让初学者错三次。
4. C++ 特有的内存和语法陷阱
-
数组开多大？4 * N 是经验值，有人开小了导致越界 RE。
-
递归深度：极端情况下树高约 log N，一般不会爆栈，但如果你在递归里写了死循环，那就另说了。
-
全局数组 vs 动态分配：用 vector 动态扩容更安全，但很多人习惯 int tree[maxn<<2]。
正因为这些难点，线段树才需要一套稳定的代码模板。下面我们就从最基础的版本开始，逐步构建一个健壮的 C++ 线段树。
二、基础框架：不带懒标记的单点修改 + 区间查询
这个版本是线段树的“Hello World”。我们用 C++ 数组实现，支持：
-
建树（build）
-
单点更新（update）
-
区间查询（query，例如区间求和）
2.1 数组存储与命名约定
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int a[MAXN];
int tree[4 * MAXN];
void pushUp(int p) {
tree[p] = tree[p << 1] + tree[p << 1 | 1];
}
这里 p << 1 等价于 p * 2，p << 1 | 1 等价于 p * 2 + 1，位运算写法在竞赛代码中很常见。
2.2 建树（build）
void build(int p, int l, int r) {
if (l == r) {
tree[p] = a[l];
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
pushUp(p);
}
关键点：只有叶子节点（l == r）才直接赋值，内部节点通过 pushUp 由孩子算出。
2.3 单点更新
void update(int p, int l, int r, int pos, int val) {
if (l == r) {
tree[p] = val;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(p << 1, l, mid, pos, val);
else update(p << 1 | 1, mid + 1, r, pos, val);
pushUp(p);
}
2.4 区间查询
int query(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return tree[p];
}
int mid = (l + r) >> 1;
int res = 0;
if (ql <= mid) res += query(p << 1, l, mid, ql, qr);
if (qr > mid) res += query(p << 1 | 1, mid + 1, r, ql, qr);
return res;
}
这个基础版本已经能解决不少题目（例如 HDU 1166 敌兵布阵）。但一旦要求区间修改（比如把 [L,R] 内每个数都加上 v），这个版本就会超时，因为每次更新都要递归到所有叶子。于是，懒标记（Lazy Propagation）登场了。
三、进阶核心：区间修改 + 懒标记（最难啃的骨头）
懒标记的精髓：当要修改的区间完全覆盖当前节点区间时，不递归到孩子，而是：
-
更新当前节点的 tree 值（注意要乘以区间长度）
-
在当前节点上打一个标记，表示“我的孩子还没有更新，以后用到时再下传”
3.1 增加懒标记数组
3.2 下推操作（pushDown）
这是最容易写错的地方。以下是一个标准的“区间加”的 pushDown 实现：
void pushDown(int p, int l, int r) {
if (lazy[p] != 0) {
int mid = (l + r) >> 1;
int left = p << 1, right = p << 1 | 1;
lazy[left] += lazy[p];
tree[left] += lazy[p] * (mid - l + 1);
lazy[right] += lazy[p];
tree[right] += lazy[p] * (r - mid);
lazy[p] = 0;
}
}
三处易错点：
3.3 区间更新（updateRange）
void updateRange(int p, int l, int r, int ul, int ur, int val) {
if (ul <= l && r <= ur) {
tree[p] += val * (r - l + 1);
lazy[p] += val;
return;
}
pushDown(p, l, r);
int mid = (l + r) >> 1;
if (ul <= mid) updateRange(p << 1, l, mid, ul, ur, val);
if (ur > mid) updateRange(p << 1 | 1, mid + 1, r, ul, ur, val);
pushUp(p);
}
3.4 带懒标记的区间查询
查询时同样需要先 pushDown，确保访问到的孩子数据是最新的。
int queryRange(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return tree[p];
}
pushDown(p, l, r);
int mid = (l + r) >> 1;
int res = 0;
if (ql <= mid) res += queryRange(p << 1, l, mid, ql, qr);
if (qr > mid) res += queryRange(p << 1 | 1, mid + 1, r, ql, qr);
return res;
}
至此，一个支持区间加、区间求和的线段树就完成了。总代码大约 80~100 行。如果你能熟练默写以上结构，你已经击败了 70% 的初学者。
四、C++ 封装：用结构体让你告别全局变量
上述代码中，tree、lazy、a 都是全局数组，在单题中没问题，但如果一道题有多个线段树实例（例如对不同的数组分别维护），全局方式就显得笨拙。C++ 的 class 或 struct 可以完美封装线段树，而且能利用构造函数自动分配内存。
下面给出一个使用 vector 的封装版，支持任意长度的数组，并且模板参数可以指定“合并操作”。
template<typename T>
class SegTree {
private:
int n;
vector<T> tree, lazy;
vector<T> *arr;
void pushUp(int p) {
tree[p] = tree[p<<1] + tree[p<<1|1];
}
void pushDown(int p, int l, int r) {
if (lazy[p] != 0) {
int mid = (l + r) >> 1;
int left = p<<1, right = p<<1|1;
lazy[left] += lazy[p];
tree[left] += lazy[p] * (mid - l + 1);
lazy[right] += lazy[p];
tree[right] += lazy[p] * (r - mid);
lazy[p] = 0;
}
}
void build(int p, int l, int r) {
if (l == r) {
tree[p] = (*arr)[l];
return;
}
int mid = (l + r) >> 1;
build(p<<1, l, mid);
build(p<<1|1, mid+1, r);
pushUp(p);
}
void update(int p, int l, int r, int ul, int ur, T val) {
if (ul <= l && r <= ur) {
tree[p] += val * (r - l + 1);
lazy[p] += val;
return;
}
pushDown(p, l, r);
int mid = (l + r) >> 1;
if (ul <= mid) update(p<<1, l, mid, ul, ur, val);
if (ur > mid) update(p<<1|1, mid+1, r, ul, ur, val);
pushUp(p);
}
T query(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[p];
pushDown(p, l, r);
int mid = (l + r) >> 1;
T res = 0;
if (ql <= mid) res += query(p<<1, l, mid, ql, qr);
if (qr > mid) res += query(p<<1|1, mid+1, r, ql, qr);
return res;
}
public:
SegTree(vector<T>& _arr, int _n) {
n = _n;
arr = &_arr;
tree.resize(4 * n + 5, 0);
lazy.resize(4 * n + 5, 0);
build(1, 1, n);
}
void rangeAdd(int l, int r, T val) {
update(1, 1, n, l, r, val);
}
T rangeSum(int l, int r) {
return query(1, 1, n, l, r);
}
};
使用示例：
vector<int> v = {0, 1, 2, 3, 4, 5};
SegTree<int> st(v, 5);
st.rangeAdd(2, 4, 10);
cout << st.rangeSum(1, 5) << endl;
封装的好处：代码复用性高，且可以通过模板支持 int、long long 等类型，未来升级成区间最大值、区间赋值等也只需修改 pushUp 和 pushDown 内部的运算。
五、常见错误与调试心法（血的教训）
-
数组越界
线段树开 4*N 是底线，但如果你使用了 vector 动态扩容，记得 resize(4*n+5)。如果开小了，可能在递归很深时访问越界，导致 RE 或莫名 WA。
-
pushDown 位置错误
黄金法则：任何需要进入孩子分支的地方，必须先 pushDown（除非你能绝对保证当前节点没有待下传的标记）。查询和更新都需要。
-
区间长度计算错误
tree[left] += lazy[p] * (mid - l + 1) 这里的 (mid - l + 1) 是左儿子区间的长度，有人误写成 (r - l + 1) 或 (r - mid)，导致数值错误。
-
递归爆栈
一般不会，因为树高只有约 20（N=1e5）。但如果写错了递归终止条件导致无限递归，就会爆栈。解决：在递归函数开头加 if (l > r) return; 作为防御。
-
多组数据时没有清空 lazy
如果使用全局数组，每组新数据前要 memset(tree, 0, sizeof tree) 和 memset(lazy, 0, sizeof lazy)。用 vector 封装则没有这个问题。
调试技巧：
-
对极端小数据（n=1,2,3）手动模拟递归过程，打印每个节点的 (l,r) 和值。
-
写一个暴力函数（直接循环计算区间和）与线段树结果对拍。
-
在 pushUp、pushDown 里用 static int cnt 计数，观察调用次数是否合理。
六、从模板到实战：下一步学什么？
掌握了“区间加、区间求和”模版后，你已经可以解决掉大部分难度在“提高-”级别的线段树题。但真正的挑战还在后面：
-
区间修改类型变化：区间赋值、区间乘、区间开方——每种操作对应的 pushDown 逻辑都不同。对于“区间加乘混合”，需要两个标记并规定顺序（一般是先乘后加）。
-
维护更多信息：区间最大子段和、区间最大公约数、区间最值 + 最值个数。你需要定义 struct Node 并在 pushUp 中合并。
-
可持久化线段树（主席树）：在静态数组上支持查询历史版本，是线段树的又一进阶。
无论多么复杂，只要你把本文的基础骨架刻进脑子里，所有的扩展都只是往骨架里填充不同的业务逻辑。
七、结语：手撕线段树，从这一刻开始
C++ 线段树之所以难写，是因为它同时对递归思维、边界控制、懒标记逻辑和 C++ 语法提出了不低的要求。但它也是回报率极高的数据结构——一旦你亲手写出了第一个 AC 的线段树，你会发现以前觉得头疼的区间问题，现在都能用一套统一的框架优雅地解决。
最后，送你一份“默写检查清单”：
-
build 函数：递归终止 l==r，记得 pushUp
-
pushDown 函数：非空标记时更新孩子 tree 和 lazy，乘以对应长度，最后清空当前标记
-
updateRange 函数：完全覆盖则打标记并返回；否则 pushDown，递归左右，最后 pushUp
-
queryRange 函数：完全覆盖则返回；否则 pushDown，递归左右，合并结果
拿起你的键盘，照着这个清单敲一遍，然后去洛谷做 P3372 【模板】线段树 1。当你看到绿色的 AC 时，你会明白：所有的手撕，都是为了最后的喜悦。 |
