Count distinct values in . Wavelet trees don't directly support this efficiently. Approach 1: Offline with sweepline Sort queries by right endpoint.
Use BIT to track "last occurrence" of each value. Approach 2: Persistent segment tree Build on value positions.
Query counts values whose last occurrence is in . Approach 3: Mo's algorithm Maintain frequency map while processing queries in Mo's order.
Distinct count in per query requires persistent structures. Wavelet tree helps with frequency queries but not distinct counts directly.