首页 > 其他 > 详细

Splay 区间操作(二)

时间:2018-07-15 00:41:56      阅读:218      评论:0      收藏:0      [点我收藏+]

首先基本操作如下:

删除第rank个点

void Remove(int id){//删除第rank个点
    rank++;
    int x = find(root, rank - 1);
    splay(x, 0);
    x = find(root, rank + 1);
    splay(x, root);
    ch[ch[root][1]][0] = 0;
    pushup(ch[root][1]),pushup(root);
    }

删除编号为id的点

void Remove(int id){//删除编号为id的点
    splay(id, 0);
    int rank = size[ch[root][0]] + 1;
    int x = find(root, rank - 1);
    splay(x, 0);
    x = find(root, rank + 1);//printf("root=%d\n", root);
    splay(x, root);
    ch[ch[root][1]][0] = 0;
    pushup(ch[root][1]),pushup(root);
    }

插入变成第rank个点

void insert(int rank,int v){//插入变成第rank个点
    int x = find(root, rank);
    splay(x, 0);//printf("size=%d\n",size[ch[root][0]]);
    x = find(root, rank + 1);
    splay(x, root);
    ch[ch[root][1]][0] = New(ch[root][1], v);
    pushup(ch[root][1]),pushup(root);
    }

区间翻转在上一篇博客有了。值得注意的是:\(Splay\)常数较大,有时一个操作需要多个基本操作一起并用,大大降低效率。所以在条件允许的情况下,我们尽量减少\(Splay\)的次数,达到相同的结果,详细会在以后的若干篇博客提及

Splay 区间操作(二)

原文:https://www.cnblogs.com/Tony-Double-Sky/p/9311408.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!