# 2536. Increment Submatrices by One
###### tags: `Leetcode` `Medium` `Line Sweep`
Link: https://leetcode.com/problems/increment-submatrices-by-one/description/
## 思路
思路参考[这里](https://leetcode.com/problems/increment-submatrices-by-one/solutions/3052675/python3-sweep-line-range-addition-with-visualization-clean-concise/)
### 思路一 $O(qn+n^2)$
对于每一个query给涉及的每一行都标上+-1
### 思路二 $O(q+n^2)$
2D Line Sweep
左上角+1 右上角-1 左下角-1 右下角+1
然后先sweep line on rows再sweep line on columns
## Code
### 思路一

class Solution:
    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
        ans = [[0]*n for _ in range(n)]
        for r1, c1, r2, c2 in queries:
            for r in range(r1, r2+1):
                ans[r][c1] += 1
                if c2+1<n: ans[r][c2+1] -= 1
        for r in range(n):
            for c in range(1, n):
                ans[r][c] += ans[r][c-1]
        return ans

### 思路二

class Solution:
    def rangeAddQueries(self, n: int, queries: List[List[int]]) -> List[List[int]]:
        ans = [[0]*n for _ in range(n)]
        for r1, c1, r2, c2 in queries:
            ans[r1][c1] += 1
            if r2+1<n: ans[r2+1][c1] -= 1
            if c2+1<n: ans[r1][c2+1] -= 1
            if r2+1<n and c2+1<n: ans[r2+1][c2+1] += 1
        for r in range(n):
            for c in range(1, n):
                ans[r][c] += ans[r][c-1]
        for c in range(n):
            for r in range(1, n):
                ans[r][c] += ans[r-1][c]
        return ans