在线段树中,一般都不需要刻意保存其左右子结点的下标,而直接由其本身的下标导出,传统的写法是:
根结点:1
A的左子结点:2A(写成A<<1)
A的右子结点:2A+1(写成(A<<1)+1)
这种表示法可以表示出整棵线段树,因为:
(1)每个结点的子结点的下标都比它大,这样就不会出现环;
(2)每个结点的父结点都是唯一的(其本身下标整除2);
但是,这种表示法有一个弱点:结点的下标是有可能超过2N的,但不会超过4N,因此,为了表示出跨度为N的线段,我们需要开4N的空间,然而,其中只有2N-1个位置是有用的(因为表示跨度为N的线段的线段树共有(2N-1)个结点),这样,就有一半的空间被浪费。尤其是这种线段树推广到多维的时候——K维线段树就只有1/2K的位置是有用的,空间利用率非常低。在某些卡空间的场合,它就囧掉了。

那么,有木有好一点的写法呢?最好能使空间利用率达到100%——也就是所有结点的下标刚好就是1~(2N-1)!!(0号结点一般作为“哨兵”,不被占用)
并且,这种写法要保证仅仅由结点的下标和它表示的线段的左右端点(因为在遍历线段时,下标和左右端点基本上都是同时知道的),就能得出其子结点的下标,而不需要借助额外的东东(最好mid都不需要算)。
这种写法就是——直接将每个结点的DFS遍历次序当做它的下标!!
比如,跨度为6的线段树:

容易发现,根结点下标为1,下标为A的结点的左子结点下标为(A+1),右子结点下标为A+SZ(A.L)+1,其中SZ(A.L)为A的左子树大小。
若A的左右端点为l、r,mid=(l+r)/2(下取整),则A的左子树所表示的线段为[l, mid],所以SZ(A.L)=(mid-l+1)*2-1=(mid-l)*2+1=((r-l-1)/2(上取整))*2+1
这样,A的右子结点下标就是A+((r-l+1)/2(上取整))*2,也就是A加上大于(r-l)的最小的偶数
写在代码里就是:
int mid=l+r>>1;
opr(l, mid, A
+1);
opr(mid
+1, r, (r-l&1?A+r-l+1:A+r-l+2));
或者,借助位运算,可以免去条件判断:
int mid=l+r>>1;
opr(l, mid, A
+1);
opr(mid
+1, r, A+r-l+2-((r^l)&1));
经测试,后者(使用位运算的)虽然总的运算次数多于前者(使用条件判断的),但后者比前者快一点点,其原因可能与C语言中的条件运算符速度较慢有关;

这样,我们就成功地将线段树下标的空间利用率提高到了100%!!以后只需要开2N空间就行了囧……
与传统表示法相比,这种新式表示法虽然可以节省空间,但时间消耗要更大一些(时间和空间总是矛盾的囧……),因为它在找右子结点的时候需要较多的运算。平均起来,新式表示法比传统表示法要慢10~15%,对于某些坑爹的数据(对右子结点调用比较多的那种)可能慢得更多。此外,在下放标记的时候,传统表示法只需要知道结点下标就行了,而新式表示法必须同时知道结点的左右端点,这样在dm中就需要传递三个参数,从而要慢一些,当然,我们可以不用dm,直接在操作里面写标记下放。

Feedback

# re: 【AHOI2013复仇】关于线段树下标的一种优化表示法[未登录]  回复  更多评论   

2012-12-21 22:08 by xiaodao
zkw 线段树?。。。。

# re: 【AHOI2013复仇】关于线段树下标的一种优化表示法  回复  更多评论   

2015-05-05 15:03 by zkw
zkw线段树表示不服!!!

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理