[Zju 2112] 线段树(四)
时间：2010-10-18 来源：Master_Chivu
承上三节...
本节讨论线段树的扩展应用
即树套树 树套XXX等等
}
线段树还可以和其他数据结构结合
会产生更为强大的效果
先看问题
Zju 2112
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1112
给定数列和若干询问或操作
操作修改序列的一个值 询问查询区间第K小值
区间问题 是线段树的操作
而第K小值和修改值则是 平衡树的操作
我们能否把两个强大的数据结构组合起来呢?
可以!
最常用的方法是把线段树的每个节点都建为当前区间的数构成的平衡树
这样我们就可以很容易地解决修改 建树操作
1 procedure build(a,b:longint);
2 var i,x,mid:longint;
3 begin
4 inc(ktt); x:=ktt;
5 kl[x]:=a; kr[x]:=b;
6 kls[x]:=0; krs[x]:=0;
7 t[x]:=0;
8 if b-a>1
9 then begin
10 mid:=(kl[x]+kr[x])shr 1;
11 kls[x]:=ktt+1; build(a,mid);
12 krs[x]:=ktt+1; build(mid,b);
13 end;
14 for i:=a+1 to b do
15 insert(t[x],v[i]);
16 end;
建树每次新建节点都插入区间内所有节点即可
实质上线段树保存的是当前区间内平衡树根节点的指针
而存储平衡树的数组存储了所有的平衡树 是一个森林
1 function change(x,a,c:longint):longint;
2 var mid,temp:longint;
3 begin
4 if (kl[x]=a-1)and(kr[x]=a)
5 then begin
6 change:=n[t[x]];
7 t[x]:=0; insert(t[x],c);
8 end
9 else begin
10 mid:=(kl[x]+kr[x])shr 1;
11 if a<=mid
12 then temp:=change(kls[x],a,c)
13 else temp:=change(krs[x],a,c);
14 delete(t[x],temp);
15 insert(t[x],c);
16 change:=temp;
17 end;
18 end;
只需从被修改节点所在的叶子节点开始 一路向上到根为止
对路径上所有的区间平衡树 都执行删除原先的节点 插入新的节点操作即可
这样修改操作的复杂度上界是O(Log2N*Log2N) 符合要求
比较复杂的是查询操作
由于我们只知道整块的区间(直接为线段树节点的区间)内的情况
而任意区间(由线段树内整区间拼接)的情况全然不知
所以我们要完成拼接区间的操作
我用SBT实现了线段树内的平衡树
考虑二分答案
二分排序后区间内的所有值 然后判定
我们设当前二分值为mid 在mid
我们用getsum函数判定mid在所查询区间内的排位(rank)
1 function getsum(x,a,b,c:longint):longint;
2 var mid,temp:longint;
3 begin
4 if (a<=kl[x])and(kr[x]<=b)
5 then begin
6 flag:=flag or(find(t[x],c));
7 getsum:=rank(t[x],c);
8 end
9 else begin
10 temp:=1;
11 mid:=(kl[x]+kr[x])shr 1;
12 if a<mid then temp:=temp+getsum(kls[x],a,b,c)-1;
13 if b>mid then temp:=temp+getsum(krs[x],a,b,c)-1;
14 getsum:=temp;
15 end;
16 end;
依旧是用经典的线段树查询代码
getsum很形象地表示了段代码查询rank的方式 累加
举个例子 好理解些
比如我们查询到所查区间由3个整区间拼接而成
区间内值分别是
A:{1 5 3 5} 排序后 {1 3 5 5}
B:{8 9 10 4 5 7} 排序后 {4 5 7 8 9 10}
C:{12 13 7 0} 排序后 {0 7 12 13}
拼起来就是所查区间X:{0 1 3 4 5 5 5 7 7 8 9 10 12 13}
由于会出现所查数不在所查区间内
我们把排名看作插入此数后的排名
比如查询10的排名 显然我们可以看出10在最后的所查区间排名是12
我们接着可以看在A B C中10的排名
A:5 {1 3 5 5 10}
B:6 {4 5 7 8 9 10}
C:3 {0 7 10 12 13}
我们还可以发现把两个集合合并之后
如果mid在A中排位为r1 在B中排位为r2 则在合并后为r1+r2-1
这就是我们累计求rank的基本原理 证明很简单 考虑比mid小的数的个数即可
有了判定过程 我们继续考虑二分的过程
我们运用二分答案 最需要仔细考虑
首先考虑单调性
显然这个二分是有单调性的
如果一个数的rank小于目标rank 则不是最终解
如果一个数的rank等于目标rank 则有可能是最终解
如果一个数的rank大于目标rank 则必定不是最终解
然后考虑二分细节
1 l0:=1; r0:=m;
2 while l0<r0 do
3 begin
4 flag:=false;
5 mid:=(l0+r0+1)shr 1;
6 now:=select(t[1],mid);
7 rnk:=getsum(1,x-1,y,now);
8 if rnk<=z then l0:=mid else r0:=mid-1;
9 end;
10 writeln(select(t[1],l0));
注意这段代码 完全是按照单调性来写的
没有在循环过程中直接判定是解 然后退出输出 而是等l=r时再退出
这样在有解的情况下必然出解(而数据保证有解)
没有让l0=mid+1 而是让l0=mid
这样保证最终解始终在我们二分出的范围内
正是考虑到了数可以重复出现 普通二分可能错过最终解 才修改了二分的过程
相应地 为了避免死循环 mid=(l0+r0+1)shr 1
解决了这一系列的操作
我们就完成了对问题的解决
完整代码在文章最后
线段树还可以套线段树
还可以扩展为四分树 亦可套有序线性表 扩展性还是很好的
下一节讨论树状数组 一个牛B的由线段树衍生出的数据结构
BOB HAN 原创 转载请注明出处 http://www.cnblogs.com/Booble/
{$I+,Q+,R+,S+}
const maxn=60000;
max=1000000;
var l,r,s,n:array[0..max]of longint;
kl,kr,kls,krs,t:array[1..maxn shl 1]of longint;
u,v,w:array[1..maxn]of longint;
rnk,c,m,k,i,ktt,tt,x,y,z,l0,r0,mid,now:longint;
flag:boolean;
ch:char;
procedure zig(var x:longint);
var y:longint;
begin
y:=l[x]; l[x]:=r[y]; r[y]:=x;
s[y]:=s[x]; s[x]:=s[l[x]]+s[r[x]]+1;
x:=y;
end;
procedure zag(var x:longint);
var y:longint;
begin
y:=r[x]; r[x]:=l[y]; l[y]:=x;
s[y]:=s[x]; s[x]:=s[l[x]]+s[r[x]]+1;
x:=y;
end;
procedure maintain(var x:longint; flag:boolean);
begin
if flag
then begin
if s[l[l[x]]]>s[r[x]] then zig(x)
else if s[l[r[x]]]>s[r[x]]
then begin zag(l[x]); zig(x); end
else exit;
end
else begin
if s[r[r[x]]]>s[l[x]] then zag(x)
else if s[r[l[x]]]>s[l[x]]
then begin zig(r[x]); zag(x); end
else exit;
end;
maintain(l[x],true); maintain(r[x],false);
maintain(x,true); maintain(x,false);
end;
procedure insert(var x:longint; v:longint);
begin
if x=0
then begin
inc(tt); x:=tt;
s[x]:=1; n[x]:=v;
l[x]:=0; r[x]:=0;
end
else begin
inc(s[x]);
if v<=n[x]
then insert(l[x],v)
else insert(r[x],v);
maintain(x,v<=n[x]);
end;
end;
function delete(var x:longint; v:longint):longint;
begin
dec(s[x]);
if (v=n[x])or(v<n[x])and(l[x]=0)or(v>n[x])and(r[x]=0)
then begin
delete:=n[x];
if (l[x]=0)or(r[x]=0)
then x:=l[x]+r[x]
else n[x]:=delete(l[x],n[x]+1);
end
else if v<=n[x]
then delete:=delete(l[x],v)
else delete:=delete(r[x],v);
end;
function find(x,v:longint):boolean;
begin
if x=0 then exit(false);
if v=n[x] then exit(true);
if v<n[x] then find:=find(l[x],v)
else find:=find(r[x],v);
end;
function select(x,k:longint):longint;
begin
if s[l[x]]+1=k then exit(n[x]);
if k<=s[l[x]] then select:=select(l[x],k)
else select:=select(r[x],k-s[l[x]]-1);
end;
function rank(x,v:longint):longint;
begin
if x=0 then exit(1);
if v<=n[x] then rank:=rank(l[x],v)
else rank:=rank(r[x],v)+s[l[x]]+1;
end;
procedure build(a,b:longint);
var i,x,mid:longint;
begin
inc(ktt); x:=ktt;
kl[x]:=a; kr[x]:=b;
kls[x]:=0; krs[x]:=0;
t[x]:=0;
if b-a>1
then begin
mid:=(kl[x]+kr[x])shr 1;
kls[x]:=ktt+1; build(a,mid);
krs[x]:=ktt+1; build(mid,b);
end;
for i:=a+1 to b do
insert(t[x],v[i]);
end;
function getsum(x,a,b,c:longint):longint;
var mid,temp:longint;
begin
if (a<=kl[x])and(kr[x]<=b)
then begin
flag:=flag or(find(t[x],c));
getsum:=rank(t[x],c);
end
else begin
temp:=1;
mid:=(kl[x]+kr[x])shr 1;
if a<mid then temp:=temp+getsum(kls[x],a,b,c)-1;
if b>mid then temp:=temp+getsum(krs[x],a,b,c)-1;
getsum:=temp;
end;
end;
function change(x,a,c:longint):longint;
var mid,temp:longint;
begin
if (kl[x]=a-1)and(kr[x]=a)
then begin
change:=n[t[x]];
t[x]:=0; insert(t[x],c);
end
else begin
mid:=(kl[x]+kr[x])shr 1;
if a<=mid
then temp:=change(kls[x],a,c)
else temp:=change(krs[x],a,c);
delete(t[x],temp);
insert(t[x],c);
change:=temp;
end;
end;
procedure sort(l,r:longint);
var i,j,x1,x2,y:longint;
begin
i:=l; j:=r;
x1:=u[(l+r)shr 1];
x2:=w[(l+r)shr 1];
repeat
while (u[i]<x1)or(u[i]=x1)and(w[i]<x2) do inc(i);
while (u[j]>x1)or(u[j]=x1)and(w[j]>x2) do dec(j);
if not(i>j)
then begin
y:=u[i]; u[i]:=u[j]; u[j]:=y;
y:=w[i]; w[i]:=w[j]; w[j]:=y;
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
procedure out(x:longint);
begin
if x=0 then exit;
out(l[x]);
write(n[x],' ');
out(r[x]);
end;
begin
assign(input,'rank.in'); reset(input);
assign(output,'rank.out'); rewrite(output);
readln(c);
while c>0 do
begin
dec(c);
readln(m,k);
for i:=1 to m do
read(v[i]);
readln;
tt:=0; ktt:=0; s[0]:=0;
build(0,m);
for i:=1 to k do
begin
read(ch);
read(x,y);
if ch='Q' then read(z);
readln;
case ch of
'Q':
begin
l0:=1; r0:=m;
while l0<r0 do
begin
flag:=false;
mid:=(l0+r0+1)shr 1;
now:=select(t[1],mid);
rnk:=getsum(1,x-1,y,now);
if rnk<=z then l0:=mid else r0:=mid-1;
end;
writeln(select(t[1],l0));
end;
'C':
begin
change(1,x,y);
//out(t[1]); writeln;
end;
end;
end;
end;
close(input); close(output);
end.
相关阅读 更多 +
