// Implement an object that preprocesses an array of N integers in range 0..K-1 each

// and then is able to answer how many elements fall within the given range rMin..rMax(inclusively).

// The preprocessing can take O(K) memory (kept for later use) and O(N+K) time. 

// After preprocessing, each range request should take O(1) time.

using System;

using System.Diagnostics;

public class RangeCalculator

{

    private int[] countSmaller; // countSmaller[k] contains number of values less than k

    // O(K)

    public RangeCalculator(int K)

    {

        countSmaller = new int[K+1];    // initialized to 0 by C#

    }

    // O(N + K)

    public void preprocess(int[] a)

    {

        int [] count = new int[countSmaller.Length-1];  // initialized to 0 by C#

        foreach(int k in a)

        {

            Trace.Assert(0 <= k && k < count.Length);

            count[k]++;

        }

​

        countSmaller[0] = 0;

        // Invariant: for k=0..i-1 countSmaller[k] is the number of elements less than k

        for(int i = 1; i < countSmaller.Length; i++)

        {

            countSmaller[i] = count[i-1] + countSmaller[i-1];

        }

    }

    // O(1)

    public int countInRange(int rMin, int rMax)

    {

        return countSmaller[rMax+1] - countSmaller[rMin];

    }

}

​

public class Program

{

    public static void Main()

    {   

        int [] a = new []{ 0, 12, 0, 1, 4, 4, 15, 0};

        Test(a, 16, 0, 0);

        Test(a, 16, 15, 15);

        Test(a, 16, 0, 15);

        Test(a, 16, 0, 9);

        Test(a, 16, 3, 13);

    }

    public static void Test(int[] a, int k, int rmin, int rmax)

    {

        RangeCalculator range = new RangeCalculator(k);

        range.preprocess(a);

        int n = range.countInRange(rmin, rmax);

        Console.WriteLine("Sequence ({0}) has {1} values in range {2}..{3}", string.Join(" ", a), n, rmin, rmax);

    }

}