算法笔记：线段树

　　这是一篇关于一些比较常用的姿势的线段树的算法笔记

线段树的基本实现

　　什么是线段树呢？请先思考这样一个问题：

　　给定一个长度为n的数组，有m次操作，每次操作有如下几种可能：

　　1、给ai加上v

　　2、给a[L,R]上的每个数加上v

　　3、求区间[L,R]上a的最大/小值

　　4、求区间[L,R]上∑(i∈[L,R])ai

　　5、查询ai的值

　　当然，这些操作都可以只用一个数组a进行模拟来完成

　　现在我们分析一下复杂度：对于操作1、5来说，每次的时间复杂度为O(1)，因为只需要修改或输出数组a[i]的值就好了，但是对于操作2、3、4来说，每次的时间复杂度为O(区间长度)

　　在这种情况下，,理论最差情况下的时间复杂度是O(mn)的

　　这样的方法显然对于十万及以上级别的数据非常棘手

　　因此我们需要一种可以处理较大数据量的数据结构

　　这时候树状数组 线段树就来了

　　既然区间问题不好处理，那么我们是否能够想到一种查找区间效率较高的算法呢？

　　仔细想一下：对于两个区间[l,m],[m+1,r],l<m<r来说，这两个区间我们可以合成为一个区间，即区间[l,r]

　　那么我们也可以说，区间[l.r]包含了区间[l,m]和[m+1,r]，同时,[l,m],[m+1,r]这两个区间内又包含了其它的区间

　　于是我们就可以将区间[1,n]进行不断的细分，最后所有区间的长度都为1

　　显然我们可以用树来表示区间之间的从属关系。

　　为了方便，我们一般采用二叉树的形式来存储区间，且区间[l,r]的2个儿子节点之间的分界线恰为[l,r]的中点

　　也就是说，我们通过树，用二分的方法，间接地将区间进行了细分

　　这就是区间树。可以证明，二叉区间树的深度为logn（本文中所有的log均为log₂）

　　那么，在这棵区间树上，如果要查询区间[l,r]的值，那么我们可以对这个区间进行细分，将其化为区间树上的一些点所代表的区间的集合

　　因为在区间树上，我们最终将整个区间都划分为了长度为1的区间，那么对于任何区间，都可以在区间树上以点的集合的形式进行表示

　　因为当我们在区间树上找到一个区间属于当前要操作的区间时，其从属的区间没有必要进行查找，那么显然在区间树上查询一个区间的值的时间复杂度是log级别的

　　因此单点操作的时间复杂度也是log级别的

　　这样的话我们就能将单点操作和区间操作的时间复杂度进行均摊，达到log级别

　　可以发现，区间树的时间复杂度是非常优秀的

　　而大部分情况下线段树就是在二叉区间树上进行操作的数据结构

　　那么我们考虑一下以上几种操作的具体事项：

　　对于单点操作来说，我们直接递归到对应的叶子结点，然后修改即可

　　对于区间修改来说，我们需要通过递归找到所有对应的区间（包括对应区间的子区间），然后进行修改

　　对于区间查询来说，只需要找到对应的区间即可

　　这样的话我们就得到了线段树的代码雏形：

struct node{
    int maxx,sum;
}tree[1000010];

void build(int pos,int l,int r){//通过递归将整棵树进行初始化
    if (l==r){
        tree[pos].maxx=a[l],tree[pos].sum=a[l];//叶子节点的值为该节点所对应的单点(叶子节点区间长度为1)的值
        return;
    }
    int m=l+r>>1;
    //初始化左右子树
    build(pos<<1,l,m);
    build(pos<<1|1,m+1,r);
    //用左右子树的值对当前节点进行初始化
    tree[pos].maxx=max(tree[pos<<1].maxx,tree[pos<<1|1].maxx);
    tree[pos].sum=tree[pos<<1].sum+tree[pos<<1|1].sum;
}

