Range Minimum Query

Change the merge operation from sum to min:

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] = min(tree[2*node], tree[2*node+1])

def query(node, start, end, l, r):
    if r < start or end < l:
        return float('inf') # identity for min
    if l <= start and end <= r:
        return tree[node]
    mid = (start + end) // 2
    return min(query(2*node, start, mid, l, r),
               query(2*node+1, mid+1, end, l, r))

The identity element changes: 0 for sum, $\infty$ for min, $-\infty$ for max, 1 for product.

Same $O(\log n)$ complexity for all operations.