Given a m x n grid, how many unique sub-rectangles exist on such a grid?
For example,
1 x 1 grid has 1 sub-rectangle.
1 x 2 grid has 3 sub-rectangles.
I am looking for a general formula that can be used to directly compute the number existing sub-rectangle.
The answer is m(m+1)n(n+1)/4.
a rectangle is defined by its two projections on the x-axis and on the y-axis.
projection on x-axis : number of pairs (a,b) such that 1 <= a <= b <= m = m(m+1)/2
idem for y-axis