void update1(int pos,int l,int r,int p,int v){
    //pos为当前节点的位置，l和r为节点所对应的区间，p为要
    if (l==r){
        tree[pos].maxx+=v;tree[pos].sum+=v;//已找到所要修改的单点在区间树上对应的节点
        return;
    }
    int m=l+r>>1;
    //二分查找p所在的位置
    if (p<=m)    update1(pos<<1,l,m);
    else    update1(pos<<1|1,m+1,r);
    tree[pos].maxx=max(tree[pos<<1].maxx,tree[pos<<1|1].maxx);
    tree[pos].sum=tree[pos<<1].sum+tree[pos<<1|1].sum;
}

void update2(int pos,int l,int r,int L,int R,int v){
    if (l==r){//已经递归到了叶子结点
        tree[pos].maxx+=v;tree[pos].sum+=v;
        return;
    }
    if (l>R||r<L)    return;
    if (L<=l&&r<=R){//若要修改的区间包含当前节点，对当前节点进行修改
        tree[pos].maxx+=v;tree[pos].sum+=(r-l+1)*v;
    }
    int m=l+r>>1;
    update2(pos<<1,l,m,L,R,v);
    update2(pos<<1|1,m+1,r,L,R,v);
    tree[pos].maxx=max(tree[pos<<1].maxx,tree[pos<<1|1].maxx);
    tree[pos].sum=tree[pos<<1].sum+tree[pos<<1|1].sum;
}

int query_max(int pos,int l,int r,int L,int R){
    if (l>R||r<L)    return 0;
    if (L<=l&&r<=R)    return tree[pos].maxx;
    int m=l+r>>1;
    return max(query_max(pos<<1,l,m,L,R),query_max(pos<<1|1,m+1,r,L,r,v));
}

int query_sum(int pos,int l,int r,int L,int R){
    if (l>R||r<L)    return 0;
    if (L<=l&&r<=R)    return tree[pos].sum;
    int m=l+r>>1;
    return query_sum(pos<<1,l,m,L,R)+query_sum(pos<<1|1,m+1,r,L,R);
}

　　对于单点修改，我们采用递归来进行操作，但是我们可以发现，虽然max值需要在子树更新之后再进行更新，但是只要当前节点中包含要修改的节点，其sum值就一定会加上v，且只会加上v

　　那么如果只询问区间和的话，我们可以通过非递归的方式进行修改，从而对运行时间进行优化

void update(int p,int v){
    int pos=1,l=1,r=n,m;
    while (l!=r){
        tree[pos].sum+=v;
        m=l+r>>1;
        if (p<=m)    r=m;
        else    l=m+1;
    }
    tree[pos].sum+=v;
}

　　既然关于加法我们可以写一份这样的模板，那么关于其他的运算，我们同样可以写出相似的模板

懒标记

　　从上面我们已经得到了线段树的代码雏形，接下来我们来对代码进行分析：

　　　　由于要建一颗完整的数，所以建树耗费的时间确实比较大，但因为一棵树上的点最多有4n个，其复杂度仍然是O(n)

　　　　单点修改只是修改树上的一条路径，而树上的最长路径是logn的，因此其复杂度也是O(logn)

　　　　询问区间最大值与询问区间和，因为要所查找到的点很少，所以理论上复杂度也是O(logn)的

　　　　但是对于区间修改的话，我们修改的是所查找到的点的子树上的所有点

　　　　　　这就意味着，如果我们每次都对区间[1,n]进行一次修改，那么我们每次都会修改整棵树

　　　　也就是说，这种线段树的区间修改，无法达到真正意义上的均摊时间复杂度

　　　　那么我们能否对区间修改进行优化呢？

　　这时候懒标记就起了作用

　　懒标记其实就是对我们暂时用不到的点打上了一个需要更新的标记，当我们需要用到这个节点的时候，再对当前节点进行更新，并把这个标记传到其左右子树上

　　那么这样的话我们是否达到了优化区间修改的作用呢？

　　　　对于区间修改来说，我们仅将原先要修改的子树的根节点打上了懒标记，然后返回，因此其时间复杂度与区间的询问是相同的，即O(logn)

　　　　对于区间询问来说，我们只是在遍历到带有标记的节点时，才对标记进行相关的处理，而关于标记的处理的复杂度显然是O(1)的，对整体的时间复杂度不造成影响，即区间询问的时间复杂度仍然是O(logn)

　　　　建树只是增加了标记的初始化，单点操作则不需要进行初始化，其时间复杂度不变

