The overlap trick works for idempotent operations: .
Idempotent:
- : ✓
- : ✓
- : ✓
- Bitwise AND: ✓
- Bitwise OR: ✓
NOT idempotent:
- Sum: ✗
- Product: ✗
- XOR: ✗
- Count: overlapping counts twice ✗ For non-idempotent operations, you can still use Sparse Table, but queries become because you must use non-overlapping ranges. Idempotent query: . Non-idempotent query: . Space: .