Building the Tree

Build recursively: base case is a leaf (single element), recursive case combines children.

def build(arr, node, start, end):
    if start == end:
        tree[node] = arr[start]
    else:
        mid = (start + end) // 2
        build(arr, 2*node, start, mid)
        build(arr, 2*node+1, mid+1, end)
        tree[node] = tree[2*node] + tree[2*node+1]

Call with build(arr, 1, 0, n-1).

Time complexity: $O(n)$. You visit each of the $O(n)$ nodes exactly once.

Space complexity: $O(n)$ for the tree array.

The merge operation (here, addition) defines what the tree computes. Change + to min for range minimum queries.