How many subrectangle exists on a m x n grid

Same answer as @Thomash provided, but with a bit more explanation, posting for posterity:

If you can figure this out in one dimension, it's easy to move it into two dimensions.

Let's look at a 1x5:

 5 1x1 squares
+4 1x2 squares
+3 1x3 squares
+2 1x4 squares
+1 1x5 squares = 15 squares.

The formula for this is simple: sum = n(1 + n)/ 2. In the case of 5, you want 5(1+5)/2 = 15.

So, to get your answer, just do this for n and m, and multiply them:

sumN = n(1+n)/2
sumM = m(1+m)/2
totalRectangles = nm(1+n)(1+m)/4

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

Tags:

Algorithm