线段树构建方法

Question

嗨，我正在学习线段树。使用递归方法构建线段树对我来说很清楚，我是这样实现的：

void build( int n, int b, int e){
    if(b > e) return;
    else if (b == e) { tree[n] = arr[b]; return }
    build(n*2 , b , (b+e)/2 );
    build(n*2+1 , (b+e)/2+1 , e );
    tree[n] =  tree[n*2] + tree[n*2 + 1] ;
}

但我见过这样的射手实现：

    void build() {  // build the tree
      for (int i = n - 1; i > 0; --i) t[i] = t[i<<1] + t[i<<1|1];
   }

i understand that t[i<<1] is same as  t[2*i] and t[i<<1|1] is same as t[2*i+1]

但是这个逻辑如何帮助我构建线段树？？一个简单的例子会很有帮助

Answer 1

实际上，您的代码和他们的代码中有一个不同的 "function" build()。在您的代码中，当您构建线段树时，您还输入了叶子值，但是在他们的代码中，他们在以下语句中输入了叶子值：

for (int i = 0; i < n; ++i) scanf("%d", t + n + i);

并使用 build() 仅填充另一个节点

线段树构建方法

segment tree building method

c++

segment-tree