public class Kyselytesti {
    private static final int N = 1000000;
    private static final int M = 50000;
    private static final int A = (int)Math.sqrt(N)+1;

    private static int[] taulu = new int[N];
    private static int[][] kysely = new int[M][2];
    private static int[] summa = new int[N];
    private static int[] vali = new int[A];

    private static void alusta() {
        for (int i = 0; i < N; i++) {
            taulu[i] = (int)(Math.random()*100);
            if (i > 0) summa[i] = summa[i-1];
            summa[i] += taulu[i];
            vali[i/A] += taulu[i];
        }
        for (int i = 0; i < M; i++) {
            int alku = (int)(Math.random()*N);
            int loppu = (int)(Math.random()*N);
            if (alku < loppu) {
                kysely[i][0] = alku;
                kysely[i][1] = loppu;
            } else {
                kysely[i][1] = alku;
                kysely[i][0] = loppu;
            }
        }
    }

    private static int kysely1(int alku, int loppu) {
        int tulos = 0;
        for (int i = alku; i <= loppu; i++) {
            tulos += taulu[i];
        }
        return tulos;
    }

    private static int kysely2(int alku, int loppu) {
        int tulos = summa[loppu];
        if (alku > 0) tulos -= summa[alku-1];
        return tulos;
    }

    private static int kysely3(int alku, int loppu) {
        int tulos = 0;
        for (int i = alku; i <= loppu; i++) {
            if (i%A == 0 && i+A-1 <= loppu) {
                tulos += vali[i/A];
                i += A-1;
            } else {
                tulos += taulu[i];
            }
        }
        return tulos;
    }

    private static void testi1() {
        long alku = System.currentTimeMillis();
        for (int i = 0; i < M; i++) {
            kysely1(kysely[i][0], kysely[i][1]);
        }
        long loppu = System.currentTimeMillis();
        System.out.println("Testi 1: " + (loppu-alku) + " ms");
    }

    private static void testi2() {
        long alku = System.currentTimeMillis();
        for (int i = 0; i < M; i++) {
            kysely2(kysely[i][0], kysely[i][1]);
        }
        long loppu = System.currentTimeMillis();
        System.out.println("Testi 2: " + (loppu-alku) + " ms");
    }

    private static void testi3() {
        long alku = System.currentTimeMillis();
        for (int i = 0; i < M; i++) {
            kysely3(kysely[i][0], kysely[i][1]);
        }
        long loppu = System.currentTimeMillis();
        System.out.println("Testi 3: " + (loppu-alku) + " ms");
    }

    public static void main(String[] args) {
        alusta();
        testi1();
        testi2();
        testi3();
    }
}