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, for min, for max, 1 for product.
Same complexity for all operations.