首页 > 代码库 > 线段树为什么要开4倍空间
线段树为什么要开4倍空间
假设我们用一个数组来头轻脚重地存储一个线段树，根节点是1，孩子节点分别是2n, 2n+1, 那么，设线段长为L(即[1..L+1))
设树的高度为H，对H，有：
这是一个很简单的递归式，并用公式（http://scinart.github.io/math/2014/03/16/QA39.2.G733-1994-CM-3/#mjx-eqn-3.11）逐次代换，就等到
所以
所以显然所需空间为
2^H?1=2^(?lgL?+1)?1
=2×2^(?lgL?)?1
=2×2(L?1)?1,L≥2
=4L?5,L≥2
-- EOF --（过程来自于http://scinart.github.io/acm/2014/03/19/acm-segment-tree-space-analysis/）跟大家一起分享下!
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。