Second Minimum Query

What if you need both the minimum AND second minimum in a range?

Store pairs at each position: $(\text{min}, \text{secondMin})$.

Merge function:

def merge(pair1, pair2):
    a, b = pair1  # min, secondMin from first range
    c, d = pair2  # min, secondMin from second range
    sorted_vals = sorted([a, b, c, d])
    return (sorted_vals[0], sorted_vals[1])

The merge here is NOT idempotent. Merging a pair with itself, like merge((3,5), (3,5)), gives (3,3) not (3,5). Because of this, you cannot use the overlapping-ranges trick. You need $O(\log n)$ queries instead, splitting the range into non-overlapping blocks.

Use case: problems needing the two smallest elements in a range, or detecting ties.