绝大多数实际场景下，用数组实现线段树更合适，因其结构固定、缓存友好、不易出错且支持快速初始化；需开4×n大小、下标从1开始，并配合懒标记优化区间修改。
线段树用数组还是指针实现更合适
绝大多数实际场景下，用 vector 或普通数组实现线段树比动态指针树更优。原因很实在：指针版写起来容易出错（内存泄漏、空指针解引用）、缓存不友好、常数大；而数组版结构固定、下标规则明确（tree[i] 的左右子节点是 tree[2*i] 和 tree[2*i+1]），且支持批量初始化和快速重置。
注意点：
- 数组大小至少要开到
4 * n，不能只开2*n—— 否则在非 2 的幂长度时会越界 - 下标从 1 开始用（即
tree[1]是根）比从 0 开始逻辑更干净，避免父子下标公式里反复加减 1 - 如果数据范围可能达
1e5，别用int tree[200005]这种栈上静态数组，改用vector<long long> tree</long>
区间修改必须用懒标记（lazy tag）吗
不是“必须”，但不用就大概率超时或写错。比如对长度为 1e5 的数组做 1e4 次区间加法，暴力更新每个叶子节点，最坏 O(n) × O(q) = 1e9，稳 TLE。
懒标记本质是延迟传播：只在真正需要访问子区间时才把父节点的未处理操作推下去。关键操作有三个：
立即学习“C++免费学习笔记（深入）”；
-
push_down(idx, l, r)：把lazy[idx]加到左右子节点的lazy上，并更新tree[idx]值，最后清空lazy[idx] - 所有
update和query进入子区间前，必须先调用push_down -
lazy数组类型要和操作匹配：区间加对应long long lazy[]，区间赋值则需额外标记是否“已赋值”
build、update、query 的递归边界怎么写才不出错
核心原则：递归函数的参数统一为 (idx, l, r, ql, qr, val) 形式，其中 [l, r] 是当前节点覆盖区间，[ql, qr] 是目标操作区间。边界判断只依赖这四个变量，不引入额外标志位。
常见错误写法：if (l == r) { tree[idx] = a[l]; return; } —— 这只适用于 build，混进 update 就崩了。
正确写法要点：
-
build(idx, l, r)：当l == r时直接赋值a[l]；否则递归建左右子树，再tree[idx] = tree[2*idx] + tree[2*idx+1] -
update(idx, l, r, ql, qr, val)：若qr 直接返回；若 <code>ql ，更新当前节点并设 <code>lazy[idx] += val，然后return；否则先push_down，再递归左右 -
query(idx, l, r, ql, qr)：同样先判无交集 / 完全包含；否则push_down后左右递归求和
单点修改和区间修改能共用同一套 update 函数吗
能，而且应该共用。单点修改只是区间修改的特例：令 ql == qr 即可。强行拆成两个函数会导致重复逻辑、维护成本高、容易漏修 bug。
实操建议：
- 把 update 接口设计为
void update(int ql, int qr, long long val)，内部调用私有递归函数 - 如果业务中存在“单点赋值”和“区间加”两种语义，不要重载函数名，而是加一个枚举参数
OpType，并在push_down和合并逻辑里区分处理 - 测试时务必覆盖三种 case：单点（1,1）、跨中点（1,n/2+1）、完全左偏（1,10）—— 很多 bug 只在特定区间形状下暴露
class SegmentTree {
int n;
vector<long long> tree, lazy;
void push_down(int idx, int l, int r) {
if (lazy[idx] == 0) return;
tree[idx] += lazy[idx] * (r - l + 1);
if (l != r) {
lazy[idx * 2] += lazy[idx];
lazy[idx * 2 + 1] += lazy[idx];
}
lazy[idx] = 0;
}
void update(int idx, int l, int r, int ql, int qr, long long val) {
push_down(idx, l, r);
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
lazy[idx] += val;
push_down(idx, l, r); // 立即生效，保证 tree[idx] 正确
return;
}
int mid = (l + r) / 2;
update(idx * 2, l, mid, ql, qr, val);
update(idx * 2 + 1, mid + 1, r, ql, qr, val);
tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
}
public:
SegmentTree(int size, const vector<int>& a) : n(size), tree(4 * n), lazy(4 * n) {
function<void(int, int, int)> build = [&](int idx, int l, int r) {
if (l == r) {
tree[idx] = a[l];
return;
}
int mid = (l + r) / 2;
build(idx * 2, l, mid);
build(idx * 2 + 1, mid + 1, r);
tree[idx] = tree[idx * 2] + tree[idx * 2 + 1];
};
build(1, 0, n - 1);
}
void update(int l, int r, long long val) {
update(1, 0, n - 1, l, r, val);
}
long long query(int l, int r) {
// query 实现类似 update，此处省略
return 0;
}
};
数组大小、懒标记传播时机、递归入口的区间闭合性——这三个地方出错，调试起来最费时间。
