Range Sum Query 2D Immutable

Implement a class NumMatrix. It is built once from a rectangular grid of integers and then answers many rectangle-sum queries.

• NumMatrix(matrix): matrix is a list of rows, at least 1×1. Values may be negative. The grid never changes after construction.
• sum_region(r1, c1, r2, c2): return the sum of every matrix[r][c] with r1 <= r <= r2 and c1 <= c <= c2. Indexes are 0-based and inclusive, and always satisfy r1 <= r2, c1 <= c2 and lie inside the grid.

m = NumMatrix([[2, 0, -1],
               [4, 3,  5],
               [1, 1,  1]])
m.sum_region(0, 0, 1, 1)  # 9   (2 + 0 + 4 + 3)
m.sum_region(1, 1, 2, 2)  # 10  (3 + 5 + 1 + 1)
m.sum_region(0, 2, 2, 2)  # 5   (-1 + 5 + 1)

Constraints: up to 200×200 cells, up to 2·10^5 queries.

Every query must be O(1) after an O(rows × cols) setup. Summing the rectangle cell by cell, or row by row, fails the large test.