public class Summa2D {
    public static final int N = 1000;
    public static int[][] taulu = new int[N][N];
    public static int[][] summa = new int[N][N];

    public static void arvoSisalto() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                taulu[i][j] = (int)(Math.random()*100);
            }
        }
    }

    public static void laskeSummat() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                summa[i][j] = taulu[i][j];
                if (i > 0) summa[i][j] += summa[i-1][j];
                if (j > 0) summa[i][j] += summa[i][j-1];
                if (i > 0 && j > 0) summa[i][j] -= summa[i-1][j-1];
            }
        }
    }

    public static int kysely(int y1, int x1, int y2, int x2) {
        int tulos = summa[y2][x2];
        if (y1 > 0) tulos -= summa[y1-1][x2];
        if (x1 > 0) tulos -= summa[y2][x1-1];
        if (y1 > 0 && x1 > 0) tulos += summa[y1-1][x1-1];
        return tulos;
    }

    public static int hidas(int y1, int x1, int y2, int x2) {
        int tulos = 0;
        for (int i = y1; i <= y2; i++) {
            for (int j = x1; j <= x2; j++) {
                tulos += taulu[i][j];
            }
        }
        return tulos;
    }

    public static void main(String[] args) {
        arvoSisalto();
        laskeSummat();
        // testataan toimivuus
        for (int i = 0; i < 10000; i++) {
            int y1 = (int)(Math.random()*1000);
            int x1 = (int)(Math.random()*1000);
            int y2 = (int)(Math.random()*1000);
            int x2 = (int)(Math.random()*1000);
            if (y1 > y2) {int t = y1; y1 = y2; y2 = t;}
            if (x1 > x2) {int t = x1; x1 = x2; x2 = t;}
            if (kysely(y1, x1, y2, x2) != hidas(y1, x1, y2, x2)) {
                System.out.println("Summataulukko ei toimi!");
            }
        }
    }
}