线段树的数组要开到多大啊

为毛一个数据范围为200000的题，开到400000还不够

我一般开到4*N

不感兴趣

开通SVIP免广告

我开到800000的确过了

我空间里有一篇分析的文章，因为懒就不复制过来了。

通常3倍至4倍……

如果你把它当完全二叉树那样表示。。。一般是3*n（但有些情况不行），4*n是无压力的
如果你用了指针的话（指静态数组模拟）， 2*n-1刚刚好

用指针的话应该不用数组了。

不感兴趣

开通SVIP免广告

……当然不够

动态开点可以

*2和*2+1那种线段树

最保险的是向上取到最近的二的次幂，再乘以2
比如一个数据范围为131073的题线段树应该开到262144*2=524288

400000是理论上的，但你可能会对叶子执行pushdown之类，因此就得浪费一倍空间

下载贴吧APP
看高清直播、视频！

分享到: