CLRS Solutions | Exercise 8.2-4 | Sorting in Linear Time

Describe an algorithm that, given $n$ integers in the range 0 to $k$, preprocesses its input and then answers any query about how many of the $n$ integers fall into a range $[a \mathinner{.\,.} b]$ in $O(1)$ time. Your algorithm should use $\Theta(n + k)$ preprocessing time.

The key insight is to use the counting array from counting sort, but keep it in its cumulative form.

Think of a simpler problem first: how many numbers are $\leq b$? If we have a cumulative count array, this is just one lookup. Similarly, how many are $\leq a - 1$? Another lookup. The difference gives us the count in range $[a \mathinner{.\,.} b]$.

$$\textsc{Preprocess}(A, k)$$$$\begin{aligned} 1& \quad \text{let}\,C[0..k]\,\text{be}\,a\,\text{new}\,\text{array} \\ 2& \quad \textbf{for }\,i\,=\,0\textbf{ to }\,k \\ 3& \quad \qquad C[i]\,=\,0 \\ 4& \quad \textbf{for }\,j\,=\,1\textbf{ to }\,A.length \\ 5& \quad \qquad C[A[j]]\,=\,C[A[j]]\,+\,1 \\ 6& \quad \textbf{for }\,i\,=\,1\textbf{ to }\,k \\ 7& \quad \qquad C[i]\,=\,C[i]\,+\,C[i - 1] \\ 8& \quad \textbf{return }\,C \\ \end{aligned}$$

After preprocessing, $C[i]$ contains the number of elements in $A$ with value $\leq i$.

$$\textsc{RangeQuery}(C, a, b)$$$$\begin{aligned} 1& \quad \textbf{if }\,a\,=\,0 \\ 2& \quad \qquad \textbf{return }\,C[b] \\ 3& \quad \textbf{else }\textbf{ return }\,C[b]\,-\,C[a - 1] \\ \end{aligned}$$

The number of elements in range $[a \mathinner{.\,.} b]$ equals the number of elements $\leq b$ minus the number of elements $\leq a - 1$.

As an example, suppose $A = \langle 2, 5, 3, 0, 2, 3, 0, 3 \rangle$ with $k = 5$.

After counting: $C = [2, 0, 2, 3, 0, 1]$

After cumulative sum: $C = [2, 2, 4, 7, 7, 8]$

Query $[2 \mathinner{.\,.} 3]$: $C[3] - C[1] = 7 - 2 = 5$

Indeed, values 2, 2, 3, 3, 3 are in range $[2 \mathinner{.\,.} 3]$.