n*2的建树方法，适用于动态建树，就是说没有任何一个节点被浪费的建法。而这里我使用的，或者说大多数人使用的这种用x*2表示左子树 x*2+1表示右子树的建法，是不能只开到n*2的，因为有写节点没用到。 举个列子来说，假如线段树的n = 11，你认为应该建树为22或者23，保守点。 如果你要找[9,9]的区间，就会出现RTE了。 那么开多少才正确呢？ 其实，应该是 2^ ( ceiling( log2(n) )+1 )， 即2的log2(n)的上取整加1次幂。
原文：http://www.cnblogs.com/fqqq/p/4995359.html