提高组线段树汇总
下标线段树下标线段树即最普通的线段树，用来维护一个区间 \(\) 的信息，可以发现这其实对应了数组里面的下标，故称其为下标线段树
基本原理
对于每个节点 \(\)，左儿子是 \(\)，右儿子是 \(\)，\(mid=(l+r)/2\)（向下取整）
我们发现除了最后一层是一个满二叉树，于是我们就可以用与二叉堆类似的方法存储
对于一个编号为 \(x\) 的节点，父亲节点 \(x/2\)（x >> 1）（向下取整），左儿子 \(2x\)（x1; build(umid\) 只递归右边
剩下的情况需要递归左边和右边，这种情况最多发生一次，之后便会变成上述两种情况。因此复杂度为 \(O(2\log n)\) 忽略常数还是 \(O(\log n)\) 的
[*]\(\cap= \varnothing\)，这种情况是不存在的
总结一下操作过程：
[*]若 \(\) 完全覆盖了当前节点所覆盖的区间，则立即回溯，并且该节点的值做为一个备选答案
[*]若左子节点与 \(\) 有重叠部分，则递归访问左子节点
[*]若右子节点与 \(\) 有重叠部分，则递归访问右子节点
push down：给一个区间加上一个数，更新到两个子节点
例题
I. 最大数
因为动态添加比较麻烦，所以我们直接建 \(1\sim m\) 个空间就行了（最多 \(m\) 个操作，也就是 \(m\) 个空间），每次新增一个数的时候相当于直接修改，问后 \(L\) 个数里面最大值就是问 \(\)（\(n\) 在每次加数的时候也顺带 ++）
#include using namespace std;const int N = 200005;struct Node{ int l, r; //左儿子右儿子 int v; //记录的最大值}tr;//建树void build(int u, int l, int r){ tr = { l,r }; if (l == r) return; //叶子节点 int mid = l + r >> 1; build(u > y; if (k == 1) { if (x > y) swap(x, y); cout1; if (r > r; if (op == 'C') { cin >> d; add(l, d), modify(1, l, d); if (r < n) add(r + 1, -d), modify(1, r + 1, -d); } else cout
页:
[1]