线段树是高效解决区间动态查询与更新问题的数据结构，支持O(log n)时间复杂度的区间和、最值查询及单点/区间更新，核心包括建树、查询、单点更新和懒惰传播四大操作。
线段树是解决区间动态查询（如区间和、最值）与单点/区间更新问题的高效数据结构，核心在于用二叉树表示区间划分，支持 O(log n) 时间完成查询和修改。
构建线段树：自底向上划分区间
线段树每个节点代表一个区间 [l, r]，根节点覆盖整个数组范围 [0, n−1]；叶子节点对应单个元素；非叶子节点的左右子树分别覆盖左半区间和右半区间。建树采用递归方式：
- 若 l == r，当前节点存储 arr[l] 的值，为叶子节点
- 否则计算 mid = (l + r) / 2，递归构建左子树 [l, mid] 和右子树 [mid+1, r]
- 当前节点的值由左右子节点合并而来（如求和则 sum = left.sum + right.sum）
区间查询：递归拆分匹配区间
查询 [ql, qr] 范围内信息时，从根开始向下遍历，根据当前节点区间 [l, r] 与查询区间的关系决定处理逻辑：
- 若 [l, r] 完全在 [ql, qr] 内，直接返回该节点值
- 若 [l, r] 与 [ql, qr] 无交集，返回中性值（如求和返回 0，求最大值返回 −∞）
- 否则递归查询左右子树，并合并结果（如求和就相加，求最大值取 max）
单点更新：定位叶子后向上回溯维护
修改位置 idx 的值为 val 时，先找到对应叶子节点（路径由 idx 在区间中的归属决定），更新其值，再逐层向上更新所有祖先节点：
- 递归进入左子树或右子树，直到 l == r == idx
- 更新叶子值后，在返回过程中重新计算父节点值（如 sum = left.sum + right.sum）
- 整个过程只访问 O(log n) 个节点
懒惰传播：支持区间更新的关键优化
当需要对区间 [l, r] 执行统一操作（如全部加 v），暴力更新每个点会退化为 O(n)。懒惰传播引入延迟标记（lazy tag）：
- 每个节点额外记录一个 lazy 值，表示该区间待执行但尚未下推的操作
- 查询或更新前，若当前节点有 lazy 标记，先应用到自身，并将标记下传给子节点（同时清空当前标记）
- 区间更新时，若当前节点区间完全被覆盖，直接更新本节点值并打上 lazy 标记，不再往下递归
不复杂但容易忽略细节：数组大小要开到 4×n（避免越界），下标常用 0-based，合并操作需满足结合律，懒标记的设计要与操作类型匹配（如加法标记可累加，赋值标记需覆盖）。
