Problem - 2D Range Sum

Given a 2D matrix, handle multiple queries asking for the sum of elements inside a rectangle defined by its upper left corner $(row1, col1)$ and lower right corner $(row2, col2)$.

This extends the 1D prefix sum to two dimensions. The same trade-off applies: $O(nm)$ preprocessing for $O(1)$ queries. Read the problem. Notice there can be $10^4$ queries on a $200 \times 200$ matrix.