Submatrix sum query

#1

Can someone please tell me, how can we approach the code for this?

#2

Hey @lakshay2311 are you having issue in preparing the prefix submatrix?

#3

Yes, and how can we input queries.

#4

Take a look at this implementation https://ide.codingblocks.com/s/184797.
And for queries ,you will simply need to take input for how many queries there are and then simply run a loop for accepting that many queries and using your formula that many times to compute the answer.

#5

why we are taking an aux matrix?

#6

aux matrix is the matrix in which we are precomputing the prefix sums of the matrix elements so that we can answer the queries in O(1) time. I would suggest you to dry run the code for a 3X3 matrix example to see how we are calculating it and how the formula is working.

#7

Okay. i got it thanks