线段树
进阶线段树把一个大区间拆成很多可组合的小区间。
// 算法讲解
线段树
会展示数组被拆成哪些区间，以及一次区间查询如何下钻命中的节点。
待机
速度 中
待机 ⌨1struct Node {
2 int l, r, sum;
3};
4
5vector<Node> seg;
6
7void pushUp(int p) {
8 seg[p].sum = seg[p << 1].sum + seg[p << 1 | 1].sum;
9}
10
11int query(int p, int ql, int qr) {
12 if (ql <= seg[p].l && seg[p].r <= qr) return seg[p].sum;
13 int mid = (seg[p].l + seg[p].r) >> 1;
14 int ans = 0;
15 if (ql <= mid) ans += query(p << 1, ql, qr);
16 if (qr > mid) ans += query(p << 1 | 1, ql, qr);
17 return ans;
18}
复杂度分析
时间 建树 O(n), 更新/查询 O(log n)
空间 O(n)
最优 O(log n)
最坏 O(log n)
算法讲解
线段树通过递归二分区间，把数组映射成一棵"节点负责一个区间"的树。
单点修改、区间查询、区间加法、区间赋值等问题，都可以通过节点信息合并来完成。
懒标记的意义在于"先记账，等真正访问到子区间时再下传"，避免每次都更新整棵子树。
它是很多高级数据结构与算法优化的起点，值得尽早熟悉。