http://allenlsy.com/2010/09/08/poj-2828/

n*2的建树方法，适用于动态建树，就是说没有任何一个节点被浪费的建法。而这里我使用的，或者说大多数人使用的这种用x*2表示左子树 x*2+1表示右子树的建法，是不能只开到n*2的，因为有写节点没用到。
举个列子来说，假如线段树的n = 11，你认为应该建树为22或者23，保守点。
（去网站看图）
如果你要找[9,9]的区间，就会出现RTE了。
那么开多少才正确呢？
其实，应该是 2^ ( seiling( log2(n) )+1 )， 即2的log2(n)的上取整加1次幂。
这道题目，用此方法计算，得到实际需要空间大小524288，我开了524300，AC了

• Re:关于线段树开空间大小的问题 (358) shenyang_ 2011-09-06 09:51:03