线段树开4N个节点足够的正确性证明

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

线段树开4N个节点足够的正确性证明

作者：

tomousw , 2023-06-10 21:53:46 , 所有人可见 , 阅读 175

最后一层需要开的节点数为 $2^{\lceil\log_{2}^{n}\rceil}$
而 $\lceil\log_{2}^{n}\rceil<\log_{2}^{n}+1$
则 $2^{\lceil\log_{2}^{n}\rceil}<2n$
即当倒数第二层开 $n$ 个，倒数第一层 $2n$ 个时一定足够
此时共 $4n-1$ 个
证毕

0 评论

App 内打开