伸展树算法
- 格式：docx
- 大小：25.40 KB
- 文档页数：16
伸展树学习
1、access(i,t):如果i在树t中，则返回指向它的指针，否则返回空指针。为了实现access(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)，首先执行access(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)，首先执行access(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
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:longint;k:longint);
begin
ifi=0 then exit;
if b1[i]>0 then
begin
put1(l[i],b1[i]);
put1(r[i],b1[i]);
b1[i]:=0;
end;
if b2[i]>0 then
begin
put2(l[i]);
put2(r[i]);
b2[i]:=0;
end;
if k<=son[l[i]] then
begin
up(l[i],k);
right(i);
end else
if k>son[l[i]]+1 then
begin
up(r[i],k-son[l[i]]-1);
left(i);
end; end;
procedure work;
var
i,j,k,kk,c,z:longint;
st:string;
begin
readln(task);
for task:=1 to task do
begin
readln(st);
whilest[length(st)]=' ' do delete(st,length(st),1);
st:=st+' ';
if (st[1]='A') then c:=1 else
if (st[1]='R') and (st[4]='E') then c:=2 else
if (st[1]='R') and (st[4]='O') then c:=3 else
if (st[1]='I') then c:=4 else
if (st[1]='D') then c:=5 else c:=6;
delete(st,1,pos(' ',st));
val(copy(st,1,pos(' ',st)-1),i,z);
delete(st,1,pos(' ',st));
if length(st)>1 then
begin
val(copy(st,1,pos(' ',st)-1),j,z);
delete(st,1,pos(' ',st));
if length(st)>1 then val(copy(st,1,length(st)-1),k,z);
end;
case c of
1:begin
inc(i);
inc(j);
up(root,i-1);
up(root,j+1);
put1(r[l[root]],k);
end;
2:begin
inc(i);inc(j);
up(root,i-1);up(root,j+1);
put2(r[l[root]]);
end;
3:begin
inc(i);
inc(j);
up(root,i-1); up(root,j+1);
k:=k mod (j-i+1);
if k>0 then
begin
kk:=r[l[root]];
up(kk,j-k-i+1);
up(r[kk],k);
z:=r[kk];
r[z]:=kk;
r[l[root]]:=z;
r[kk]:=0;
update(r[z]);
update(z);
end;
end;
4:begin
inc(i);
inc(n);
a[n]:=j;
mi[n]:=j;
j:=n;
up(root,i);{把i旋转到root处}
r[j]:=r[root];
r[root]:=j;
update(j);
update(root);
end;
5:begin
inc(i);
up(root,i);{把以root为根的树中的第i小的旋转到root处}
up(r[root],1);{把以r[root]为根的树中的第i小的旋转到r[root] 处}
l[r[root]]:=l[root];
root:=r[root];
update(root);
end;
6:begin
inc(i);
inc(j);
up(root,i-1);
up(root,j+1);
writeln(mi[r[l[root]]]);
end;
end;
end;
