Range Count of Ones in a Binary Matrix (Immutable)

You are given an immutable R x C binary matrix M (only 0/1). You must support many queries. Each query provides the top-left corner (r1, c1) and bottom-right corner (r2, c2) (inclusive, with 0 <= r1 <= r2 < R, 0 <= c1 <= c2 < C) and you should return the number of 1s in that sub-rectangle. Requirements: Matrix is immutable. For many queries, each query should be as fast as possible. Constraints (for complexity goals): 1 <= R, C <= 3000 (or larger) Number of queries Q can be large (e.g., 10^5) Example matrix: 1 0 1 0 1 0 1 1 1 Query (0,0) to (1,1) -> 2 Explain preprocessing and query complexity, and implement the interface. Provide at least 5 test cases including edge cases. Example Input M=[[1,0,1],[0,1,0],[1,1,1]] q=1 0 0 1 1 Output 2