 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2016/functional-programming-design-and-analysis-of-algorithms-resit/6/f/solution

Precompute the 26 cumulative counts

C [j] = # {i : a_{i} \leq j}

using prefix sums. Then

# {i : c < a_{i} \leq d} = C [d] - C [c] if c < d,

and the answer is zero if

c \geq d

. Counting and prefix summation take

O (n + 26) = O (n)

preprocessing time and constant storage for this fixed alphabet. Each query uses two indexed reads and one subtraction, hence

O (1)

time. The guard for

c > d

prevents a negative answer for an empty interval.

 New to topics? Read the docs here!