线段树核心结构用数组模拟完全二叉树，下标从1开始，tree大小至少4n，左右子节点为2i和2*i+1，每个节点维护区间[l,r]，建树递归划分，叶子存单点值。
线段树的核心结构怎么写（C++基础模板）
线段树不是必须用指针实现的，数组模拟更常用、更快、也更不容易内存泄漏。核心是用一棵完全二叉树（下标从 1 开始）表示区间划分，每个节点存对应区间的聚合信息（比如和、最值等）。
关键点在于：
- tree 数组大小至少为 4 * n（安全起见，避免越界）
- 左右子节点下标分别是 2 * i 和 2 * i + 1（根为 1）
- 每个节点维护区间 [l, r]，建树时递归划分，叶子节点对应单点
vector<long long> tree;
vector<int> a; // 原数组，0-indexed
<p>void build(int i, int l, int r) {
if (l == r) {
tree[i] = a[l];
return;
}
int mid = (l + r) / 2;
build(2<em>i, l, mid);
build(2</em>i+1, mid+1, r);
tree[i] = tree[2<em>i] + tree[2</em>i+1]; // 示例：维护区间和
}</p>
单点修改和区间查询怎么写（最常用操作）
单点修改本质是“找到对应叶子，向上更新所有祖先”；区间查询则是“递归覆盖，能整段用就用，不能就拆”。两者都依赖区间是否相交的判断逻辑。
常见错误： - 查询时忘了检查当前节点区间与目标区间无交集（应直接返回默认值） - 修改时传错下标（原数组是 0-indexed，线段树内部统一用 0-indexed 区间） - 忘记 push_up 更新父节点
void update(int i, int l, int r, int idx, int val) {
if (l == r) {
tree[i] = val;
return;
}
int mid = (l + r) / 2;
if (idx <= mid) update(2*i, l, mid, idx, val);
else update(2*i+1, mid+1, r, idx, val);
tree[i] = tree[2*i] + tree[2*i+1];
}
<p>long long query(int i, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0; // 无交集
if (ql <= l && r <= qr) return tree[i]; // 完全覆盖
int mid = (l + r) / 2;
return query(2<em>i, l, mid, ql, qr) + query(2</em>i+1, mid+1, r, ql, qr);
}</p>
懒标记（lazy propagation）什么时候必须加
只有涉及区间修改（比如“把 [l,r] 全部加 x”）时才需要 lazy。单点修改不需要，强行加反而引入 bug。
为什么必须加： - 不加会导致每次区间修改退化成 O(n) - lazy 的本质是“延迟更新”，只在必要时下推（push_down），并标记子节点待更新
容易踩的坑：
- push_down 忘了清空当前节点的 lazy[i]
- 下推时没把 lazy 值“累加”到子节点 lazy 上（而是覆盖），导致多次修改丢失
- 查询/修改进入子树前没调用 push_down
vector<long long> lazy;
<p>void push_down(int i, int l, int r) {
if (lazy[i] == 0) return;
tree[i] += lazy[i] <em> (r - l + 1); // 假设是区间加法
if (l != r) {
lazy[2</em>i] += lazy[i];
lazy[2*i+1] += lazy[i];
}
lazy[i] = 0;
}</p>
建树和调用时的边界细节（最容易出错的地方）
C++ 里最常翻车的是下标体系混乱：原数组用 0-indexed，线段树节点也该统一用 0-indexed 区间，但树数组下标从 1 开始。别混用 1-indexed 原数组或手写 mid+1 写成 mid。
立即学习“C++免费学习笔记（深入）”；
务必确认：
- build(1, 0, n-1) —— 根节点编号 1，覆盖原数组索引 [0, n-1]
- 所有 query/update 调用里的区间端点都是 0-indexed
- tree 和 lazy 大小都开到 4 * n，别信“2 * n 够用”这种说法
- 如果用 int 存和，注意溢出，宁可用 long long
复杂点其实不在结构本身，而在于每次修改或查询时，是否完整走通了“检查交集 → 判断覆盖 → 分治递归 → 合并结果 → 更新父节点”的链条。漏掉任意一环，结果就不可靠。
