# 1314. Matrix Block Sum

[Link](https://leetcode.com/problems/matrix-block-sum/)

**Solution**

先求出rangeSum

```java
      int[][] rangeSum = new int[m+1][n+1];
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n ; j++){
                rangeSum[i][j] = rangeSum[i-1][j] + rangeSum[i][j-1] - rangeSum[i-1][j-1] + mat[i-1][j-1]; 
            }
        }
```

再透過rangeSum求出block sum

![](https://2628390332-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M0RnkuvOeqe0clAIN1b%2F-MGpN8UWLlWt2fPlnyn8%2F-MGuVIB_kXucKt3eUepk%2Fimage.png?alt=media\&token=3557d28c-19e2-434b-bcbb-d427429e6a16)

```java
      int[][] ans = new int[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                
                int r1 = Math.max(0, i-K);
                int r2 = Math.min(m-1, i+K);
                int c1 = Math.max(0, j-K);
                int c2 = Math.min(n-1, j+K);
                r1++;r2++;c1++;c2++; //rangeSum start from 1
                ans[i][j] = rangeSum[r2][c2] - rangeSum[r1-1][c2] - rangeSum[r2][c1-1] + rangeSum[r1-1][c1-1];
            }
        }
        return ans;
```
