I have a binary matrix of size M*N. I'm given K queries where each consists of given sub-matrix, with upper left coord (x1,y1) and lower right coord (x2,y2). My task is to find how many one's are in each submatrix. I should find the best solution in terms of time complexity.

How can I achieve that?

I suppose that I should somehow pre-calculate the matrix to I can then answer the queries in O(1) time. But I'm not really sure how to pre-calculate the matrix.

CodePudding user response：

Let C(x1, y1, x2, y2) be the number of ones in a sub-matrix with upper left coord (x1, y1) and lower right coord (x2, y2) (i.e. x2 >= x1 and y2 >= y1), and let (1, 1) be the upper-left corner of the MxN binary matrix. Then:

• If x1 > 1 and y1 > 1: C(x1, y1, x2, y2) = C(1, 1, x2, y2) - C(1, 1, x2, y1-1) - C(1, 1, x1-1, y2) C(1, 1, x1-1, y1-1)
• If x1 = 1 and y1 > 1: C(x1, y1, x2, y2) = C(1, 1, x2, y2) - C(1, 1, x2, y1-1)
• If x1 > 1 and y1 = 1: C(x1, y1, x2, y2) = C(1, 1, x2, y2) - C(1, 1, x1-1, y2)
• If x1 = 1 and y1 = 1: C(x1, y1, x2, y2) = C(1, 1, x2, y2)

If you precompute C(1, 1, x, y) for 1 <= x <= M and 1 <= y <= M in a O(MN) precomputation step, each query C(x1, y1, x2, y2) can be answered in O(1) time.