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$
  • $\begingroup$ You can reduce element distinctness to your problem (in linear time). Perhaps talking about a model is in order? $\endgroup$ – Aryabhata May 18 '12 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 '12 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$ – Tsuyoshi Ito May 18 '12 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$ – Tsuyoshi Ito May 18 '12 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$ – Tsuyoshi Ito May 19 '12 at 0:10
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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