在线段树中，我们在数组之上构建线段树。
例如，如果数组大小为8[0-7]索引。
线段树中的节点数为 15，即 1、2、3、4 级中的 1、2、4、8
但是在一个问题中，如果我将结构数组大小声明为 seg tree[2*N + 1] 它会给出错误的答案，而如果我将其声明如下
struct seg{
int sum;
};
seg tree[4*N + 1];
它给出了错误的答案。我的疑问是 [2*N] 就足够了，那为什么会给出错误的答案。
节点段(1-1)的编号为9，其父节点的编号为4。所以左 child 是2*N，右 child 是2*N+1
最佳答案
设n 为初始数组的大小。线段树的大小为:
2*n-1如果n是 2 的幂。2*2^(log_2(n)+1)-1如果n不是 2 的幂。
编辑:我们确实可以只创建一个大小为 2*n-1 的数组来在理论上创建一棵树，但请考虑我们如何在数组表示中从父级到子级线段树？左 child 位于索引 2*i+1(从 0 开始索引)，右 child 位于索引 2*i+2。为了保持这个不变量，我们必须构造完整的二叉树，为此公式如上。
您也可以引用this .
关于c++ - 线段树数据结构中的数组大小，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37201440/