IMPLEMENT THE FOLLOWING ALGORITHM IN C#: PROVIDE A TEST AND PRINT THE OUTPUT

Given n integers in the range 0 to k-1, the algorithm preprocesses its input in O(n+k) time, then answers a query about how many of the n integers fall into a range[a.b ]in O(1)time:

The algorithm will begin by preprocessing count[i] containing the number of elements less than or equal to i in the array. When queried about how many integers fall into a range[a..b], simply compute count[b]?count[a?1]. This takes O(1) times and yields the desired output. See the structure below:

using System; public class RangeCalculator { //O(N+K) public void preprocess(int[] c) { // preprocess the array } //O(1) public int countInRange(int a, int b) { //return the number of elements } public static void Main(){ } }

The object might be used in the following way:

int K = 16;

int a[] = new a[]{ 0, 12, 0, 1, 4, 4, 15, 0, /* any list of numbers each in range 0..K-1 */};

RangeCalculator ranges = new RangeCalculator(K); // no timing requirements

ranges.preprocess(a); // can take up to O(a.Length + K)

Console.WriteLine("Number of zeroes in a = {0}", ranges.countInRange(0, 0)); // takes O(1)

Console.WriteLine("Number of elements less than 10 in a = {0}", ranges.countInRange(0, 9)); // takes O(1)

Console.WriteLine("Number of elements in range 3..13 in a = {0}", ranges.countInRange(3, 13)); // takes O(1)