區間樹Splay——[NOI2005]維護數列

無指針Splay超詳細講解

區間樹這玩意真TM玄學。

學這東西你必須要擁有的

1.通過【模闆】文藝平衡樹（Splay），【模闆】普通平衡樹，GSS3 - Can you answer these queries III

2.學會Splay，學會求最大子段和并知道怎麼維護資訊和下傳标記，及會有區間修的最大子段和

3.多年的程式設計技巧，以及一顆寫資料結構的良好心态

4.攢夠兩個月的肝，這很重要！

如果你不會上面東西的解決方法

1.看以下部落格Splay入門解析，文藝平衡樹Splay題解，GSS系列題解——最大子段和系列。

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<x)  //比較node是權值x的左兒子還是右兒子                

操作剖析

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<mid)build(begin,mid-1,mid);    //建左子樹
    if(mid<end)build(mid+1,end,mid);        //建右子樹
    tree[node].val=a[mid];tree[node].fa=pre;tree[node].tag=TAGNONE; //基本資訊指派
    pushup(node);           //維護資訊
    tree[pre].ch[mid>=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最大子段和

難點

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<bits/stdc++.h>
#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<x)  //比較node是權值x的左兒子還是右兒子
using namespace std;
int root,cnt,a[maxn],id[maxn],rub[maxn],top,n,m;
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];
int rublish(){              //垃圾回收
    if(top==0)return ++cnt;
    int node=rub[top--];
    return node;
}
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 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 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);       //區間最大字尾和更新
}
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;               //除去标記
    }
}
void rotate(int node){                      //rotate 模闆
    int fa=F(node);
    int gfa=F(fa);
    int z=tree[fa].ch[1]==node;
    tree[gfa].ch[tree[gfa].ch[1]==fa]=node; tree[node].fa=gfa;
    tree[fa].ch[z]=tree[node].ch[z^1];tree[tree[node].ch[z^1]].fa=fa;
    tree[node].ch[z^1]=fa;tree[fa].fa=node;
    pushup(fa); pushup(node);
}
void Splay(int node,int goal){              //Splay 模闆
    while(tree[node].fa!=goal){
        int fa=F(node);
        int gfa=F(fa);
        if(gfa!=goal)
        (compare(fa,tree[node].val))!=(compare(gfa,tree[fa].val))
        ?rotate(node) : rotate(fa);
        rotate(node);
    }
    if(!goal)root=node;
}
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<mid)build(begin,mid-1,mid);    //建左子樹
    if(mid<end)build(mid+1,end,mid);        //建右子樹
    tree[node].val=a[mid];tree[node].fa=pre;tree[node].tag=TAGNONE; //基本資訊指派
    pushup(node);           //維護資訊
    tree[pre].ch[mid>=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);
    }
}                

後記

學習時有參考I_AM_HelloWord大佬的題解。是以有的地方和他的代碼很像。

希望大家都能掌握區間樹QwQ。

謝謝觀賞

轉載于:https://www.cnblogs.com/hyfhaha/p/10729296.html