线段树
Floating_Trees
·
·
算法·理论
理论
维护区间信息的数据结构，在 O(\log n) 的复杂度内实现各项操作。
线段树将每个长度不为 1 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。
懒惰标记
## 实现
对于 `update(k, L, R, val)`：
+ 若第 $k$ 个区间被 $[L,R]$ 包含，则 $tag_i + val$，$sum_i + val \times \text{区间长度}$。
+ 若第 $k$ 个区间部分被 $[L,R]$ 包含，则现将懒惰标记传给儿子节点，在对儿子节点进行 `update`，接着在用儿子节点更新当前节点。
+ 若第 $k$ 个区间与 $[L,R]$ 没有公共部分，则直接返回，无需更新。