首先我们归纳证明,当 x=LChild(Root)或者 y=RChild(Root)时,f(Root)<=Log
2
n 成立。
(这个我们称之为引理)其中 n=R(Root)-L(Root),我们对 n 进行归纳。
f(Root)=f(LChild(Root))+f(RChild(Root))
1.如果 x=L(Root)
如果 y<=m , 那么 f(RChild(Root))=0 ,所以 f(Root)=f(LChild(Root)) 。 根 据归纳假 设
f(LChild(Root))<=Log
2
n。所以 f(Root)<=Log
2
n
如果 y>m,那么:
f(Root)=f(LChild(Root))+f(RChild(Root))
此时[a,b]完全覆盖 LChild(Root),所以 f(LChild(Root))=1;因为 L(RChild(Root))=m,而
[a,b]和 RChild(Root)的交集是[m,y],根据引理的归纳假设 f(RChild(Root))<=log
2
(n/2)。也就
是说:
f(Root)= 1+f(RChild(Root))<=1+ log
2
(n/2)=log
2
n
2.如果 y=R(Root)
和 x=L(Root)类似。
以上两点综合可以证明,当[a,b]和 Root 线段的交集在 Root 的左边界或者右边界重合时,
f(Root)=log
2
n。(n=R(Root)-L(Root))
接下来我们归纳证明对于一般情况 f(Root)<=2log
2
n。(还是对 n 归纳。n=R(Root)-
L(Root))
[a,b]和 Root 线段的交集还是设为[x,y]。m 是 Root 线段的中点。
1.如果[x,y]完全包含于[L(Root)..m]之内,则 f(RChild(Root))=0,所以:
f(Root)=f(LChild(Root))
根据归纳假设 f(LChild(Root))<=2log
2
n。
2.如果[x,y]完全包含于[m..R(Root)]之内,则 f(LChild(Root))=0。和 1 类似。
3.如果 1., 2.都不满足,那么必然有 L(Root)<=x<=m,m<=y<=R(Root)。
那么 f(LChild(Root))和 f(RChild(Root))就都落入了引理的研究范围,即 f(LChild(Root)),
f(RChild(Root))都满足<=log
2
n/2。
所以 f(Root)= f(LChild(Root))+f(RChild(Root))<=2log
2
n/2<=2log
2
n。
综上所述,总有 f(Root)<=2log
2
n。即 f(Root)~O(log
2
n)。
这就是说我们插入或者拿走一根黑布的时间复杂度是 O(logn)。
回到原来的题目。如何输出有黑色区间的总长度?
给每个节点加入一个属性 Len,用 Len(Root)表示。Len(Root)的意义就是:把以 Root
为根的子树中所有的黑布条叠加起来,被染黑区间的总长度。
如果 Count(Root)>0,则 Len(Root)=R(Root)-L(Root)。
否则 Len(Root)=Len(LChild(Root))+Len(RChild(Root))。
因为每次添加/去掉布条只要改动树中至多 2log
2
n 个节点,所以也只有这 2log
2
n 个节点
的 Len 值会出现变动,及时更新即可,时间复杂度 O(log
2
n)。
每次添加删除布条后直接输出 Len(Root)即可。新的 Add 过程如下:
procedure Add(Root, a, b);
begin
if Root = NIL then
Exit;
if (a<=L(Root))and(b>=R(Root)) then {[a,b]完全包含该线段}
Count[Root] Count[Root] + 1 {因为 Root 代表的线段被覆盖了,所以将其标记}