关于线段树的疑问

Question

在n=2^k+j的情况需要的数组空间 老师给的是4n 这样会不会给得太过于足够了 这个空间。

其实应该 为 2^（k+2）空间吧，也就是在n中找到不大于n但是满足2的最大k次方，找到这个k值，然后基于这个k乘以4。

Answer 1

liuyubobobo 2018-06-26 17:29:37

赞！可以参考这个问答下的讨论：）

https://coding.imooc.com/learn/questiondetail/58660.html

加油！

• 提问者 丶远走高飞 #1

  所以说 其实是故意再多浪费空间，目的是为了不反推这个k值么

• liuyubobobo 回复 提问者 丶远走高飞 #2

  是犯懒啊！哈哈：）开4n的空间是算法竞赛中实现线段树的惯例。从没遇到过因为4n的空间比2^（k+2）大所以导致内存溢出（MLE）的情况。但是如果你的实际业务场景内存空间特别吃紧，可以改进代码，开辟2^（k+2）的空间，甚至放弃使用数组存储的线段树（因为即使这个空间足够紧，也有很多空间浪费！），转而使用基于节点链式链接的线段树：）

• 提问者 丶远走高飞 回复 liuyubobobo #3

  了解了，谢谢老师