1
$\begingroup$

Given an array of N integers, there may be a need to perform q queries. A query could be like determining the number of values that are less than an integer k. Which data structure could be used to minimize Time Complexity?

My Thoughts:
One easy way could be to keep the numbers sorted. And then, for each query, we just have to do a binary search. I am not sure if this can be done easily using a prefix array, segment tree or suffix tree in some way

$\endgroup$
4
  • 1
    $\begingroup$ Is the structure static? That is you do not need to support insertions and deletions? Do you have a target running-time for the queries? $\endgroup$
    – Russel
    Sep 7, 2022 at 15:44
  • $\begingroup$ It works for this case. Now determine the sum of all values less than an integer k. Can you do that with a slightly more complicated data structure? And Russel's very important question: Is that array given once and fixed for all time, or can it change over time? $\endgroup$
    – gnasher729
    Sep 7, 2022 at 15:50
  • $\begingroup$ @Russel yes the array is fixed for all time $\endgroup$
    – nicku
    Sep 7, 2022 at 16:20
  • 1
    $\begingroup$ Why don't you want a sorted array ? $\endgroup$
    – user16034
    Sep 7, 2022 at 16:35

2 Answers 2

4
$\begingroup$

This operation is often called "rank", and there are many data structures that can implement it. It is often seen in the combination "rank/select", where "select" is the converse operation: for any k, it returns the kth smallest integer in the set.

These two operations are surprisingly general. For example, you don't strictly need a set membership query if you have a fast $\mathrm{rank}$ query, since $\mathrm{rank}(k+1) - \mathrm{rank}(k)$ is 1 if $k$ is an element of the set and 0 if it is not.

Binary search on a sorted list is certainly an option, and arguably the simplest one to implement. However, you can do much better, both in time usage and in space usage, by implementing an index for performing efficient rank queries.

I'll give one example of how you can do this, and then direct you to a good starting paper for more details.

We will suppose that the integers stored in the set are known to be in the range $[0,M)$ for some $M$. $M$ could, for example, be the largest element plus one.

Then you could represent the set as an $M$-element bit vector $\mathbf{b}$, with a set bit denoting membership (i.e. $b_i=1$ means $i$ is in the set).

Set $l$ to be the closest power of 2 to $\log^2 M$ and $s$ to be the closest power of 2 to $\frac{1}{2}\log M$. (All logarithms are base 2.) Using powers of 2 makes many of the following operations bit shifting and masking, and also ensures that $s$ divides evenly into $l$, which simplifies the analysis.

As an example, suppose $M = 2^{32}$, then $l = 1024$ and $s=16$.

The first part of the rank index is an array $R_l[0\ldots \frac{M}{l}]$, where $R_l[i]$ stores the number of elements in the set that are less than $i\cdot l$.

The second part of the rank index is an array $R_s[0\ldots \frac{M}{s}]$, where $R_s[i]$ stores the number of the elements in the set that are less than $i\cdot s$ but greater than or equal to $\left\lfloor \frac{is}{l} \right\rfloor$.

Then you can compute $\mathrm{rank}(k)$ by:

$$\mathrm{rank}(k) = R_l[\left\lfloor k / l\right\rfloor] + R_s[\left\lfloor k / s\right\rfloor] + \mathrm{popcount}(\left\lfloor k / s \right\rfloor \cdot s, k \bmod s)$$

Here, $\mathrm{popcount}(i, c)$ counts the number of set bits in the range $[i,i+c)$, by inspecting the bit vector. This may seem like it should take $O(l)$ time, but because $c < s$, and $s < \log M$, the number of bits you need to inspect is a constant number of machine words, and so it can be done in constant time. Most modern desktop-class CPUs have a popcount instruction built in, or failing that, you could use a small lookup table (say, of $2^8$ entries) and use bit shift/mask operations and a couple of table lookups to handle the example case of $s=16$.

Alternatively, you can implement popcount in $O(\log c) = O(\log \log M)$ time using clever bit arithmetic, but we will assume it takes $O(1)$ time.

In that case, the rank operation overall takes $O(1)$ time.

Now we consider the size of the index. The array $R_l$ has $M/l$ entries, and each entry uses $O(\log M)$ bits of storage. The array $R_s$ has $M/s$ entries, but each entry only requires $O(\log \log M)$ bits of storage. In total, the space usage in bits is:

$$O\left(\frac{M}{\log M}\right) + O\left(\frac{M \log \log M}{\log M}\right) = o(M)$$

That's little-oh of $M$ bits, compared to the bit vector itself which uses $M$ bits.

Index data structures which have this asymptotic space behaviour are referred to as "succinct". Succinct data structures are an important class of data structures because they get more efficient, in a relative sense, as you store more data.

Suppose that a data structure requires $f(M)$ bits of size; you might know this using an information theoretic argument, for example. Then:

  • A representation which uses $f(M) + O(1)$ bits is implicit.
  • A representation which uses $f(M) + O(f(M)) = (1 + O(1))f(M)$ bits is compact. So, for example, a data structure which always imposes a 1% overhead is a compact data structure.
  • A representation which uses $f(M) + o(f(M)) = (1 + o(1))f(M)$ bits is succinct. The absolute size of the overhead might grow quite large, but the relative overhead is $o(1)$, and so eventually becomes negligible as $M$ increases.

Now, of course, if $M$ is large but the number of elements in the set $K$ is relatively small (i.e. the bit vector is "sparse"), this may not be a practical implementation. However, an index which implements "rank on a bit vector" is a basic component in fancier variants which handle the sparse case; many of them essentially boil down to compressing the bit vector and then performing rank queries on the compressed form.

For further information, see:

A final word of caution before you go down this rabbit hole.

You defined the rank operation to be the number of elements in the set less than k. Some papers define it to be the number of elements less than or equal to k, including the paper I cited above. (Some papers also start counting at 1 instead of 0, which is even more confusing.)

The two conventions are equivalent, of course, but I recommend using your "less than" convention. Take it from someone who has implemented rank/select indexes, it makes everything slightly simpler. But it does mean that you may have to mentally translate some of the papers you read.

$\endgroup$
1
$\begingroup$

If the range of the integers is small then you can compute the histogram of the inputs then compute the prefix sum of this histogram. This preprocessing takes $O(n) $ time. Now given the prefix sum, you can now perform each query in $O(1)$ time.

If the range of the integers is large compared to $N$, then your idea of presorting and then binary search for each query should suffice. You will get an $O( n \log n) $ preprocessing and $O(\log n) $ query.

$\endgroup$
2
  • $\begingroup$ If the size of the range is $r$, the preprocessing takes $O(r)$ time and space. $\endgroup$
    – user16034
    Sep 7, 2022 at 16:54
  • $\begingroup$ This is true, I am actually assuming here that small means $r = O(n) $. And I think its a good to point out that the first solution requires extra space. $\endgroup$
    – Russel
    Sep 7, 2022 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.