伸展树算法.docx

伸展树学习
1、access(i,t):如果i在树t中,则返回指向它的指针,否则返回空指针。ess(i,t),可以从树t的根部向下查找i。如果查找操作遇到了一个含有i的节点x,就在x处进行splay操作,并返回指向x的指针,访问结束。如果遇到了空指针,表示i不在树中,此时就在最后一个非空节点处进行splay操作,然后返回空指针。如果树是空的,将忽略掉splay操作。
2、insert(i,t):将条目i插入树t中(假设其尚不存在)。为了实现insert(i,t),首先执行split(i,t),然后把t换成一个由新的包含有i的根节点组成的树,这个根节点的左右子树分别是split返回的树t1和t2。
3、delete(i,t):从树t中删除条目i(假设其已经存在)。为了实现delete(i,t),ess(i,t),然后把t换成其左子树和右子树join之后的新树。
4、join(t1,t2):将树t1和t2合并成一棵树,其中包含之前两棵树的所有条目,并返回合并之后的树。这个操作假设t1中的所有条目都小于t2 中的条目,操作完成之后会销毁t1和t2。为了实现join(t1,t2),首先访问t1中最大的条目i。访问结束之后,t1的根节点中包含的就是i,它的右孩子显然为空。于是把t2作为这个根节点的右子树并返回完成之后的新树即可实现join操作。
5、split(i,t):构建并返回两棵树t1和t2,其中t1包含t中所有小于等于i的条目,t2包含t中所有大于i的条目。操作完成之后销毁t。为了实现split(i,t),ess(i,t),然后根据新根节点中的值是大于还是小于等于i来切断这个根节点的左链接或右链接,并返回形成的两棵树。
另外insert和delete方法有更好的实现,时间复杂度更小:
1、insert(i, t):查找i,把遇到的空指针替换成一个含有i的新节点,然后再在新节点处对树进行splay操作。
2、delete(i, t):查找含有i的节点,设此节点为x,其父节点为y。把x的左右子树合并之后替换掉x,然后再从y处进行splay操作。
const
maxn=100000+5;
oo=maxlongint shr 1;
var
n,root,task:longint;
a,son,l,r,b1,b2,mi:array [0..maxn+maxn] of longint;
function min(x,y:longint):longint;
begin
if x<y then min:=x else min:=y;
end;
procedureinit;
var
i:longint;
begin
readln(n);
root:=n+2;
for i:=2 to n+1 do
begin
readln(a[i]);
l[i]:=i-1;
son[i]:=i;
mi[i]:=a[i];
end;
l[n+2]:=n+1;
son[1]:=1;
son[n+2]:=n+2;
mi[0]:=oo;
mi[1]:=oo;
mi[n+2]:=oo;
a[1]:=oo;
a[n+2]:=oo;
n:=n+2;
end;
procedure update(i:longint);
begin
son[i]:=son[l[i]]+son[r[i]]+1;
mi[i]:=min(min(mi[l[i]],mi[r[i]]),a[i]);
end;
procedure left(var i:longint);
var
j:longint;
begin
j:=r[i];
r[i]:=l[j];
l[j]:=i;
update(i);
update(j);
i:=j;
end;
procedure right(var i:longint);
var
j:longint;
begin
j:=l[i];
l[i]:=r[j];
r[j]:=i;
update(i);
update(j);
i:=j;
end;
procedure put1(i,j:longint);
begin
ifi=0 then exit;
a[i]:=a[i]+j;
mi[i]:=mi[i]+j;
b1[i]:=b1[i]+j;
end;
procedure put2(i:longint);
var
z:longint;
begin
ifi=0 then exit;
z:=l[i];
l[i]:=r[i];
r[i]:=z;
b2[i]:=1-b2[i];
end;
procedure up(var i:l