| 26 | } |
| 27 | |
| 28 | private static int[][] precomputeMatrix(int[][] matrix) { |
| 29 | int[][] sumMatrix = new int[matrix.length][matrix[0].length]; |
| 30 | for (int i = 0; i < matrix.length; i++) { |
| 31 | for (int j = 0; j < matrix[0].length; j++) { |
| 32 | if (i == 0 && j == 0) { // first cell |
| 33 | sumMatrix[i][j] = matrix[i][j]; |
| 34 | } else if (j == 0) { // cell in first column |
| 35 | sumMatrix[i][j] = sumMatrix[i - 1][j] + matrix[i][j]; |
| 36 | } else if (i == 0) { // cell in first row |
| 37 | sumMatrix[i][j] = sumMatrix[i][j - 1] + matrix[i][j]; |
| 38 | } else { |
| 39 | sumMatrix[i][j] = sumMatrix[i - 1][j] + |
| 40 | sumMatrix[i][j - 1] - sumMatrix[i - 1][j - 1] + |
| 41 | matrix[i][j]; |
| 42 | } |
| 43 | } |
| 44 | } |
| 45 | return sumMatrix; |
| 46 | } |
| 47 | |
| 48 | private static int computeSum(int[][] sumMatrix, int i1, int i2, |
| 49 | int j1, int j2) { |