# Preprocess an array for counting an element in a slice (reduction to RMQ?)

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.

• You can reduce element distinctness to your problem (in linear time). Perhaps talking about a model is in order? – Aryabhata May 18 '12 at 22:55
• @Aryabhata what's exactly element distinctness problem? Now I'm reading this: en.wikipedia.org/wiki/Range_Queries – andy May 18 '12 at 23:01
• 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. – Tsuyoshi Ito May 18 '12 at 23:15
• @Aryabhata: The reduction which I think you are talking about does not work because k is a constant in this problem. – Tsuyoshi Ito May 18 '12 at 23:18
• 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. – Tsuyoshi Ito May 19 '12 at 0:10

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.