运用伸展树解决数列维护问题

《运用伸展树解决数列维护问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、运用伸展树解决数列维护问题运用伸展树解决数列维护问题1ByCrash【关键词】数列维护问题、伸展树【摘要】对于数列维护问题，我们常用的一种手段是线段树。但使用线段树有一定的局限性，本文介绍运用伸展树解决这类问题，并且可以实现更多的功能。【目录】（1）伸展树的伸展操作（2）在伸展树中对区间进行操作（3）实例分析——NOI2005维护数列（Sequence）（4）和线段树的比较1Blog地址：http://hi.baidu.com/oimaster第1页共8页运用伸展树解决数列维护问题（1）伸展树的伸展操作伸展树属于一种平衡树，我们可以把其当做普通的排序二叉树使用，但是其功能不局限于此。伸展

2、树的核心就是Splay（伸展）操作，SplayX()表示把结点X旋转到整棵树的根，这里的旋转方法同其他的平衡树。一般人对于这个操作，可能首先想到的方法就是简单的一层一层向上旋转，但是这样常常无法改变树的形态，一条链Splay后还是一条链。因此伸展树使用了一些新的方法进行这个看似简单的操作。分三种情况讨论：1.如果当前结点父结点即为根结点，那么我们只需要进行一次简单旋转即可完成任务，我们称这种旋转为单旋转。2.设当前结点为X，X的父结点为Y，Y的父结点为Z，如果Y和X同为其父亲的左孩子或右孩子，那么我们先旋转Y，再旋转X。我们称这种旋转为一字形旋转。3.最后一种就是和上面相反的情况，这时我

3、们连续旋转两次X。我们称这种旋转为之字形旋转。ZXYYDAXZCBAB图一一字形旋转CD第2页共8页运用伸展树解决数列维护问题ZXYYZDXAABCD图二之字形旋转BC通常来说，每进行一种操作后都会进行一次Splay操作，这样可以保证每次操作的平摊时间复杂度是On(log)。关于证明可以参见相关书籍和论文。既然可以把任何一个结点转到根，那么也就可以把任意一个结点转到其到根路径上任何一个结点的下面（特别地，转到根就是转到空结点Null的下面）。下面的利用伸展树维护数列就要用到将一个结点转到某个结点下面。最后附上Splay操作的代码：//node为结点类型，其中ch[0]表示左结点指针，ch

4、[1]表示右结点指针//pre表示指向父亲的指针voidRotate(node*x,intc)//旋转操作，c=0表示左旋，c=1表示右旋{node*y=x->pre;y->ch[!c]=x->ch[c];if(x->ch[c]!=Null)x->ch[c]->pre=y;x->pre=y->pre;if(y->pre!=Null)if(y->pre->ch[0]==y)y->pre->ch[0]=x;elsey->pre->ch[1]=x;x->ch[c]=y,y->pre=x;if(y==root)root=x;//root表示整棵树的根结点}voidSplay(node*x,nod

5、e*f)//Splay操作，表示把结点x转到结点f的下面{for(;x->pre!=f;)if(x->pre->pre==f)//父结点的父亲即为f，执行单旋转if(x->pre->ch[0]==x)Rotate(x,1);elseRotate(x,0);第3页共8页运用伸展树解决数列维护问题else{node*y=x->pre,*z=y->pre;if(z->ch[0]==y)if(y->ch[0]==x)Rotate(y,1),Rotate(x,1);//一字形旋转elseRotate(x,0),Rotate(x,1);//之字形旋转elseif(y->ch[1]==x)Rotate

6、(y,0),Rotate(x,0);//一字形旋转elseRotate(x,1),Rotate(x,0);//之字形旋转}}（2）在伸展树中对区间进行操作首先我们认为伸展树的中序遍历即为我们维a-1护的数列，那么很重要的一个操作就是怎么在伸展树中表示任意一个区间。比如我们要提取区间b+1ab,，那么我们将a前面一个数对应的结点转到树根，将b后面一个结点对应的结点转到树根的右边，那么根右边的左子树就对应了区间ab,。*其中的道理也是很简单的，将a前面一个数对图三提取区间应的结点转到树根后，a及a后面的数就在根的右子树上，然后又将b后面一个结点对应的结点转到树根的右边，那么ab,

7、这个区间就是图三中*所示的子树。利用这个，我们就可以实现线段树的一些功能，比如回答对区间的询问。我们在每个结点上记录关于以这个结点为根的子树的信息，然后询问时先提取区间，再直接读取子树的相关信息。还可以对区间进行整体修改，这也要用到和线段树类似的延迟标记技术，就是对于每个结点，再额外记录一个或多个标记，表示以这个结点为根的子树是否被进行了某种操作，并且这种操作影响其子结点的信息值。当然，既然记录了标记，那么旋转和其他一些操作中也就要