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\le j\}$ using prefix sums. Thenand the answer is zero if $c\ge 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.