/*
 * Intervalli.java - questo programma risolve il problema 4.9 p. 116
 * di Demetrescu, Finocchi, Italiano, "Algoritmi e strutture dati"
 * (seconda edizione), McGraw-Hill, 2008.
 *
 * Descrivere un algoritmo che dato un array A di n numeri interi,
 * tutti compresi nell'intervallo [1,k], preprocessa l'array in tempo
 * O(n+k) in modo da generare una opportuna struttura dati che
 * consenta di rispondere in tempo O(1) a query del tipo: ``quanti
 * elementi di $A$ sono compresi nell'intervallo [a,b]?''  (per
 * qualsiasi $1 \leq a \leq b \leq k$)
 *
 * Version 0.1 del 2009/11/09
 * Autore: Moreno Marzolla (marzolla (at) cs.unibo.it)
 *
 * This file has been released by the author in the Public Domain
 */
public class Intervalli {

    int sum[]; // sum[i] e' il numero di elementi di A che sono minori
               // o uguali di i, i=1,2,...k. sum[0] vale zero
    int k;

    /**
     * Preprocessa l'array A[] (che puo' contenere esclusivamente
     * valori interi compresi nell'intervallo [1,...k]) in modo da
     * poter poi rispondere in tempo O(1).
     *
     * Questo metodo ha complessit' Theta(n+k), essendo n il numero di
     * elementi in A[].
     */
    public Intervalli( int A[], int k )
    {
	this.k = k;
	int i;
	sum = new int[k+1];
	// Initializza sum[] a zero
	for ( i=0; i<k+1; ++i )
	    sum[i] = 0;
	// Calcola i valori si sum[] iterando una sola volta sull'array A[]
	for ( i=0; i<A.length; ++i ) {
	    sum[A[i]]++;
	}
	// Calcola le somme
	for ( i=1; i<k+1; ++i ) {
	    sum[i] = sum[i-1]+sum[i];
	}
    }

    /**
     * Restituisce il numero di elementi di A[] compresi tra a e b
     * (estremi inclusi). Questo metodo ha complessit' O(1).
     */
    public int conta( int a, int b )
    {
	// si assume che 1 <= a <= b <= k
	return (sum[b] - sum[a-1]);
    }

    public static void main( String args[] )
    {
	int A[] = {1, 2, 3, 1, 3, 2, 2, 4, 2, 3, 1, 3, 2, 2, 4, 1, 1, 1, 2};
	Intervalli interv = new Intervalli(A,4);
	System.out.println("Numero elementi in [1,2] = " + interv.conta(1,2));
	System.out.println("Numero elementi in [2,3] = " + interv.conta(2,3));
	System.out.println("Numero elementi in [3,4] = " + interv.conta(3,4));
    }
}