A concise explanation of Pre-calculation


  • 0
    K

    Using the same example as the question's:

    image

    separate it into four parts based on the given rectangle:

    a = (3,5)
    b = (0,1,4,
         6,3,2)
    c = (1,4,1)
    d = (2,0,1,
         1,0,1,
         0,3,0)
    

    "d" is what we need to calculate here, so let's make it forward:

    A = a = sumRegion(0,0, row1 - 1, col1 - 1)
    B = a + b = sumRegion(0,0, row1 - 1, col2)
    C = a + c = sumRegion(0,0, row2, col1 - 1)
    D = a + b + c + d = sumRegion(0,0, row2, col2)
    

    so it's easy to get this: d = (A+D) - (B+C)

    The rest is that how to calculate A, B, C and D.

    Yes, just for-loop one time the matrix, we can get them.


  • 2

    I don't quite think of it like your a, b, c, d but like this:

    enter image description here


  • 0

    I think you should also draw a paint to explain how to get the sum of the blue and red rectangles.


  • 0
    K

    The diagram is the same as the equation: d = (A+D) - (B+C), my "a, b, c, d" just hep to reach that. But yes, your diagram is more concise.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.