We have a two-dimensional $n \times n$ array containing binary values binary ($0$ and $1$) where $0$ denotes a black pixel and $1$ a white pixel.
Enter the number of square areas (with the same number of columns and rows), in of which there are as many black pixels as white pixels. For example, found the $2 \times 2$ area should have two cells containing white and two pixels containing black pixels. However, a $10 \times 10$ area was correctly found should have $50$ white pixels and the same number of black ones. The program should provide for given array, the number of different square areas of any size for which the same number of cells containing 1 as the containing cells were found number $0$.
Calculate the computational complexity of two versions of the program:
not using the partial sum table
using a partial sum table created earlier
The partial sum table stores in the position (k, l) the sum of the analyzed elements array contained in cells (i, j) for which i<=n, j<=m (in cells located on left and top of the cell with the address (k, l)). Therefore, to determine the sum of S elements in In the rectangular area of the table, just refer to the four values from the sum table
partial parts according to the formula: S = D + A-B-C