Time complexiity

#1

please explain how to achieve the sum:

We have an integer array of size NxM.

We need to answer Q queries each of the form (x1, y1, x2, y2) and you should output the sum of the rectangular region described by the top left cell (x1,y1) and the bottom right cell described by (x2, y2). There may also be point updates.

Solve this using 2D fenwick tree, BIT[i][j] stores sum of the rectangular region (i - LSOne(i), j - LSOne(j), i ,j).

What is the optimal time complexity for answering each query?

#2

@kumar_sunny,

image
image674×504 26.4 KB

Here, query(i,j) gives sum of rectangle {(1,1),(i,j)}.

#3

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.