学习心得 - 数据结构 - 线段树

· · 算法·理论

此文为复习专用

我去我还写过这么唐的东西。

定义

线段树是一种可以处理区间问题的数据结构。它通过以树结构映射数组，达到一种把区间问题转化成树上问题目的的数据结构。我们常用的是递归二叉式的线段树。具体的，我们可以把 [1,10] 这个区间作为一个端点 \color{blue}1，这个时候 \color{blue}2 是它的左子树，记录的范围为 [1,5]，而 \color{blue}1 的右子树记录的是 \color{blue}3\color{black}[6,10]。以此类推，直到只剩下单个的节点，如 [1,1]，[2,2] 之类的，我这里画个图：

[1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ,\ \ \ \ \ \ \ \ \ \ \ \ \ \ 10] \\ [1 \ \ \ \ \ \ \ \ \ \ \ \ \ ,5][6,\ \ \ \ \ \ \ \ \ \ 10] \\ [1,\ \ \ 3][4,\ 5][6,\ \ \ 8][9,\ 10] \\ [1,2][3][4][5][6,7][8][9][10]

PS：最底下的 [1,2]，[6,7] 还要有一层 [1][2][6][7]。

懒标记

当修改包含区间修改，暴力单点修改的效率也就不行了。这个时候我们可以使用懒标记。懒标记用于处理当操作覆盖整个节点时，我们可以先不下传操作，而是暂时存储在节点位置，等到需要的时候再下传。

动态开点

就是把左右子树改成动态开点，用于处理修改范围极大的情况，如权值线段树。

标记永久化

既然有懒标记，那么我们是否存在一种不下传标记的写法呢？这就是标记永久化。我们发现每一个操作管辖的都是它的子树，那么我们可以做到一路修改需要修改的节点，再记录一下路上的标记即可。这个东西看起来很没用，但是这个东西可以优化掉 pushup 的算法复杂度（一般子树合并需要使用），还可能是可持久化线段树要区间修改，可是蒟蒻太弱了没见过 qwq。

可持久化

见学习心得 - 可持久化。

李超线段树

也是线段树，但是维护线段问题。具体看例题。这个线段树能动态插入线段或直线，然后维护区间凸包的极值。这个东西可以用于斜率优化 dp。具体的，我们可以在加入直线的时候自动转化成直线解析式 y=kx+b，然后按照斜率的各种性质维护，具体实现短，但是复杂。

void maketag(int p,int l,int r,int upv){
    int mid=(l+r)>>1;
    int eq=equ(f(upv,mid),f(val[p],mid));
    if(eq==1||(eq==0&&upv<val[p]))
        swap(val[p],upv);
    int leq,riq;
    leq=equ(f(upv,l),f(val[p],l));
    riq=equ(f(upv,r),f(val[p],r));
    if(leq==1||(leq==0&&upv<val[p]))
        maketag(p<<1,l,mid,upv);
    if(riq==1||(riq==0&&upv<val[p]))
        maketag(p<<1|1,mid+1,r,upv);
    return;
}