4 / 5 Prefix Sums & Difference Arrays

Four Corners One Rectangle

A 2D prefix table P is built so that P[i][j] is the sum of the subrectangle from row 1, column 1 through row i, column j, with row 0 and column 0 all zeros.

P 0 1 2 3 4
0 0 0 0 0 0
1 0 3 4 8 9
2 0 8 18 24 31
3 0 13 26 37 52
4 0 22 42 62 80

The query rectangle equals the big corner rectangle minus two overlapping strips plus the doubly removed corner P[A][B] P[a-1][B] P[A][b-1] P[a-1][b-1] query rows a..A, cols b..B row 0, col 0 is the top-left origin of every prefix rectangle

What is the sum of the subrectangle covering rows 2 through 4 and columns 2 through 4?

A

25

B

52

C

49

D

46