区间树Splay——[NOI2005]维护数列

阅读量：5036 次

发布时间：2019-06-12

本文共 8931 字，大约阅读时间需要 29 分钟。

无指针Splay超详细讲解

区间树这玩意真TM玄学。

学这东西你必须要拥有的

1.通过，，

2.学会Splay，学会求最大子段和并知道怎么维护信息和下传标记，及会有区间修的最大子段和

3.~~多年的编程技巧~~，以及一颗写数据结构的良好心态

4.攒够~~两个月的~~肝，这很重要！

如果你不会上面东西的解决方法

1.看以下博客，，。

2.看上面

3.别管，瞎逼的

4.好好养生，如果不够肝的话千万别写这道题

那么现在就可以开始了

既然你已经会了上面的前置技能，那么我们就可以开始分步解决这道题了。

先给出我们需要存的全部信息：

struct kkk{    int ch[2];          //左右儿子    int size;           //子树大小    int fa;             //父亲    int tag;            //赋值标记    int val;            //权值    int rev;            //翻转标记              int sum;            //区间权值和    int left;           //左区间，指区间最大前缀和    int right;          //右区间，指区间最大后缀和    int middle;         //中区间，指区间最大子段和    void clear(){ch[0]=ch[1]=fa=rev=0;tag=TAGNONE;} //清空节点信息}tree[maxn];

存的东西很多，大家务必要理解清楚每一个信息所表达的含义。

区间树Splay介绍

做过“普通平衡树”的都知道，在“普通平衡树”里，Splay是按照权值来排序的，所以能维护数的关系。那么现在到了维护区间上的操作了，也就不能按权值来排序了。

区间树，我们按照的是序列中的编号来排序。

我们可以发现，序列中的第k个点，在Splay中也是第k大的。（按编号排序嘛

所以我们想要查找序列中第k个位置，就直接找Splay中的第k大就可以了。

所以“普通平衡树”里的Splay操作，rotate操作和kth操作都是可以直接照搬的（一样的，只是维护编号而已

那么我们怎么在Splay中找到一个区间[x,y]呢？

我们可以考虑Splay的性质，将 x Splay上根，再将 y Splay上到x的右节点，那么我们得出的 y 的左子树就是我们要的[x,y]区间。

之后我们想对这个区间做什么就可以直接对那颗子树做了。

上面就是区间树的一些介绍

代码中的一些宏定义

#define TAGNONE 10000001                //没有赋值tag的标志#define L(node) (tree[node].ch[0])      //替左儿子#define R(node) (tree[node].ch[1])      //替右儿子#define F(node) (tree[node].fa)         //替父亲#define V(node) (tree[node].val)        //替权值#define S(node) (tree[node].size)       //替子树大小#define compare(node,x) (tree[node].val

操作剖析

1.基本操作 Splay,rotate,kth

这个就不用怎么说了吧，大家在做平衡树Splay都写过的啦！

2.将指定区间找出来 split操作

和上面讲的区间树一样，先找到区间[l,r]的kth，计l的kth为x，r的kth为y。

然后Splay(x,0);Splay(y,x); （直接上代码解释）

最后返回y的左儿子就是指定区间

代码：

int split(int k,int len){   //找到那个区间的位置    int x=kth(k),y=kth(k+len+1);    Splay(x,0);Splay(y,x);    return L(y);}

3.建一颗平衡的Splay，build操作

一开始我们要构造一颗有初始信息的Splay，一个一个insert显然很慢，所以我们写一个build，可以将一段序列建成一颗平衡的Splay的操作。

其实写起来和线段树差不多，注意是以编号排序来建树。

void New(int node,int x){                       //新建节点    tree[node].middle=tree[node].sum=x;         //赋值信息    tree[node].tag=TAGNONE;tree[node].rev=0;    //标记初始化    tree[node].left=tree[node].right=max(x,0);  //区间赋值    tree[node].size=1;          //大小赋值}void build(int begin,int end,int fa){           //建树    int mid=(begin+end)>>1;int node=id[mid],pre=id[fa];    if(begin==end)          //到达底部        New(node,a[begin]); //新建一个节点    if(begin
    
     =fa]=node;}

4.插入操作 insert

这里题目要求的是在x位置后插入一段长为len的序列

如果我们还是一个一个插入，仍然很慢，所以我们可以直接把插入的序列build成一颗平衡的子树，最后直接在x后插入建成的子树就可以了。

void insert(int k,int len){         //插入区间    for(int i=1;i<=len;i++)scanf("%d",&a[i]);   //输入区间    for(int i=1;i<=len;i++)        id[i]=rublish();            //从垃圾桶里找一个编号    build(1,len,0);                 //将输入的区间建成一个完全二叉树    int z=id[(1+len)>>1];    int x=kth(k+1),y=kth(k+2);      //找到要插入的位置    Splay(x,0);Splay(y,x);    tree[z].fa=y; tree[y].ch[0]=z;  //将新建的子树插入树中    pushup(y);pushup(x);            //维护信息}

5.删除操作 eraser

这个就更简单了，直接找到那个区间，然后让那个子树的父亲将左儿子清为0就可以了。

但是，为了节省空间，我们加入了一个垃圾回收的操作，就是将删除的节点重新利用起来，以节省空间

所以我们还要遍历一遍子树将那颗子树的节点扔进垃圾桶里

int rublish(){              //垃圾回收    if(top==0)return ++cnt;    int node=rub[top--];    return node;}void remove(int node){      //将一个子树清空    if(L(node))remove(L(node));     //继续清空左子树    if(R(node))remove(R(node));     //继续清空右子树    rub[++top]=node; tree[node].clear();    //清空并仍进垃圾桶，定义里有}void eraser(int x,int len){         //删除区间    int node=split(x,len),y=F(node);//找到该区间    remove(node);tree[y].ch[0]=0;   //删除该区间，子树清空    pushup(y);pushup(F(y));         //维护信息}

6.修改操作 update

一样的，先找到指定区间的子树，然后直接修改信息，打上赋值标记

void change_val(int node,int val){          //更新点值    if(!node)return ;   //空节点返回    tree[node].tag=tree[node].val=val;      //打赋值标记，更新权值    tree[node].sum=val*tree[node].size;     //更新区间权值和    tree[node].left=tree[node].right=max(tree[node].sum,0); //左右区间更新    tree[node].middle=max(tree[node].sum,val);  //最大子段和更新}void update(int x,int tot,int val){ //更新区间的指    int node=split(x,tot),y=F(node);    //找到该区间    change_val(node,val);           //更新该区间    pushup(y);pushup(F(y));         //维护信息}

7.翻转操作 reverse

一样的，先找到指定的区间的子树，然后直接翻转，打上翻转标记

void change_rev(int node){                  //更新翻转    swap(tree[node].ch[0],tree[node].ch[1]);//交换左右儿子    swap(tree[node].left,tree[node].right); //交换左右区间    tree[node].rev^=1;                      //打翻转标记}void reverse(int x,int len){            //翻转区间    int node=split(x,len),y=F(node);//找到该区间    if(tree[node].tag!=TAGNONE)return ; //如果已经有赋值标记就不用管了    change_rev(node);               //翻转该区间    pushup(y);pushup(F(y));         //维护信息}

8.求和操作 query

这就更简单了，找到指定区间的子树，然后直接输出那颗子树的sum就OK了

void query(int x,int len){  //查询区间权值和    int node=split(x,len);  //找到该区间    printf("%d\n",tree[node].sum);  //输出答案}

9.求最大子段和

直接输出root的middle最大子段和

printf("%d\n",tree[root].middle);

难点

10.维护信息和下传标记

这玩意是真毒瘤，不过主要还是难在最大子段和上面，只要我们能理解“GSS3”中的求法，其实也很简单。

维护信息，所以除了这个最大子段和之外，好像还挺简单的。最大子段和那几个更新方法这里就不讲了，不知道可以看上面的博客。

void pushup(int node){                  //维护信息    kkk &x=tree[L(node)],&y=tree[R(node)];int val=tree[node].val;   //实质是将左右儿子合并，x代替左儿子，y代替右儿子    kkk &res=tree[node];                //res代替tree[node]    res.sum=x.sum+y.sum+val; res.size=x.size+y.size+1;  //权值和更新，子树大小更新    res.middle=max(max(x.middle,y.middle),x.right+y.left+val);  //最大子段和更新    res.left=max(x.left,x.sum+y.left+val);          //区间最大前缀和更新    res.right=max(y.right,y.sum+x.right+val);       //区间最大后缀和更新}

下传标记，这本来是比较得毒瘤，我们要先更新赋值操作，左右儿子有很多信息需要更新，其中就有tag，sum，left，right和middle，更新起来十分的繁琐。但是在之前的赋值操作update中，我们引入了一个叫change_val的函数，所以这里，我们可以直接调用那个函数。于是代码就被减短了很多。

最后将tag标记为TAGNONE就OK了

然后要更新翻转操作，一样的，在之前翻转操作revrese中，我们引入了一个叫change_rev的函数，所以这里，我们还是可以直接调用。于是代码又被减了……

最后将rev标记为0就OK了。

代码：

void pushdown(int node){                //标记下传    if(tree[node].tag!=TAGNONE){        //判断有没有赋值标记        change_val(L(node),tree[node].tag); //更新左儿子        change_val(R(node),tree[node].tag); //更新右儿子        tree[node].tag=TAGNONE;         //除去标记    }    if(tree[node].rev){                 //判断有没有翻转标记        change_rev(L(node));            //更新左儿子        change_rev(R(node));            //更新右儿子        tree[node].rev=0;               //除去标记    }}

看，多简短

11.主函数

注意边界！注意边界！注意边界！主要的事情说三遍！

其他就没什么了，都是输入嘛。

总代码

#include
    
     #define TAGNONE 10000001#define maxn 1000010#define inf 100000001#define L(node) (tree[node].ch[0])      //替左儿子#define R(node) (tree[node].ch[1])      //替右儿子#define F(node) (tree[node].fa)         //替父亲#define V(node) (tree[node].val)        //替权值#define S(node) (tree[node].size)       //替子树大小#define compare(node,x) (tree[node].val
     
      >1;int node=id[mid],pre=id[fa];    if(begin==end)          //到达底部        New(node,a[begin]); //新建一个节点    if(begin
      
       =fa]=node;}int kth(int x){             //kth模板    int node=root;    while(1){        pushdown(node);        if(tree[L(node)].size>=x)node=L(node);        else        if(tree[L(node)].size+1==x)return node;        else x-=tree[L(node)].size+1,node=R(node);    }}void remove(int node){      //将一个子树清空    if(L(node))remove(L(node));     //继续清空左子树    if(R(node))remove(R(node));     //继续清空右子树    rub[++top]=node; tree[node].clear();    //清空并仍进垃圾桶}int split(int k,int len){   //找到那个区间的位置    int x=kth(k),y=kth(k+len+1);    Splay(x,0);Splay(y,x);    return L(y);}void query(int x,int len){  //查询区间权值和    int node=split(x,len);  //找到该区间    printf("%d\n",tree[node].sum);  //输出答案}void update(int x,int tot,int val){ //更新区间的指    int node=split(x,tot),y=F(node);    //找到该区间    change_val(node,val);           //更新该区间    pushup(y);pushup(F(y));         //维护信息}void rever(int x,int len){          //翻转区间    int node=split(x,len),y=F(node);//找到该区间    if(tree[node].tag!=TAGNONE)return ; //如果已经有赋值标记就不用管了    change_rev(node);               //翻转该区间    pushup(y);pushup(F(y));         //维护信息}void eraser(int x,int len){         //删除区间    int node=split(x,len),y=F(node);//找到该区间    remove(node);tree[y].ch[0]=0;   //删除该区间，子树清空    pushup(y);pushup(F(y));         //维护信息}void insert(int k,int len){         //插入区间    for(int i=1;i<=len;i++)scanf("%d",&a[i]);   //输入区间    for(int i=1;i<=len;i++)        id[i]=rublish();    build(1,len,0);                 //将输入的区间建成一个完全二叉树    int z=id[(1+len)>>1];    int x=kth(k+1),y=kth(k+2);      //找到要插入的位置    Splay(x,0);Splay(y,x);    tree[z].fa=y; tree[y].ch[0]=z;  //将新建的子树插入树中    pushup(y);pushup(x);            //维护信息}int main(){    scanf("%d%d",&n,&m);    tree[0].middle=a[1]=a[n+2]=-inf;    //边界    for(int i=1;i<=n;i++)scanf("%d",&a[i+1]);   //输入    for(int i=1;i<=n+2;i++)id[i]=i;    build(1,n+2,0);                 //建成一颗Splay    root=(n+3)>>1;cnt=n+2;          //指根，更新点数    for(int i=1;i<=m;i++){        string s; int x,len,y;          cin>>s;        if(s!="MAX-SUM")scanf("%d%d",&x,&len);        else printf("%d\n",tree[root].middle);        if(s=="INSERT")insert(x,len);        if(s=="DELETE")eraser(x,len);        if(s=="MAKE-SAME")            scanf("%d",&y),update(x,len,y);        if(s=="REVERSE")rever(x,len);        if(s=="GET-SUM")query(x,len);    }}