Idempotent Operations

The overlap trick works for idempotent operations: $f(a, a) = a$.

Idempotent:

• $\min$: $\min(a, a) = a$ ✓
• $\max$: $\max(a, a) = a$ ✓
• $\gcd$: $\gcd(a, a) = a$ ✓
• Bitwise AND: $a \land a = a$ ✓
• Bitwise OR: $a \lor a = a$ ✓

NOT idempotent:

• Sum: $a + a = 2a \neq a$ ✗
• Product: $a \cdot a = a^2 \neq a$ ✗
• XOR: $a \oplus a = 0 \neq a$ ✗
• Count: overlapping counts twice ✗ For non-idempotent operations, you can still use Sparse Table, but queries become $O(\log n)$ because you must use non-overlapping ranges. Idempotent query: $O(1)$. Non-idempotent query: $O(\log n)$. Space: $O(n \log n)$.