<p>Given a <code>m * n</code> matrix of ones and zeros, return how many <strong>square</strong> submatrices have all ones.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> matrix =
[
&nbsp; [0,1,1,1],
&nbsp; [1,1,1,1],
&nbsp; [0,1,1,1]
]
<strong>Output:</strong> 15
<strong>Explanation:</strong> 
There are <strong>10</strong> squares of side 1.
There are <strong>4</strong> squares of side 2.
There is  <strong>1</strong> square of side 3.
Total number of squares = 10 + 4 + 1 = <strong>15</strong>.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
<strong>Output:</strong> 7
<strong>Explanation:</strong> 
There are <b>6</b> squares of side 1.  
There is <strong>1</strong> square of side 2. 
Total number of squares = 6 + 1 = <b>7</b>.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length&nbsp;&lt;= 300</code></li>
	<li><code>1 &lt;= arr[0].length&nbsp;&lt;= 300</code></li>
	<li><code>0 &lt;= arr[i][j] &lt;= 1</code></li>
</ul>

class Fenwick2D:
    def __init__(self, rows, cols):
        self.bit = [[0 for _ in range(cols+1)] for _ in range(rows+1)]
    
    def update(self, row, col, val):
        col += 1
        row += 1
        while row < len(self.bit):
            col_ = col
            while col_ < len(self.bit[0]):
                self.bit[row][col_] += val
                col_ += col_ & -col_
            row += row & -row

    def get(self, row, col):
        col += 1
        row += 1
        ans = 0
        while row > 0:
            col_ = col
            while col_ > 0:
                ans += self.bit[row][col_]
                col_ -= col_ & -col_
            row -= row & -row
        return ans

    def printNormalSum(self):
        for row in range(len(self.bit)):
            x = ""
            for col in range(len(self.bit[0])):
                x += f"{self.get(row-1, col-1)} "
            print(x)



class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        rows = len(matrix)
        cols = len(matrix[0])
        prefsum = [[0 for _ in range(cols)] for _ in range(rows)]

        for i in range(rows):
            for j in range(cols):
                prefsum[i][j] = matrix[i][j] - (prefsum[i-1][j-1] if i>=1 and j>=1 else 0) + (prefsum[i-1][j] if i >= 1 else 0) + (prefsum[i][j-1] if j >= 1 else 0)
            
        for i in prefsum:
            print(i)
        # fenwick.printNormalSum()
        mxsize = min(rows, cols)
        ans = 0
        for size in range(1, mxsize+1):
            for i in range(rows):
                for j in range(cols):
                    # considering this i and j is end, find what would be begin
                    beginx = i - size + 1
                    beginy = j - size + 1

                    if beginx >= 0 and beginy >= 0:
                        beforex = beginx - 1
                        beforey = beginy - 1

                        # sum till end
                        full = prefsum[i][j]
                        common = prefsum[beforex][beforey] if beforex >= 0 and beforey >= 0 else 0
                        upper = prefsum[beforex][j] if beforex >= 0 else 0
                        left = prefsum[i][beforey] if beforey >= 0 else 0

                        if full + common - upper - left >= size * size:
                            ans += 1
        return ans

21100