Let $U=\{1,\ldots, u\}$ be a universe of elements for some $u\in \mathbb N$. Given some $n\in\mathbb N$, we are interested in computing some function $f:U^{\le n}\to\mathbb R$ over range queries.
In the Range Query problem we get an integer array $A[1,\ldots,n]\in U^n$ and wish to compute queries that takes as input parameters $1\le i\le j\le n$ and return $f(A[i,\ldots,j])$.
Consider the function $f$ that returns the number of distinct elements in the queried range.
The goal is to preprocess the input array $A$ and create a small summary that allows efficient computation of these distinct queries.
What is the best known algorithm for the problem? (given a memory bound $m$, what is the minimal query time that is required).
.
If we allow approximation of the number of distinct elements, can we get faster queries?
EDIT: I have found a related problem discussed in stackoverflow. The answer there shows a $O(n\log n\log u)$ bits algorithm that answers queries in $O(\log n)$ time.
Is this optimal?
Can we get better time/space bounds if we allow approximation?