Splay（伸展树）实现可分裂与合并的序列

对于BST，除了Treap树之外，还有一种Splay的伸展树，他能快速的分裂与合并。

重要的操作是伸展操作，将一个指定的结点 x 旋转到根的过程。

分三种情况，一次单旋，两次同向单旋，两次反向旋转。可以手动模拟一下这个过程。

到这里，问题常常是将序列的第 k 个元素旋转到根。

首先，要知道的是伸展树里面v存的是什么，是节点的编号（下标）。这样才能像 Treap实现名次树那样，很方便的找到左边第 k 个元素。

//将序列左数第k个元素选择到根

void splay(Node* &o,int k) {

    o->pushdown();

    int d = o->cmp(k);

    if(d==1) k-=o->ch[0]->s + 1;

    if(d!=-1) {

        Node* p = o->ch[d];



        p->pushdown();

        int d2 = p->cmp(k);

        int k2 = (d2==0 ? k : k - p->ch[0]->s - 1);

        if(d2!=-1) {

            splay(p->ch[d2],k2);

            if(d==d2) rotate(o,d^1);

            else rotate(o->ch[d],d);

        }

        rotate(o,d^1);

    }

}

分裂与合并：

分裂：从序列从左第 k 个元素分裂，就是将序列的 o 的第 K 小元素伸展到根，断开树根与右子节点。

合并：将left部分最大的元素旋转到根，将right作为 left的右子树。（保证right>left所有元素）。

// 合并操作。假定left所有元素小于 right

Node* merge(Node* left,Node* right) {

    splay(left,left->s);

    left->ch[1] = right;

    left->maintain();

    return left;

}



//把 o 前 k 个小结点放到left里面，其他放到ritht里面，如果不够right = null

void split(Node* o,int k,Node* &left,Node* &right) {

    splay(o,k);

    left = o;

    right = o->ch[1];

    o->ch[1] = null;

    left->maintain();

}

有时，对于序列有反转操作，这时，利用线段树的 lazy标记，标记某一段是否反转。

对于，数据结构的定义：用一个Node数组，和一个Node 的 root指针，指向这个数组的元素。

#include <bits/stdc++.h>

using namespace std;

struct Node {

    Node *ch[];

    int s;

    int flip;

    int v;

    int cmp(int k) const {

        int d = k - ch[]->s;

        if(d==) return -;     //序列第 k 个找到

        return d <= ?  : ;

    }

    void maintain() {

        s = ch[]->s + ch[]->s + ;

    }

    void pushdown() {

        if(flip) {

            flip = ;

            swap(ch[],ch[]);

            ch[]->flip = !ch[]->flip;

            ch[]->flip = !ch[]->flip;

        }

    }

};

Node *null = new Node();

// d = 0 左旋

void rotate(Node* &o,int d) {

    Node* k = o->ch[d^];

    o->ch[d^] = k->ch[d];

    k->ch[d] = o;

    o->maintain();

    k->maintain();

    o = k;

}

//将序列左数第k个元素选择到根

void splay(Node* &o,int k) {

    o->pushdown();

    int d = o->cmp(k);

    if(d==) k-=o->ch[]->s + ;

    if(d!=-) {

        Node* p = o->ch[d];

        p->pushdown();

        int d2 = p->cmp(k);

        int k2 = (d2== ? k : k - p->ch[]->s - );

        if(d2!=-) {

            splay(p->ch[d2],k2);

            if(d==d2) rotate(o,d^);

            else rotate(o->ch[d],d);

        }

        rotate(o,d^);

    }

}

// 合并操作。假定left所有元素小于 right

Node* merge(Node* left,Node* right) {

    splay(left,left->s);

    left->ch[] = right;

    left->maintain();

    return left;

}

//把 o 前 k 个小结点放到left里面，其他放到ritht里面，如果不够right = null

void split(Node* o,int k,Node* &left,Node* &right) {

    splay(o,k);

    left = o;

    right = o->ch[];

    o->ch[] = null;

    left->maintain();

}

const int maxn = 1e5+;

struct SplaySequence {

    int n;

    Node seq[maxn];

    Node *root;

    Node* build(int sz) {

        if(!sz) return null;

        Node* L = build(sz/);

        Node* o = &seq[++n];

        o->v = n;

        o->ch[] = L;

        o->ch[] = build(sz-sz/-);

        o->flip = o ->s = ;

        o->maintain();

        return o;

    }

    void init(int sz) {

        n = ;

        null->s = ;

        root = build(sz);

        for(int i = ; i < sz; i++)

            printf("%d ",seq[i].v);

        puts("");

    }

};

vector<int> ans;

void print(Node* o) {

    if(o!=null) {

        o->pushdown();

        print(o->ch[]);

        ans.push_back(o->v);

        print(o->ch[]);

    }

}

void debug(Node* o) {

    if(o!=null) {

        o->pushdown();

        debug(o->ch[]);

        printf("%d \n",o->v -);

        debug(o->ch[]);

    }

}

SplaySequence ss;

int main()

{

    int n,m;

    scanf("%d%d",&n,&m);

    ss.init(n+);

    debug(ss.root);

    for(int i = ; i < m; i++) {

        int a,b;

        scanf("%d%d",&a,&b);

        Node* left,*mid,*right,*o;

        split(ss.root,a,left,o);

        split(o,b-a+,mid,right);

        mid->flip ^=;

        ss.root = merge(merge(left,right),mid);

    }

    print(ss.root);

    for(int i = ; i < (int)ans.size(); i++)

        printf("%d\n",ans[i]-);

    return ;

}

巴特西

Uva 11922 Splay

Splay（伸展树）实现可分裂与合并的序列

最新文章

热门文章