　　这样我们就将线段树一次修改的整体复杂度降到了O(logn)

　　懒标记的关键代码如下：

void push_tag(int pos,int l,int r){
    int lc=pos<<1,rc=pos<<1|1;
    tree[lc].delta=tree[pos].delta;tree[rc].delta=tree[pos].delta;//标记下传
    tree[pos].maxx+=delta;tree[pos].sum+=(r-l+1)*delta;//对当前节点进行更新
    tree[pos].delta=0;//清除标记
}

动态开点

　　我们来考虑这样一个问题（bzoj 1067:降雨量）：http://www.lydsy.com/JudgeOnline/problem.php?id=1067

　　大意就是有n次操作，m次询问，每次操作加上一个单点（n<=10000），每次询问给出x,y，问是否同时满足以下条件

　　1、[x,y]上的所有点是否已知

　　2、(x,y)上的最大值是否小于y

　　3、x的值是否小于等于y

　　如果所有点的坐标的范围是[1,100000]，那么我们直接写一个线段树就可以把这题艹爆（虽然后面的处理特别麻烦）

　　但是现实是残酷的，点的坐标的范围是[-1e9,1e9]，那么我们怎么写这道题呢？

　　这时候就用到了 离散化 动态开点

　　因为题中的操作次数较少，而每次操作只涉及单点更新，即最多更新31个点，且树上所有点的初始值均为0，如果我们对区间[-1e9,1e9]构造一颗完整的区间树，这棵树上就会有极其多的点是我们用不到的

　　那么我们可以不对区间树进行初始化，即建一棵没有节点的树，当我们要对某个不在树上的点进行操作时，将这个点加到树上就可以了，这就是动态开点。准确来说，动态开点就是一种只维护我们需要的点的操作

　　具体的实现是这样的：我们用len来维护当前已有的点的个数，在线段树的结构体中增加lc与rc，代表当前节点的左儿子与右儿子的位置，当我们要加入一个新的节点时，将len++，那么新节点的下标就是len的位置

　　在标记永久化中，我会将动态开点与标记永久化相结合的代码给出

 

标记永久化

　　既然我们已经知道动态开点的写法了，那么当我们使用动态开点线段树的时候，或许会有一些不方便的情况

　　比如：当我们查询到一个节点时，要进行标记的下传，但是如果当前节点的子节点的个数不够2个的时候，就需要构建新的节点，这样的话难免无法达到空间的最大化利用（当然在一些树套树的应用中，也有一些懒标记的下传极难实现的情况，这里我们暂时不作讨论）

　　我们可以采用标记永久化的方法，对动态开点线段树的空间利用进一步进行优化

　　什么是标记永久化呢？

　　顾名思义，就是当我们在线段树上的某个节点打上标记之后，无论是否查询到这个节点，都不将标记下传

　　这样我们就不必因为多开节点而浪费多余的空间了，但是我们怎么维护树上的值呢？

　　我们用sum来记录当前节点所代表的区间的和，lc与rc代表左右子节点，l与r代表那么显然sum=lc.sum+rc.sum+(r-l+1)*(由根节点到当前节点的路径上的标记和)，但是显然这样写的话时间效率是较低的

　　但是我们可以基于上面的思路进行一下优化

　　当我们要查找一个节点的时候，我们在遍历的同时，记录一下遍历时经过的节点上的标记的和，那么就可以直接计算出这段区间的和了

　　因此sum只需要记录左右子节点的sum以及当前节点的标记*(r-l+1)就行了

　　维护区间最大值和维护区间和的操作基本上是类似的，下面给出动态开点以及标记永久化的模板

struct node{
    node *lc,*rc;
    int maxx,sum,delta;
    node(){//初始化节点
        lc=rc=NULL;
        maxx=sum=delta=0;
    }
    inline void update(int l,int r){//重新计算sum值和maxx值
        sum=0;maxx=0x80000000;
        if (lc!=NULL){
            sum+=lc->sum;
            maxx=max(maxx,lc->maxx);
        }
        else maxx=0;
        if (rc!=NULL){
            sum+=rc->sum;
            maxx=max(maxx,rc->maxx);
        }
        else maxx=max(maxx,0);
        maxx+=delta;
        sum+=delta*(r-l+1);
    }
};
node *root=NULL;

