segment tree building method

Question

Hi i am learning segment tree. Buildilding the segment tree using the recursive methodis clear to me , i have implemented it like this:

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] ;
}

but i have seen a shoter implementation like this :

    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]

but how does that logic help i building the segment tree?? a simple example would be very helpful

Answer 1

Actually there is a different "function" of build() in your code and their code. In your code, when you build the segment tree you also input the leaves value, but in their code, they input the leaves value in this statement:

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

and use build() to only fill the other node