在一维数组中以完全二叉树方式存储线段树的空间分析

我们大家存储线段树的方式无非两种:

  1. 二叉链表
  2. 一维数组完全二叉树

二叉链表优点是节省空间,缺点是编程复杂度大,执行效率较低,空间复杂度为2N

在一维数组以完全二叉树方式存储线段树的编程复杂度小,执行效率较高,但浪费空间
长期以来,我和我校的OIer一直不知以一维方式存储线段树到底需要开多大的数组.今天正好有些闲暇的时间,写了个小程序,分析了下一维线段树在一维方式存储下到底需要占用多少空间.经本文所述方式计算约为4N

先来补习一下完全二叉树的相关知识:
完全二叉树在一维数组中这样表示:根节点为1,其左子树为2,右子树为3.
根节点为N,其左孩子为2N,右孩子为2N+1
具体实现方式可参考我的一篇题解,这里使用的就是完全二叉树方式

像线段树这样区间长度并不一定是\( 2^{n}\)的二叉树,其占用空间为 2的(最深线段的深度)次幂,就给线段树的空间占用造成了很大的不确定性.在我们学校,关于线段树的空间占用,说法大致有以下几种

  • 极端保守的:10N
  • 保守(我):5N
  • 乐观:3N
  • 极乐观:2N

然而大家写的是后大部分都是尽量多开,对于其空间占用一直没有定论,现在我来给个定论:

先上一幅图:

完全二叉树方式存储线段树的空间占用

可以看到,空间复杂度其实是最好\(\Theta(2N) \),最差是\(\Theta(4N) \),最好情况出现在略小于\(2^{k}\)附近,最坏情况出现在略大于\(2^{k}\)附近,由此看来,我们以后存线段树大概需要开4N+100 的数组就可以了.

附线段树空间计算程序:

输入区间长度,他来告诉你要开多大数组.

附线段树空间占用分析程序(打表),上面那个图的表就是它计算出来的:

然后打了个表,可以用来查询线段树空间

原创文章,转载请注明: 转载自Comzyh的博客

本文链接地址: 在一维数组中以完全二叉树方式存储线段树的空间分析

One reply on “在一维数组中以完全二叉树方式存储线段树的空间分析

发表评论

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