void add(node* &pos,int l,int r,int L,int R,int v){//区间加
    if (r<L||l>R)    return;
    if (!pos)    pos=new node();
    if (L<=l&&r<=R){//当前节点所代表的区间在要修改的区间内
        pos->delta+=v;//标记加上v
        pos->sum+=v*(r-l+1);
        pos->maxx+=v;
        return;
    }
    int m=l+r>>1;
    add(pos->lc,l,m,L,R,v);
    add(pos->rc,m+1,r,L,R,v);
    pos->update(l,r);
}

int query_sum(node *pos,int l,int r,int L,int R,int v=0){//求区间和，v代表路径上的标记和
    if (r<L||l>R)    return 0;
    if (pos==NULL){//当前区间未修改过，直接返回路径标记和与区间长度的积
        if (r>R)    return (R-l+1)*v;
        else if (L<=l&&r<=R)    return (r-l+1)*v;
        else     return (r-L+1)*v;
    }
    if (L<=l&&r<=R)    return pos->sum+(r-l+1)*v;//当前节点的区间和为sum+区间长度*路径上标记和
    int m=l+r>>1;
    return query_sum(pos->lc,l,m,L,R,v+pos->delta)+query_sum(pos->rc,m+1,r,L,R,v+pos->delta);
}

int query_max(node *pos,int l,int r,int L,int R,int v=0){//求区间最大值
    if (r<L||l>R)    return 0;
    if (pos==NULL)    return v;//当前区间未修改过，直接返回路径标记和
    if (L<=l&&r<=R)    return pos->maxx+v;
    int m=l+r>>1;
    return max(query_max(pos->lc,l,m,L,R,v+pos->delta),query_max(pos->rc,m+1,r,L,R,v+pos->delta));
}

可持久化线段树及其标记永久化

　　可持久化线段树的基本结构和主席树是类似的，其实大部分的可持久化数据结构都可以看做是主席树，这里我们为了区分应用，将主席树分为两个部分，这里介绍的是主席树在求历史最值时的作用。

　　给定一个长度为n的数组，有m次操作，每次操作有如下几种可能：

　　1、给ai加上v

　　2、给a[L,R]上的每个数加上v

　　3、求第p次修改后区间[L,R]上a的最大/小值

　　4、求第p次修改后区间[L,R]上∑(i∈[L,R])ai

　　当然可以离线一下，然后用普通的线段树写，但是如果加上一个强制在线的条件呢？

　　想一下暴力的写法：

　　　　对于每一次修改，我们都建一棵新的线段树，然后关于某个线段树作查询

　　　　但是这样的空间耗费与时间耗费都是极大的，甚至不如用二维数组模拟

　　　　想想如何对这个算法进行略微的优化：

　　　　考虑一下线段树的性质：在每次的查询中，我们访问到的节点的个数是logn级别的，也就是说，我们在一次修改中，实际上只修改了logn个节点。这样的话就说明如果我们建一棵新的线段树的话，就浪费了非常多的空间

　　　　我们就用动态开点的形式建这棵新的树，但是如果我们要查询的节点不是我们这次修改的地方呢？

　　　　这个节点一定在之前的某棵线段树上，同时我们也不必耗费额外的时间去查找这个节点的具体位置，请仔细看下面的分析：

　　　　　　每次更新时，我们用两个指针来进行遍历，这两个指针指向同一个区间，但是前一个指针指向上一次修改的线段树，后一个则指向这次修改时新建的线段树，我们将前一个指针的左儿子与右儿子对后一个指针的左儿子与右儿子进行初始化，然后将两个指针都移到左儿子和右儿子上进行更新，如果后一个指针指向的节点所代表的区间部分包含当前要修改的区间，则将这个指针指向一个新的节点

　　　　这样我们就完成了一颗新的树的建立，可以证明，可持久化线段树的时间和空间复杂度都是logn级别的

　　在可持久化线段树上，涉及区间修改的操作基本都是用懒标记来实现的，但是如果下传的话，不免会遇到要新建节点的情况，这时候怎么办？

