package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/range-sum-query-2d-immutable/
 */
public class Problem304 {
    public static class NumMatrix {
        private final Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
        private int[][] matrix;

        public NumMatrix(int[][] matrix) {
            this.matrix = matrix;
            for (int row = 0; row < matrix.length; row++) {
                int[] nums = matrix[row];
                int sum = nums[0];
                Map<Integer, Integer> numMap = new HashMap<>();
                for (int col = 1; col < nums.length; col++) {
                    sum += nums[col];
                    numMap.put(col, sum);
                    map.put(row, numMap);
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            int sum = 0;
            for (int row = row1; row <= row2; row++) {
                int[] nums = matrix[row];
                if (col1 == col2) {
                    return nums[col1];
                }
                Integer a = map.get(row).get(col1);
                if (a == null) {
                    a = 0;
                }
                if (col1 > 0) {
                    a -= nums[col1];
                }
                Integer b = map.get(row).get(col2);
                if (b == null) {
                    b = 0;
                }
                sum += b - a;
            }
            return sum;
        }
    }

    public static void main(String[] args) {
        NumMatrix matrix = new NumMatrix(new int[][]{
            {3, 0, 1, 4, 2},
            {5, 6, 3, 2, 1},
            {1, 2, 0, 1, 5},
            {4, 1, 0, 1, 7},
            {1, 0, 3, 0, 5},
        });
        System.out.println(matrix.sumRegion(2, 1, 4, 3)); // 8
        System.out.println(matrix.sumRegion(1, 1, 2, 2)); // 11
        System.out.println(matrix.sumRegion(1, 2, 2, 4)); // 12
    }
}

@@ -16,57 +16,8 @@
 e;%0A%0A
-import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A
@@ -149,89 +149,8 @@
 x %7B%0A
-        private final Map%3CInteger, Map%3CInteger, Integer%3E%3E map = new HashMap%3C%3E();%0A
     
@@ -361,107 +361,8 @@
 w%5D;%0A
-                int sum = nums%5B0%5D;%0A                Map%3CInteger, Integer%3E numMap = new HashMap%3C%3E();%0A
     
@@ -439,21 +439,26 @@
         
-s
+n
 um
+s%5Bcol%5D
  
-+
 = nums%5Bc
@@ -464,92 +464,24 @@
 col%5D
-;%0A                    numMap.put(col, sum);%0A                    map.put(row, numMap)
+ + nums%5Bcol - 1%5D
 ;%0A  
@@ -743,15 +743,16 @@
 ol1 
-== col2
+- 1 %3E= 0
 ) %7B%0A
@@ -771,22 +771,22 @@
         
-return
+sum +=
  nums%5Bco
@@ -790,908 +790,158 @@
 %5Bcol
-1%5D;%0A                %7D%0A                Integer a = map.get(row).get(col1);%0A                if (a == null) %7B%0A                    a = 0;%0A                %7D%0A                if (col1 %3E 0) %7B%0A                    a -= nums%5Bcol1%5D;%0A                %7D%0A                Integer b = map.get(row).get(col2);%0A                if (b == null) %7B%0A                    b = 0;%0A                %7D%0A                sum += b - a;%0A            %7D%0A            return sum;%0A        %7D%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        NumMatrix matrix = new NumMatrix(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        System.out.println(matrix.sumRegion(2, 1, 4, 3)); // 8%0A        System.out.println(matrix.sumRegion(1, 1, 2, 2)); // 11%0A        System.out.println(matrix.sumRegion(1, 2, 2, 4)); // 12
+2%5D - nums%5Bcol1 - 1%5D;%0A                %7D else %7B%0A                    sum += nums%5Bcol2%5D;%0A                %7D%0A            %7D%0A            return sum;%0A        %7D
 %0A   

Solve problem 304