medium

Range Sum Query 2D — Immutable

Given an integer matrix that never changes, preprocess it so that many queries of the form "sum of the rectangle with corners (r1, c1) and (r2, c2)" can each be answered in constant time.

Constraints

1 ≤ m, n ≤ 200
-10^4 ≤ matrix[i][j] ≤ 10^4
Up to 10^4 queries

Examples

in: matrix = [[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]], sumRegion(2,1,4,3)

out: 8

Code it yourself

Solve in

Your python code

Test execution is not yet available for this exercise.Practice journal →Draft saved in this browser.

Hints:

Which approach applies?

Choose an approach to check your pattern recognition, or reveal the discussion when you need help.