　　标记永久化！

　　没错，既然懒标记可以运用在可持久化线段树上，那么标记永久化也可以运用在可持久化线段树上，我们在建某棵线段树时，把上一棵树相同位置的节点的标记复制到这一棵树上就好了

　　代码大致如下（只给出了2种情况的模板（不就是懒吗））

struct node{
    node *lc,*rc;
    int maxx;
};
node *root[100010];
void build(node* &p,int l,int r){
    p=new node;
    if (l==r){
        p->maxx=a[l];
        p->lc=NULL;p->rc=NULL;
        return;
    }
    int m=l+r>>1;
    build(p->lc,l,m);
    build(p->rc,m+1,r);
    p->maxx=max(p->lc->maxx,p->rc->maxx);
}

void update(node* &x,node* &y,int l,int r,int p,int v){
    y->=new node;
    y->lc=x->lc,y->rc=x->rc;
    if (l==r){
        y->maxx=v+x->maxx;
        return;
    }
    int m=l+r>>1;
    if (p<=m)    update(x->lc,y->lc,l,m,p,v);
    else update(x->rc,y->rc,m+1,r,p,v);
    y->maxx=max(y->lc->maxx,y->rc->maxx);
}

int query(node *pos,int l,int r,int L,int R){
    if (l>R||r<L)    return 0;
    if (L<=l&&r<=R)    return pos->maxx;
    int m=l+r>>1;
    return max(query(pos->lc,l,m,L,R),query(pos->rc,m+1,r,L,R));
}

struct node{
    node *lc,*rc;
    int sum,delta,l,r;
    inline void getsum(){
        sum=0;
        if (lc!=NULL)    sum+=lc->sum+lc->delta*(lc->r-lc->l+1);
        if (rc!=NULL)    sum+=rc->sum+rc->delta*(rc->r-rc->l+1);
    }
    node(int l,int r):l(l),r(r){
        delta=0;
    }
}

void build(node* &pos,int l,int r){
    pos=new node(l,r);
    if (l==r){
        pos->lc=pos->rc=NULL;
        pos->sum=a[l];
        return;
    }
    m=l+r>>1;
    build(pos->lc,l,m);
    build(pos->rc,m+1,r);
    sum=lc->sum+rc->sum;
}

void update(node *x,node* &y,int l,int r,int L,int R,int v){
    if (l>R||r<L)    return;
    y=new node(l,r);
    y->delta=x->delta;
    y->lc=x->lc;
    y->rc=x->rc;
    if (L<=l&&r<=R){
        y->delta+=v;
        return;
    }
    int m=l+r>>1;
    update(x->lc,y->lc,l,m,L,R,v);
    update(x->rc,y->rc,m+1,r,L,R,v);
    y->getsum();
}

int query(node *pos,int l,int r,int L,int R,int v=0){
    if (l>R||r<L)    return 0;
    if (L<=l&&r<=R)    return pos->sum+(pos->v+v)*(r-l+1);
    int m=l+r>>1;
    return query(pos->lc,l,m,L,R,v+pos->v)+query(pos->rc,m+1,r,L,R,v+pos->v);
}

权值线段树

　　普通的线段树是一个解决区间最值的优秀数据结构，但是如果要求整体的第k大值就无能为力了 当然是选择平衡树啦 

　　但是我们将线段树稍微转换一下，用区间和来表示这个区间所表示的数的出现的个数的总和，就可以求整体第k大了，这就是权值线段树

　　关于具体的查找，我们设要查找的是第k大，如果当前节点的左子树的sum大于等于k，那么第k大数一定在左子树中，否则我们将k减去左子树的sum值，然后在右子树中查找即可。在平衡树的查找第k大的过程中，我们也用到了类似的方法

　　下面给出权值线段树的代码（因为要讲主席树，所以就没有写单点添加的权值线段树（其实就是懒得敲一遍模板））

void update(int p){//使用非递归的方法以减小常数
    int l=1,r=d,m,pos=1;
    while (r-l){
        v[pos]++;
        m=l+r>>1;
        if (p<=m){
            r=m;
            pos=pos<<1;
        }
        else{
            l=m+1;
            pos=pos<<1|1;
        }
    }
    v[pos]++;
}

