线段树核心结构体采用数组式存储，tree大小为4*n，根节点编号为1，含n和tree成员；单点修改需递归定位叶子并回溯更新；区间查询须分无交、全含、部分重叠三种情况处理。
线段树的核心结构体怎么写
线段树在 C++ 中最常用的是数组式（堆式）存储，而非指针式——因为避免动态分配开销、缓存友好、代码简洁。关键点是：tree 数组大小至少为 4 * n（n 是原始数组长度），这是安全上界，能覆盖所有可能节点。
结构体里通常只存区间端点和值，不建议塞太多字段。例如支持「区间求和 + 单点修改」时，tree[i] 存的是对应区间的和：
struct SegmentTree {
vector tree;
int n;
SegmentTree(int size) : n(size), tree(4 * size, 0) {}
void build(const vectorzuojiankuohaophpcnintyoujiankuohaophpcn& arr, int node = 1, int l = 0, int r = -1) {
if (r == -1) r = n - 1;
if (l == r) {
tree[node] = arr[l];
return;
}
int mid = (l + r) / 2;
build(arr, node * 2, l, mid);
build(arr, node * 2 + 1, mid + 1, r);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}};
注意：这里用 node * 2 和 node * 2 + 1 表示左右子节点，根节点编号为 1（不是 0），这是标准堆式约定；若用 0 作根，则左子为 2*node+1，容易混淆，不推荐初学使用。
立即学习“C++免费学习笔记（深入）”；
单点修改的递归逻辑怎么写才不出错
单点修改本质是「从根往下找唯一包含该位置的叶子，改完再向上更新父节点」。常见错误是边界判断写反、忘记回溯更新、或误把 l == r 当成递归终止但没处理好 mid 计算。
-
update(pos, val, node, l, r) 的 pos 是原始数组下标（0-based），必须严格落在当前 [l, r] 内
- 递归时只进一个分支：若
pos 走左，否则走右
- 更新完子树后，一定要执行
tree[node] = tree[left] + tree[right]，漏这步会导致查询结果错误
示例实现：
void update(int pos, long long val, int node = 1, int l = 0, int r = -1) {
if (r == -1) r = n - 1;
if (l == r) {
tree[node] = val;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) {
update(pos, val, node * 2, l, mid);
} else {
update(pos, val, node * 2 + 1, mid + 1, r);
}
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}区间查询为什么不能直接用 (l, r) 套公式
区间查询不是数学公式代入，而是递归拆解覆盖过程。典型错误是认为「只要当前节点区间被查询区间完全包含，就直接返回 tree[node]」，却忽略：若查询区间跨中点，必须拆成两段分别查，再合并结果。
正确逻辑分三种情况：
- 当前区间
[l, r] 与查询区间 [ql, qr] 无交集 → 返回单位元（如求和返回 0）
- 当前区间被完全包含 → 直接返回
tree[node]
- 部分重叠 → 递归查左右子树，返回二者之和
注意：边界比较必须用 ，不是 ；且查询函数应返回值，不是 void：
long long query(int ql, int qr, int node = 1, int l = 0, int r = -1) {
if (r == -1) r = n - 1;
if (qr < l || r < ql) return 0; // 无交集
if (ql <= l && r <= qr) return tree[node]; // 完全包含
int mid = (l + r) / 2;
return query(ql, qr, node * 2, l, mid) +
query(ql, qr, node * 2 + 1, mid + 1, r);
}为什么 build / update / query 都要手动传参而不是封装成类成员方法
初学者常把 l、r 提成类成员变量，结果发现多组查询会互相污染。根本原因是：线段树每个递归调用都依赖当前节点对应的区间范围，这个范围随调用栈深度变化，无法全局固定。
所以必须让 l 和 r 作为参数层层传递。虽然看起来啰嗦，但这是最清晰、最不易出错的方式。C++17 后可用 std::optional 或默认参数简化接口（如上面示例用 r = -1 触发初始化），但底层逻辑不变。
另一个易忽略点：所有操作的时间复杂度都是 O(log n)，但常数较大。如果只是做单点改 + 单点查，用普通数组就够了；只有真需要「任意区间求和/最小值/最大值」时，线段树才有意义。
