What is known about computing distinct count range queries?
A sketch data structure is an approximation of a set of elements. Sketches vary in what they store -- some store just hashes, some store elements from the set (a sample), and some store floating-point numbers.

This solution uses the sketch data structure from "A Minimal Variance Estimator for the Cardinality of Big Data Set Intersection", by Cohen et al. It stores $k$ hash values.

Let $I = 2nk/m$. Let $F[t] = \{A[1], A[2], \dots , A[tI]\}$ and $B[t] = \{A[n], A[n-1], \dots, A[n-tI]\}$.  Store the sketches for $F[1],  F[2], \dots, F[m/2k]$ and $B[1],  B[2], \dots, B[m/2k]$. That is a total of $m/k$ sketches, each of size $k$, using a total of $m$ words of space.

Let $r(x)$ denote the value of $x$ rounded to the nearest integer. To estimate the carnality of $\{A[i], \dots, A[j]\}$, estimate the cardinality of $F[r(j/I)] \bigcap B[r((n-i)/I)]$. The Cohen et al. paper describes how to do this in $\text{poly}(k)$ time. The variance of the estimate is a long formula in Corollary 2, combined with the error induced by only using $m/k$ samples, which is at most $4nk/m$.