Range Sum Query 2D - Immutable - Video Solutions

Problem Overview: You receive a 2D matrix and must repeatedly return the sum of elements inside a rectangular region defined by (row1, col1) and (row2, col2). The matrix never changes, but the number of queries can be large. A naive sum per query is too slow, so the goal is to preprocess the matrix so each query runs in constant time.

Approach 1: Using 2D Prefix Sum (Preprocessing O(m*n), Query O(1))

This approach builds a cumulative sum matrix where each cell stores the total of all elements from the top-left corner to that position. During preprocessing, iterate through the matrix and compute prefix[i][j] using values from the top, left, and top-left diagonal. Once built, any submatrix sum can be computed using the inclusion–exclusion principle: subtract the extra regions above and left, then add back the overlapping corner. Query computation becomes a few constant-time arithmetic operations. Time complexity is O(m*n) to build the prefix matrix and O(1) per query, with O(m*n) extra space. This technique is a standard extension of prefix sum applied to a matrix and works well when the matrix is immutable and queries are frequent.

Approach 2: 2D Fenwick Tree (Binary Indexed Tree) (Update O(log m * log n), Query O(log m * log n))

A 2D Fenwick Tree stores partial sums in a structured tree-like array that supports efficient region queries. Each update propagates through index ranges using bit manipulation, and prefix sums are computed by traversing parent nodes. A rectangular sum query is derived by combining four prefix queries, similar to the prefix-sum inclusion–exclusion formula. Query and update operations both run in O(log m * log n) time with O(m*n) space. Even though the original problem is immutable, this structure becomes valuable if the matrix supports updates. It relies on concepts from array indexing and tree-based cumulative structures.

Recommended for interviews: The expected solution is the 2D Prefix Sum approach. Interviewers want to see that you recognize repeated range queries and convert them into a preprocessing problem. Building the prefix matrix shows understanding of cumulative sums and inclusion–exclusion logic. Mentioning a 2D Fenwick Tree demonstrates deeper knowledge of data structures for mutable range queries, but implementing it is usually unnecessary unless updates are part of the problem.