@@ -0,0 +1,2268 @@
+import org.junit.Test;%0Aimport org.junit.experimental.max.MaxCore;%0A%0Aimport static org.junit.Assert.assertEquals;%0A%0A/**%0A * https://leetcode.com/problems/range-sum-query-2d-immutable/%0A */%0Apublic class Solution %7B%0A%0A    @Test%0A    public void test() %7B%0A        int%5B%5D%5B%5D matrix = new int%5B%5D%5B%5D%7B%0A                %7B3, 0, 1, 4, 2%7D,%0A                %7B5, 6, 3, 2, 1%7D,%0A                %7B1, 2, 0, 1, 5%7D,%0A                %7B4, 1, 0, 1, 7%7D,%0A                %7B1, 0, 3, 0, 5%7D%0A        %7D;%0A%0A        NumMatrix numMatrix = new NumMatrix(matrix);%0A        assertEquals(8, numMatrix.sumRegion(2, 1, 4, 3));%0A        assertEquals(11, numMatrix.sumRegion(1, 1, 2, 2));%0A        assertEquals(12, numMatrix.sumRegion(1, 2, 2, 4));%0A    %7D%0A%0A    @Test%0A    public void testEmptyMatrix() %7B%0A        int%5B%5D%5B%5D matrix = new int%5B%5D%5B%5D%7B%7D;%0A        NumMatrix numMatrix = new NumMatrix(matrix);%0A        assertEquals(0, numMatrix.sumRegion(2, 1, 4, 3));%0A    %7D%0A%0A    public class NumMatrix %7B%0A        private int%5B%5D%5B%5D accumulations;%0A        private int height;%0A        private int width;%0A%0A        public NumMatrix(int%5B%5D%5B%5D matrix) %7B%0A            this.height = matrix.length;%0A            this.width = height == 0 ? 0 : matrix%5B0%5D.length;%0A            this.accumulations = new int%5Bheight + 1%5D%5Bwidth + 1%5D;%0A%0A            for (int c = 0; c %3C width + 1; c++) %7B%0A                accumulations%5B0%5D%5Bc%5D = 0;%0A            %7D%0A            for (int r = 1; r %3C height + 1; r++) %7B%0A                accumulations%5Br%5D%5B0%5D = 0;%0A                for (int c = 1; c %3C width + 1; c++) %7B%0A                    accumulations%5Br%5D%5Bc%5D = accumulations%5Br%5D%5Bc - 1%5D +%0A                            accumulations%5Br - 1%5D%5Bc%5D -%0A                            accumulations%5Br - 1%5D%5Bc - 1%5D +%0A                            matrix%5Br - 1%5D%5Bc - 1%5D;%0A                %7D%0A            %7D%0A        %7D%0A%0A        public int sumRegion(int row1, int col1, int row2, int col2) %7B%0A            int sumTop = accumulations%5BMath.min(height, row1)%5D%5BMath.min(width, col2 + 1)%5D;%0A            int sumLeft = accumulations%5BMath.min(height, row2 + 1)%5D%5BMath.min(width, col1)%5D;%0A            int sumTopLeft = accumulations%5BMath.min(height, row1)%5D%5BMath.min(width, col1)%5D;%0A            int sum = accumulations%5BMath.min(height, row2 + 1)%5D%5BMath.min(width, col2 + 1)%5D;%0A            return sum - sumTop - sumLeft + sumTopLeft;%0A        %7D%0A    %7D%0A%7D%0A

Range Sum Query 2D - Immutable