void prepare(){
    //排序并离散数组
    sort(hash+1,hash+1+n);
    d=unique(hash+1,hash+1+n)-hash-1;
    for (int i=1;i<=n;i++){
        int p=lower_bound(hash+1,hash+1+n,a[i])-hash;//按照a在hash中的下标构建权值线段树
        update(p);
    }
}

int query(int pos,int l,int r,int k){
    if (l==r)    return l;
    int val=v[pos<<1],m=l+r>>1;
    if (k<=val)    return query(pos<<1,l,m,k);
    else return query(pos<<1|1,m+1,r,k-val);
}

主席树

　　权值线段树可以求整体的第k大，但是不能求区间第k大

　　但是权值线段树之间是可以求和的，那么我们可以采用树状数组套权值线段树的方式，来求区间上的第k大

　　但是我们分析一下时空复杂度：每次的单点修改操作，我们需要访问logn棵线段树上的logn个节点，因此时间上每次修改的复杂度是logn的，而开n棵动态开点线段树的最大空间耗费为O(n²)的，所以当n过大的时候，显然是不可行的

　　这时候我们需要主席树。

　　主席树其实就是一种可持久化的权值线段树，我们可以将数组看做n次修改操作，每次在数组的末尾加入一个数字，这样的话我们可以建一棵空的线段树，然后进行可持久化操作就行了

　　主席树的复杂度和可持久化线段树的复杂度一致，都是O(nlogn)，但是这样的话显然是不支持修改操作的，具体代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define MAXX 100010
int n,m,l[MAXX<<5],r[MAXX<<5],root[MAXX],len=0,a[MAXX],hash[MAXX],sum[MAXX];
//root[i]表示前缀[i]的线段树的根节点，hash是离散化后的a数组，sum计数
int read(){
    int x=0,y=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-')y=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*y;
}

void init(){
    n=read();m=read();
    for (int i=1;i<=n;i++){
        a[i]=read();hash[i]=a[i];
    }
}

int build(int L,int R){//构建一棵空树
    int rt=++len;
    sum[rt]=0;
    if (L<R){
        int m=(L+R)>>1;
        l[rt]=build(L,m);
        r[rt]=build(m+1,R);
    }
    return rt;
}

int update(int pre,int L,int R,int x){//不断查找x所在的区间，仅对包含x的区间新建节点，因此每次只建logn个节点
    int rt=++len;
    l[rt]=l[pre],r[rt]=r[pre],sum[rt]=sum[pre]+1;//左右节点中一定有一个是从树i-1的节点rt继承而来的
    if (L<R){
        int m=(L+R)>>1;
        if (x<=m)    l[rt]=update(l[pre],L,m,x);//类似二叉查找树的查找操作
        else r[rt]=update(r[pre],m+1,R,x);
    }
    return rt;
}

int query(int u,int v,int L,int R,int k){//根据两个相同位置的节点不断做差来求出区间内[l,r]的数的个数，从而求出第k小
    if (L>=R)    return L;
    int m=(L+R)>>1;
    int num=sum[l[v]]-sum[l[u]];
    if (num>=k)    return query(l[u],l[v],L,m,k);//操作类似treap中求第k大的操作
    else return query(r[u],r[v],m+1,R,k-num);
}

int main(){
    init();
    //第一步：排序并去重
    sort(hash+1,hash+1+n);
    int d=unique(hash+1,hash+1+n)-hash-1;
    //第二步：建一颗空的完整的线段树(即前缀[0]所对应的线段树)
    root[0]=build(1,d);
    //第三步：关于所有的前缀建线段树，对于前缀[i]来说，其只有logn个节点与前缀i-1对应的线段树不同，所以剩下的节点直接继承前缀i-1对应的线段树即可
    for (int i=1;i<=n;i++){
        int x=lower_bound(hash+1,hash+1+d,a[i])-hash;//获取a[i]在hash中的下标
        root[i]=update(root[i-1],1,d,x);
    }
    while (m--){
        int L,R,k;
        L=read();R=read();k=read();
        printf("%d
",hash[query(root[L-1],root[R],1,d,k)]);
    }
    return 0;
}