11
$\begingroup$

Given an array $a_1,\ldots,a_n$ of natural numbers $\leq k$, where $k$ is a constant, I want to answer in $O(1)$ queries of the form: "how many times does $m$ appear in the array between indices $i$ and $j$"?

The array should be preprocessed in linear time. In particular I'd like to know if there's a reduction to Range Minimum Query.


This is equivalent to RMQ in the case where $k=1$ and you want to query the number of ones within an interval. So we can use it.
I couldn't answer my own question because of limits of SE.

$\endgroup$
8
  • $\begingroup$ You can reduce element distinctness to your problem (in linear time). Perhaps talking about a model is in order? $\endgroup$
    – Aryabhata
    May 18, 2012 at 22:55
  • $\begingroup$ @Aryabhata what's exactly element distinctness problem? Now I'm reading this: en.wikipedia.org/wiki/Range_Queries $\endgroup$
    – andy
    May 18, 2012 at 23:01
  • $\begingroup$ This is much easier than RMQ. Hint: Because k is a constant, preprocessing can spend time proportional to kn and it still counts as linear time. $\endgroup$ May 18, 2012 at 23:15
  • $\begingroup$ @Aryabhata: The reduction which I think you are talking about does not work because k is a constant in this problem. $\endgroup$ May 18, 2012 at 23:18
  • $\begingroup$ Just in case, if the array is given at the beginning and is not updated afterward, RMQ is an overkill, as I suggested in my earlier comment. $\endgroup$ May 19, 2012 at 0:10

1 Answer 1

4
$\begingroup$

Since $k$ is constant, we can store the count of each element in the range $0..m$ for $0\leq m \lt n$ in $0..n$ in $O(nk) = O(n)$ time and space. The primary observation is that you can make a two-dimensional array count[pos][elem] = occurences of 'elem' in the indices 0..pos in $O(nk)$ time, then query ranges by finding the difference in $i,j$ indices in constant time.

Preprocessing

initialise count[pos][elem] to 0 for all elem, pos
for pos=0 to n
  for num=0 to k
      count[pos][num] = (0 if pos==0 else count[pos-1][num])
  count[pos][arr[pos]] ++

Query

(assumes i,j are both inclusive bounds)

if i == 0
  return count[j][m]
else
  return count[j][m] - count[i-1][m]

If the array is also getting updated throughout the query process, you can use $k$ Fenwick (binary index) trees in place of the count array. This lets you update in $O(\log n)$ and query in $O(\log n)$.

Apologies for any issues with this answer, it's my first.

$\endgroup$

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .