线段树开4N空间的证明

线段树写法有很多种,一般来说有:①链表写法,因为线段树是一颗二叉树,写成二叉链表是没有问题的;②数组表示,素组表示一般来说比链表写法看似空了很多节点,而实际上,因为没有二叉链表的node *left、node * right指针,实际上是大大地节省了空间,而且没有链表指针转换操作,速度也会加快。

其中数组表示也有几种细微差别的写法:①节点下标从0开始还是1开始(注意是下标,不是值,值是正负或者实数都是无关系的);②mid节点属于左边还是右边,这个会引起线段树最终的形状,比如mid属于左边,那么线段树的最后一层节点,偏左边;而mid属于右边,那么最后一层的节点往往会从右边开始排列。

注意:不管哪种写法线段树并非一颗完全二叉树!下文你就会自觉地发现。其中mid属于右边的写法,因为最终的节点在右边开始,已然不是完全二叉树。

ACMer学线段树一般都是需要使用线段树的数组表示,比较简约的一种方式是这里的这种方式,实际上利用了数组在内存地址的连续性,从而加快了进程,也节省了空间。
假设我们N个连续的节点需要建立线段树,如果最下层有节点,那么最左边一定不是空的。而最左边节点也就是左儿子是:[l,(l+r)>>1]。因此就是(1+N)不停除以2。那么线段树的深度为\(\lceil\log_2 (1+N)\rceil\) (根节点深度这里定义为1). 假如是满二叉树,那么节点数为
$$2^{\lceil\log_2 (1+N)\rceil}-1$$
通过matlab画图比较,容易得到下面的图像:

1-80个节点的情况

1-80个节点的情况

1-1e5的情况

1-1e5的情况


例如N=20时:
线段树节点超过2N个的证明

线段树节点超过2N个的证明

本文链接:线段树开4N空间的证明

转载声明:本站文章若无特别说明,皆为原创,转载请注明来源:Rexdf,谢谢!^^


此条目发表在ACM文化分类目录,贴了标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

:zsmilebig: :zsadbig: :zwiredbig: :zgreenhappy: more »

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据