Range Sum Query 2D - Immutable

#1

Hello, I am trying to code up with the implementation of the following question from Leetcode:

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

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:
Given 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) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.

Is there way you can add a section on 2D segment trees. First time asking doubt, PLMK what is the best way to work on this problem.

#2

@brookedutta,
There are no updates, so you don’t need segment or Fenwick tree. You can just do it by prefix arrays.

#3

Hello Abhijeet,

Thanks for shedding some light. Much appreciated. I did lookup on the Leetcode Discussions and it seemed like folks were suggesting solutions without naming the algorithm. It helps to get a name associated with it.

Are there any pointers to CodingBlocks lectures on Prefix arrays? Either this course or any other (ideally Java-based course).

Thanks.

#4

@brookedutta,
You don’t need a course just for learning prefix arrays. Just google it.

#5

Thanks for your KIND words and yes by now, I have figured that out as well - as suggested - by Googling!

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.