Integral Image Rectangle Sum

Problem

Sum an inclusive rectangle using a precomputed integral image.

Given an integral image of shape (H + 1) x (W + 1), return the sum of the original rectangle from rows r1..r2 and columns c1..c2 inclusive using four lookups. You may assume valid indices with r1 <= r2 and c1 <= c2.

Hint

Inclusion-exclusion: bottom-right minus top band minus left band plus the top-left corner.

Test cases

case 1

in: [[[0,0,0,0],[0,1,3,6],[0,5,12,21],[0,12,27,45]],0,0,0,0]

expected: 1

case 2

in: [[[0,0,0,0],[0,1,3,6],[0,5,12,21],[0,12,27,45]],1,1,2,2]

expected: 28

case 3

in: [[[0,0,0,0],[0,1,3,6],[0,5,12,21],[0,12,27,45]],0,1,2,1]

expected: 15

case 4

in: [[[0,0,0,0],[0,1,3,6],[0,5,12,21],[0,12,27,45]],2,0,2,2]

expected: 24

Starter codePython

def rect_sum(integral, r1, c1, r2, c2):
    # Your code here
    pass

4 test cases · run your code against them in the editor