// 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.

// The preprocessing can take O(N+K) memory and O(N+K) time. After preprocessing,

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

using System;

public class Program

{

    public static void Main()

    {

        int[] t = new []{ 0, 0, 1, 2, 3, 7, 15, 15, 20 };

        RangeCalculator calc = new RangeCalculator();

        calc.preprocess(t);

        Test(calc, -1, -1);

        Test(calc, -10, 0);

        Test(calc, 0, 0);

        Test(calc, 0, 1);

        Test(calc, 0, 2);

        Test(calc, 1, 2);

        Test(calc, 3, 7);

        Test(calc, 7, 15);

        Test(calc, 0, 100);

    }

    private static void Test(RangeCalculator calc, int rmin, int rmax)

    {

        Console.WriteLine("{0} values in range {1}..{2}", calc.countInRange(rmin, rmax), rmin, rmax);

    }

    class RangeCalculator

    {

        const int K = 1000; // or pass it to constructor

        private int [] m_equalOrLess;

        // O(N+K)

        public void preprocess(int [] a)

        {

            m_equalOrLess = new int[K];

            foreach(int v in a)

            {

                m_equalOrLess[v]++;

            }

            // Invariant: 

            // for each v in range 0..n-1 m_equalOrLess[v] contains number of values

            // that are equal or less than v

            // for each v>=n m_equalOrLess[v] contains number of values that are equal to v

            for(int n = 1; n < m_equalOrLess.Length; n++)

            {

                m_equalOrLess[n] += m_equalOrLess[n-1];

            }

            // for each v, m_equalOrLess[v] contains number of preprocessed values that are v or less

        }

​

        // O(1)

        public int countInRange(int rMin, int rMax)

        {

            // we assume no values beyond 0..K-1 range

            if(rMax < 0)

                return 0;

            int nEqualOrLess = m_equalOrLess[Math.Min(rMax, K-1)];

            return rMin<=0 ? nEqualOrLess : nEqualOrLess - m_equalOrLess[rMin-1];

        }

    }

}