[Solved]: Preprocess an array for counting an element in a slice (reduction to RMQ?)

Problem Detail: 

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.}

Asked By : andy

Answered By : Goldy

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1918

 Ask a Question

 Download Related Notes/Documents