Application: Distinct Count

Count distinct values in $A[l..r]$. 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 $[l, r]$. Approach 3: Mo's algorithm Maintain frequency map while processing queries in Mo's order.

Distinct count in $O(\log n)$ per query requires persistent structures. Wavelet tree helps with frequency queries but not distinct counts directly.