Battle of the Brains
强大到无与伦比的数据结构splay-tree
上篇文章~研究了一下sbt(size balance tree)后,三鲜师傅评论说splay-tree功能更强大,并且有很多其他数据结构无法实现的功能
于是赶紧去学习,看了这题后发现sbt几乎完成不了其中的任何一个操作,而线段树也无法完成插入.删除.翻转的操作,但是splay却能很完美的解决
其他平衡二叉树是根据权值来限制树的结构的,没有splay这么灵活.splay的任意旋转可以对一整个区间进行操作,并且可以任意增加区间,任意删除区间,都是logn的复杂度.并且可以沿用线段树的延迟标记,每次不用急着传递给子树,遍历到时候传下去即可,然后更新上来(我写了push_down和push_up两个函数,其实线段树也是这个套路,不过我以前写线段树的时候直接把这两个函数写进update和query里的,现在回去看以前线段树的代码感觉很乱,没有单独写出来优美~)
献上Crash撞神大牛的论文,里边就是将splay对一个区间的具体操作
一些其他二叉平衡树叶能完成的操作在这篇和楼教主同个时代的美女神牛杨思雨的论文里有介绍
介绍一些练习splay的题目:
【splay入门】用其他平衡二叉树能解决:(理论复杂度没有sbt好,但我用splay却比写sbt还快=.=)
[HNOI2002]营业额统计
[NOI2004]郁闷的出纳员
[HNOI2004]宠物收养所
【splay热身】其他平衡二叉树不能解决,但是线段树和splay能解决(效率是线段树的1~5倍.)
I Hate It(更新节点,区间最值)
A Simple Problem with Integers(成段更新,区间求和)
Memory Control(较为复杂的区间操作)
更多热身题可以去这里找
【splay进阶】其他平衡二叉树和线段树都无法解决:
Robotic Sort
比较有意思的题目,结点处没有任何权值,只要记录每个数字对应的结点位子,然后从小到打把相对应的位子旋转到根节点,输出i+左子树的个数,接着给左子树一个翻转的延迟标记,最后删除该节点.注意把结点旋到根部的时候要先从根部把延迟标记push_down下去.
Queue-jumpers
可以用各种数据结构解决的题,用splay的话和上题差不多,记录结点的位子..Top的操作有点麻烦,记得每次操作后都要把结点splay到根部,不然会超时=.=
Play with Chain
此题有splay的最独特的操作 区间旋转和切割
[AHOI2006]文本编辑器editor(较为简单的插入删除旋转,小数据版)
[AHOI2006]文本编辑器editor(较为简单的插入删除旋转,大数据版)
这题很恶心,最后一个是结束符号也会让你输出来,我纠结了很久很久
[NOI2005]维修数列(在插入删除基础上增加区间统计,较难)
区间统计如果做了上边三个热身题的话应该没问题了
旋转和区间统计的时候要特别注意,两者结合产生的trick留给大家自己去发现,这个trick整了我一个下午
50M的数据量,用静态的数组开不下,动态的太浪费时间,怎么办呢?自己手动压个内存池吧
总结.splay的区间操作看上去很复杂,其实就是函数多,略数一下有以下几个
void Rotate(int x,int f)
void Splay(int x,int goal)
void RotateTo(int k,int goal)
void NewNode(int &x,int c)
void push_down(int x)
void push_up(int x)
void makeTree(int &x,int l,int r,int f)
void init(int n)
这几个函数是必不可少的,并且还要再根据题目意思加一些函数
但是真正理解了之后会发现…写了最上边的三个函数后 其实剩下的就和线段树差不多,这样看来编程复杂度也不是很大,手抽筋一下花个5分钟敲下这几个函数也就OK了
所以splay的题完全可以套上线段树的马甲再加上线段树无法完成的操作变成更难的题目XD
好了,献上模板:(包括了回收内存,虽然模板上这题不需要用这个操作)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 | /* http://acm.pku.edu.cn/JudgeOnline/problem?id=3468 区间跟新,区间求和 */ #include <cstdio> #define keyTree (ch[ ch[root][1] ][0]) const int maxn = 222222; struct SplayTree{ int sz[maxn]; int ch[maxn][2]; int pre[maxn]; int root , top1 , top2; int ss[maxn] , que[maxn]; inline void Rotate(int x,int f) { int y = pre[x]; push_down(y); push_down(x); ch[y][!f] = ch[x][f]; pre[ ch[x][f] ] = y; pre[x] = pre[y]; if(pre[x]) ch[ pre[y] ][ ch[pre[y]][1] == y ] = x; ch[x][f] = y; pre[y] = x; push_up(y); } inline void Splay(int x,int goal) { push_down(x); while(pre[x] != goal) { if(pre[pre[x]] == goal) { Rotate(x , ch[pre[x]][0] == x); } else { int y = pre[x] , z = pre[y]; int f = (ch[z][0] == y); if(ch[y][f] == x) { Rotate(x , !f) , Rotate(x , f); } else { Rotate(y , f) , Rotate(x , f); } } } push_up(x); if(goal == 0) root = x; } inline void RotateTo(int k,int goal) {//把第k位的数转到goal下边 int x = root; push_down(x); while(sz[ ch[x][0] ] != k) { if(k < sz[ ch[x][0] ]) { x = ch[x][0]; } else { k -= (sz[ ch[x][0] ] + 1); x = ch[x][1]; } push_down(x); } Splay(x,goal); } inline void erase(int x) {//把以x为祖先结点删掉放进内存池,回收内存 int father = pre[x]; int head = 0 , tail = 0; for (que[tail++] = x ; head < tail ; head ++) { ss[top2 ++] = que[head]; if(ch[ que[head] ][0]) que[tail++] = ch[ que[head] ][0]; if(ch[ que[head] ][1]) que[tail++] = ch[ que[head] ][1]; } ch[ father ][ ch[father][1] == x ] = 0; pushup(father); } //以上一般不修改////////////////////////////////////////////////////////////////////////////// void debug() {printf("%d\n",root);Treaval(root);} void Treaval(int x) { if(x) { Treaval(ch[x][0]); printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,val = %2d\n",x,ch[x][0],ch[x][1],pre[x],sz[x],val[x]); Treaval(ch[x][1]); } } //以上Debug //以下是题目的特定函数: inline void NewNode(int &x,int c) { if (top2) x = ss[--top2];//用栈手动压的内存池 else x = ++top1; ch[x][0] = ch[x][1] = pre[x] = 0; sz[x] = 1; val[x] = sum[x] = c;/*这是题目特定函数*/ add[x] = 0; } //把延迟标记推到孩子 inline void push_down(int x) {/*这是题目特定函数*/ if(add[x]) { val[x] += add[x]; add[ ch[x][0] ] += add[x]; add[ ch[x][1] ] += add[x]; sum[ ch[x][0] ] += (long long)sz[ ch[x][0] ] * add[x]; sum[ ch[x][1] ] += (long long)sz[ ch[x][1] ] * add[x]; add[x] = 0; } } //把孩子状态更新上来 inline void push_up(int x) { sz[x] = 1 + sz[ ch[x][0] ] + sz[ ch[x][1] ]; /*这是题目特定函数*/ sum[x] = add[x] + val[x] + sum[ ch[x][0] ] + sum[ ch[x][1] ]; } /*初始化*/ inline void makeTree(int &x,int l,int r,int f) { if(l > r) return ; int m = (l + r)>>1; NewNode(x , num[m]); /*num[m]权值改成题目所需的*/ makeTree(ch[x][0] , l , m - 1 , x); makeTree(ch[x][1] , m + 1 , r , x); pre[x] = f; push_up(x); } inline void init(int n) {/*这是题目特定函数*/ ch[0][0] = ch[0][1] = pre[0] = sz[0] = 0; add[0] = sum[0] = 0; root = top1 = 0; //为了方便处理边界,加两个边界顶点 NewNode(root , -1); NewNode(ch[root][1] , -1); pre[top1] = root; sz[root] = 2; for (int i = 0 ; i < n ; i ++) scanf("%d",&num[i]); makeTree(keyTree , 0 , n-1 , ch[root][1]); push_up(ch[root][1]); push_up(root); } /*更新*/ inline void update( ) {/*这是题目特定函数*/ int l , r , c; scanf("%d%d%d",&l,&r,&c); RotateTo(l-1,0); RotateTo(r+1,root); add[ keyTree ] += c; sum[ keyTree ] += (long long)c * sz[ keyTree ]; } /*询问*/ inline void query() {/*这是题目特定函数*/ int l , r; scanf("%d%d",&l,&r); RotateTo(l-1 , 0); RotateTo(r+1 , root); printf("%lld\n",sum[keyTree]); } /*这是题目特定变量*/ int num[maxn]; int val[maxn]; int add[maxn]; long long sum[maxn]; }spt; int main() { int n , m; scanf("%d%d",&n,&m); spt.init(n); while(m --) { char op[2]; scanf("%s",op); if(op[0] == 'Q') { spt.query(); } else { spt.update(); } } return 0; } |
Popularity: 42% [?]
[...] [...]
[...] 伸展树： http://hi.baidu.com/zhanggmcn/blog/item/2ef6a69b0b24e4b6c9eaf481.html http://www.notonlysuccess.com/index.php/splay-tree/ [...]
[...] [...]
在erase()删除子树之后要改变父亲的ch值，并且pushup(父亲)
在pushup()里面add[x]要*size[x]
[回复]
shǎ崽 回复:
十二月 9th, 2011 at 13:40
erase() 确实是个bug,谢谢提醒
我已经忘记模板上指的是哪一题了…反正pushup()都要重写的
[回复]
Orthocenter 回复:
十二月 9th, 2011 at 13:56
嗯 。
你的模板很简洁。
这几天根据你的推荐，大部分题目都写下来了，刚刚搞定了维护数列那题。
谢谢神牛的文章！
[回复]
shǎ崽 回复:
十二月 9th, 2011 at 14:35
更谢谢你对我模板提出来的建议:)
[回复]
我想问一下，初始化的时候建好的树就是一棵二叉查找树了吗？为什么呢？谢谢！
[回复]
shǎ崽 回复:
十二月 8th, 2011 at 22:26
这模板不是二叉查找树,是区间更新树.可以做一些区间操作,没有二叉查找树的功能
[回复]
beyondxgb 回复:
十二月 9th, 2011 at 19:36
谢谢！我脑残了，我一直以为无论怎么旋转，都要保持这棵树是二叉查找树。。。
[回复]
shǎ崽 回复:
十二月 10th, 2011 at 10:16
[回复]
话说有人把这篇做成word，发到百度文库呢= =
Splay真的不好搞。。。先膜拜一下
Pira´s last blog ..hdu 3335 Divisibility(Dancing Links重复覆盖)
[回复]
希望多多指点
Chowsh´s last blog ..爱粮说
[回复]
大牛我只想知道你robotic sort那题也是这样写的吗? 我一直TLE ,直到我分开写了zig zag zigzig zigzag…
[回复]
请问hdu1890为什么要先从根部把延迟传递下去？
chonglinsun´s last blog ..使用快速傅里叶变换计算大整数乘法
[回复]
弱弱问一句，push_up()函数一般对于什么操作用啊，我到现在还没有遇到要用到push_up()，把孩子信息更新上来的题，可以说一下吗？比如什么操作需要这个？
[回复]
弱弱的问下，区间翻转的标记rev具体是怎么进行维护的？
[回复]
shǎ崽 回复:
十二月 2nd, 2010 at 13:25
有rev标记的话左右儿子交换下位子然后标记rev
[回复]
tracyzhu 回复:
十二月 7th, 2010 at 11:52
您在Rotate里面有push_down的操作 那y的左右儿子位置变换了之后 左旋不是变成了右旋了吗
[回复]
shǎ崽 回复:
十二月 7th, 2010 at 11:54
不会啊,不要主观臆测.你可以手动模拟一下看看
[回复]
tracyzhu 回复:
十二月 7th, 2010 at 12:02
。。发现了，囧 不好意思脑残了
[回复]
shǎ崽 回复:
十二月 7th, 2010 at 12:02
[回复]
学长 您好 请问你觉得数组的spaly实现是不是比指针的splay实现慢啊 我交了一道题目指针的快一倍 然后请问写数组的会不会被卡常数啊？ 谢谢
[回复]
下阶段学习splay,习题收藏了
[回复]
shǎ崽 回复:
八月 18th, 2010 at 12:33
呵呵~splay是个神奇的东西~
[回复]
首先膜拜下Orz
果然强大！NOI2005那题学会了回收内存，呵呵。
不过第一题 HNOI营业额统计 我的始终wa – -! discuss有人说数据有问题，不知是不是？
[回复]
shǎ崽 回复:
八月 14th, 2010 at 11:49
恩，是的，输入只有n-1个数字
当你读不到第n个数字的时候，直接设置为0好了
if(scanf(“%d”,&val) == EOF) val = 0;
[回复]
orz 总是无私奉献学习成果的hh
[回复]
shǎ崽 回复:
八月 13th, 2010 at 13:18
ACM的起跑线是不公平的,大家还私藏的话怎么能追上那些牛人呢?
[回复]
[...] 比较简单的斜率. BST 解决不单调的DP问题=.=(为了这题,我特地去学了sbt和splay) 【noi2007试题】货币兑换 O(n*logn) [...]
[AHOI2006]文本编辑器editor
这题有什么trick么？死活过不了…
“这题很恶心,最后一个是结束符号也会让你输出来,我纠结了很久很久”什么意思？能够再明白一点么?…
[回复]
notonlysuccess 回复:
七月 31st, 2010 at 21:03
就是最后一个字母是ascii码的0
其实这题数据真的很邪恶，直接做下边那道 [NOI2005]维修数列 好了
[回复]
daizhenyang 回复:
八月 1st, 2010 at 13:04
这题数据有问题 delete会越界
[回复]
呵呵 看过杨思雨的论文 之后 就直接看您的代码开始学习splay了
[回复]
shǎ崽 回复:
七月 31st, 2010 at 19:09
另外一篇论文更重要
看完杨思雨的论文后看我的可能会一头雾水
[回复]
abilitytao 回复:
七月 31st, 2010 at 22:27
恩恩 按照您的指示 我看完了那篇论文 但是还是不太明白 怎么进行区间操作 因为一个节点进行splay操作之后 位置就改变了 怎么进行区间的维护。。。
[回复]
戴牛威武！
[回复]
您的模板有问题
应该改成
inline void RotateTo(int k,int goal) {//??k?????goal??
int x = root;
push_down(x);
while(sz[ ch[x][0] ]!= k) {
//printf(“%d — %d\n”,sz[ ch[x][0] ],k);
//system(“pause”);
if(k <sz[ ch[x][0] ]) {
x = ch[x][0];
} else {
k -= (sz[ ch[x][0] ] + 1);
x = ch[x][1];
}
push_down(x);
}
Splay(x,goal);
}
[回复]
shǎ崽 回复:
七月 31st, 2010 at 18:26
是的是的~需要区间旋转的时候就会出现左右个数改变的情况~
所以应该先push_down才判断
[回复]
我说直接插入 Splay 节点怎么一直杯具。。原来是一开始就构造出一个完全平衡的二叉树……
[回复]
beyondxgb 回复:
十二月 8th, 2011 at 22:55
为什么一开始构造的树就是一棵二叉排序树，能解释一下吗，谢谢！
[回复]
YM, 受教了。
[回复]
shǎ崽 回复:
七月 20th, 2010 at 09:17
回拜32
[回复]
还有一个文本编辑器是ＮＯＩ２００３的，
地址是：http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1507
但是这个没有翻转操作．
＂发现sbt几乎完成不了其中的任何一个操作＂这句话有点问题吧．．．
其实除了翻转以外，ＳＢＴ都是可以做的．
只是插入时要构建一棵完全平衡的小二叉树，再接到大树上适合的位置．
否则容易严重超时= =．
edward_mj´s last blog ..HDOJ3425 Coverage【求圆与线段覆盖部分的一个沙茶方法。。。】
[回复]
shǎ崽 回复:
七月 20th, 2010 at 09:09
啊,链接链错了,其实我想说的是维护序列那题…不好意思
[回复]
看不了那篇文章啊。
[回复]
shǎ崽 回复:
七月 8th, 2010 at 18:54
哎呀,有几个链接出错了~~马上修改
[回复]
shǎ崽 回复:
七月 8th, 2010 at 18:58
还有,那个OJ挂了….好多题目看不到了..我正在想办法
[回复]
Lvsi 回复:
一月 10th, 2012 at 21:18
sha崽那些题OI的题在衡阳市八中的OJ上都有的..http://www.zybbs.org/JudgeOnline/
[回复]
Orz!!
最近在sha崽的blog学了很多东西~强势膜拜O(∩_∩)O
[回复]
shǎ崽 回复:
七月 8th, 2010 at 18:57
啊,暑假开始啦,我去年学的太少,今年补上
[回复]
AekdyCoin 回复:
七月 8th, 2010 at 22:05
太假了= =
[回复]
daizhenyang 回复:
七月 18th, 2010 at 16:50
太假了
[回复]
你这效率真高..
看你这架势以后是准备当ACM家教吗?
[回复]
shǎ崽 回复:
七月 8th, 2010 at 12:29
=.=三鲜师傅见笑了.
只是把这个算法备注一下,以后忘了可以快速回忆起来,顺便赚点人气
[回复]
Orz!!!
[回复]
shǎ崽 回复:
七月 8th, 2010 at 10:41
AC神犇怎么这么快就出现了~?
你出的防秒题有么有这个啊?
[回复]
AekdyCoin 回复:
七月 8th, 2010 at 22:04
我这头像好怪…
显然没有这个……
[回复]