提高组线段树汇总

下标线段树

下标线段树即最普通的线段树，用来维护一个区间 \([L,R]\) 的信息，可以发现这其实对应了数组里面的下标，故称其为下标线段树
基本原理

对于每个节点 \([l,r]\)，左儿子是 \([l,mid]\)，右儿子是 \([mid+1,r]\)，\(mid=(l+r)/2\)（向下取整）
我们发现除了最后一层是一个满二叉树，于是我们就可以用与二叉堆类似的方法存储
对于一个编号为 \(x\) 的节点，父亲节点 \(x/2\)（x >> 1）（向下取整），左儿子 \(2x\)（x  1;    build(u  mid\) 只递归右边
剩下的情况需要递归左边和右边，这种情况最多发生一次，之后便会变成上述两种情况。因此复杂度为 \(O(2\log n)\) 忽略常数还是 \(O(\log n)\) 的

• \([L,R]\cap[T_L,T_R]= \varnothing\)，这种情况是不存在的
  

总结一下操作过程：

• 若 \([l,r]\) 完全覆盖了当前节点所覆盖的区间，则立即回溯，并且该节点的值做为一个备选答案
  
• 若左子节点与 \([l,r]\) 有重叠部分，则递归访问左子节点
  
• 若右子节点与 \([l,r]\) 有重叠部分，则递归访问右子节点
  

push down：给一个区间加上一个数，更新到两个子节点
例题

I. [JSOI2008] 最大数

因为动态添加比较麻烦，所以我们直接建 \(1\sim m\) 个空间就行了（最多 \(m\) 个操作，也就是 \(m\) 个空间），每次新增一个数的时候相当于直接修改，问后 \(L\) 个数里面最大值就是问 \([n-L+1,n]\)（\(n\) 在每次加数的时候也顺带 ++）
[code]#include using namespace std;const int N = 200005;struct Node{    int l, r; //左儿子右儿子    int v; //记录的最大值}tr[N * 4];//建树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);            cout  1;    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