Process to build a segment tree

segment_tree_build.cpp

// [left, right] => range spanned by current node
void build(int id, int left, int right) { // O (n)
   if (left == right) {
       // when we divide and conquer on the middle element, left and right becomes equal when we reach the leaf nodes
       tree[id]  = arr[left];
       return;
   }
   int mid = (left + right)/2;
   // build left child first
   build(2 * id, left, mid);
   // build right child next
   build(2 * id + 1, mid + 1, right);
   // current node sum is available from sum of left and right child
   tree[id] = tree[id * 2] + tree[id * 2 + 1];
}