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.

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

1 Answer 1


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.


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]] ++


(assumes i,j are both inclusive bounds)

if i == 0
  return count[j][m]
  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.


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.