伸展树的学习（七）：伸展树常用的操作合集

在前面代码的基础上，我增加一些操作！

/*
* splayModel.cpp
* 本程序是在从网上搜索到的源代码经过理解、分析过后，在原有功能的基础上，
* 进行一定的优化及功能的添加，将作为我自己关于伸展树（SplayTree）的模板
* 代码。由于能力有限，本程序只处理整数
* 其实现的功能有：
* 1、根据整型数组初始化一棵树：init_tree();
* 2、往树中插入一个元素：insert();
* 3、删除树中的一个元素：remove();
* 4、指定区间的元素同时增加某个值：add();
* 5、翻转指定区间：reverse();
* 6、查询区间的最小值：query();
* 7、旋转区间k次：revolve();
* 8、插入K个元素到指定元素后面：insert_k();
* 9、从树中删除K个元素：remove_k();
* Created on: 2012-10-19
* Author: xiaoshuai
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define INF ~0u>>1
#define NIL SPLAY
#define MN 200005
using namespace std;
int n,m,l,r,x,pos;
char s[10];
struct SPLAYTREE{
struct Node{
int key,minv,size,add;
bool rev;
Node *left,*right,*father;
Node (){}
Node(int _key):key(_key){minv=_key,size=1,add=0,rev=false;}
}SPLAY[MN],*SP,*root,*head,*tail;
//tail.size=1,head.size=1(初始)而且保证以后接入的结点：Node.size>=head.size
/*
* 初始化一棵伸展树，只有head和tail结点
*/
void init(){
SP=NIL;
NIL->key=NIL->minv=INF,NIL->size=0;NIL->rev=false;NIL->add=0;
NIL->left=NIL->right=NIL->father=NIL;
head=new(++SP)Node(INF);
head->left=head->right=head->father=NIL;
tail=new(++SP)Node(INF);
tail->left=tail->right=tail->father=NIL;
head->right=tail,tail->father=head,head->size++;
root=head;//最开始，root的值为head，但接下来就未必了，也就是说：head和tail是固定不变的，而root的指向的地址是会变化的
}
/*
* 懒操作的经典代码：把当前的标记下推一个节点
* */
void pushdown(Node *&t){
if(t->rev){//如果区间需要旋转
swap(t->left,t->right);
t->left->rev=!t->left->rev;
t->right->rev=!t->right->rev;
t->rev=false;
}
if(t->add){//如果区间的值要加add
if(t->left!=NIL){
t->left->key+=t->add;
t->left->minv+=t->add;
t->left->add+=t->add;
}
if(t->right!=NIL){
t->right->key+=t->add;
t->right->minv+=t->add;
t->right->add+=t->add;
}
t->add=0;
}
}
/*
*更新区间的最小值和区间元素的个数
*/
void update(Node *&t){
t->size=t->left->size+t->right->size+1;
t->minv=min(t->key,min(t->left->minv,t->right->minv));
}
/*
* 右旋转操作
* */
void zig(Node *&t){
Node *f=t->father,*r=t->right;
pushdown(f->right);
pushdown(t->left);
pushdown(t->right);
t->father=f->father;
if(f==root) root=t;
else{
if(f->father->left==f) f->father->left=t;
else f->father->right=t;
}
t->right=f,r->father=f,f->father=t,f->left=r;
update(f);update(t);
}
/*
* 左旋转操作
* */
void zag(Node *&t){
Node *f=t->father,*l=t->left;
pushdown(f->left);
pushdown(t->left);
pushdown(t->right);
t->father=f->father;
if(f==root) root=t;
else{
if(f->father->left==f) f->father->left=t;
else f->father->right=t;
}
t->left=f,l->father=f,f->father=t,f->right=l;
update(f);update(t);
}
/*
* 伸展树的核心：伸展操作
* */
void splay(Node *&root,Node *&t){
pushdown(t);
while(root!=t){
if(t->father==root){
if(t->father->left==t) zig(t);
else zag(t);//单旋转
}
else{
if(t->father->father->left==t->father){
if(t->father->left==t) zig(t->father),zig(t);//一字旋转
else zag(t),zig(t);//之字旋转
}else{
if(t->father->left==t) zig(t),zag(t);//之字旋转
else zag(t->father),zag(t);//一字旋转
}
}
}
}
/*
* 仿线段树建树方式建立一个splay树，与build_tree合用
* */
Node* build(Node *father,int *a,int ll,int rr){
if(ll>rr)return NIL;
int mid=(ll+rr)>>1;
SP=SP+mid;
Node *t;
t=new(SP)Node(a[mid]);
t->father=father;
t->left=build(t,a,ll,mid-1);
t->right=build(t,a,mid+1,rr);
update(t);
return t;
}
/*
* function: 把数组a建立成一棵伸展树。采用的建树方式与线段树的建树方式相同
*
* @param:root 新建立树的根
* @param: a 建树用到的数组，0位置不存元素
* @param: n 数组a中元素的个数
* */
void build_tree(Node *&t,int *a,int n){
int ll=1,rr=n;
int mid=(ll+rr)>>1;
SP=SP+mid;
t=new(SP)Node(a[mid]);
t->father=NIL;
t->left=build(t,a,ll,mid-1);
t->right=build(t,a,mid+1,rr);
update(t);
}
/*
* 插入一个值到指定的位置
* */
void insert(int key,int pos){
Node *t=new(++SP)Node(key);
t->left=t->right=t->father=NIL;
Node *r=root,*p;
bool flag=false;//默认插入树的左孩子上
while(pushdown(r),r!=NIL){
p=r,r->size++;
if(r->left->size+1>pos)r=r->left,flag=false;
else pos-=r->left->size+1,r=r->right,flag=true;
}
if(flag) p->right=t;
else p->left=t;
t->father=p;
splay(root,t);
}
/*
* 把pos位置的元素旋转到根结点
* */
void select(Node *&root,int pos){
Node *r=root;
while(pushdown(r),r->left->size+1!=pos){
if(r->left->size+1>pos) r=r->left;
else pos-=r->left->size+1,r=r->right;
}
splay(root,r);
}
/*
* 把a中的n个数插入数组中，a的0号位不用
* */
void insert_k(int pos,int *a,int n){
Node *t;
build_tree(t,a,n);
select(root,pos);
select(root->right,1);
root->right->left=t;
t->father=root->right;
update(root->right);
update(root);
splay(root,t);
}
/*
* 把pos位置的元素删除
* */
void remove(int pos){
select(root,pos);
if(root->left==NIL) root=root->right;
else if(root->right==NIL) root=root->left;
else{
select(root->left,root->left->size);
root->left->right=root->right;
root->right->father=root->left;
root=root->left;
}
root->father=NIL;
update(root);
}
/*
* 删除区间[l,r]
* */
void remove_k(int ll,int rr){
//确定区间
select(root,ll);
select(root->right,rr-ll);
//执行删除操作
root->right->left=NIL;
update(root->right);
update(root);
}
/*
* 区间[l,r]同时加上a
* */
void plus(int l,int r,int a){
//确定区间
select(root,l);
select(root->right,r-l);
//执行操作
Node *t=root->right->left;
t->add+=a,t->key+=a,t->minv+=a;
splay(root,t);
}
/*
* 翻转区间[l,r]
* */
void reverse(int l,int r){
select(root,l);
select(root->right,r-l);
Node *t=root->right->left;
t->rev=!t->rev;
splay(root,t);
}
/*
* 旋转转区间[l,r] a次
* */
void revolve(int l,int r,int a){
select(root,l);
select(root->right,r-l);
select(root->right->left,root->right->left->size-a);
select(root->right->left->right,root->right->left->right->size);
Node *p=root->right->left,*t=root->right->left->right;
p->right=NIL;
p->father->left=t,t->father=p->father;
t->right=p,p->father=t;
update(t);update(p);
splay(root,p);
}
/*
* 查询区间的最小值
* */
int query(int l,int r){
select(root,l);
select(root->right,r-l);
return root->right->left->minv;
}
/*
* 从结点t开始中序遍历树
* */
void inorder(Node *t){
pushdown(t);
if(t->left!=NIL)
inorder(t->left);
if(t->key!=INF)printf("%d ",t->key);
if(t->right!=NIL)
inorder(t->right);
}
}tree;
int main(){
int a[10]={0,1,2,3,4,5,6,7,8,9};//a[0]位置不用
tree.init();//初始化一棵树
tree.insert_k(1,a,9);
cout<<"after insert array a after position 0:";tree.inorder(tree.root);cout<<endl;
tree.insert_k(1,a,9);
cout<<"after insert array a after position 0:";tree.inorder(tree.root);cout<<endl;
tree.remove_k(1,11);//确定区间的时候由于增加了head和tail两个结点，故需要把r+2，即如果删除[1,9],则参数就为[1,11]
cout<<"after remove interval [1,9]:"; tree.inorder(tree.root);cout<<endl;
tree.insert(19,1);
cout<<"after insert 19 at position 0:"; tree.inorder(tree.root);cout<<endl;
tree.remove(2);//由于我们查找的时候，左边永远有一个head，故需要加1,即如果我们删除1号位置元素，则参数就为2
cout<<"after remove position 1:";tree.inorder(tree.root);cout<<endl;
tree.plus(1,11,10);
cout<<"after plus 10 between interval [1,9]:"; tree.inorder(tree.root);cout<<endl;
tree.reverse(1,11);
cout<<"after reverse interval [1,9]:"; tree.inorder(tree.root);cout<<endl;
tree.revolve(1,11,3);
cout<<"after revolve interval [1,9] 3 times:"; tree.inorder(tree.root);cout<<endl;
int ans=tree.query(1,11);
cout<<"the min value between interval [1,9] is:"<<ans<<endl;
return 0;
}