We are given a matrix M of dimension N*N. All the cells are initially, zero. Also we are given Q queries, which contains 4 integers a b c d. where (a,b) is the TOP LEFT cell and (c,d) is the Bottom Right cell of a submatrix. Now, all the cells of This submatrix has to be incremented by one. After all the Q queries have been performed. Your task is to print the final resulting Matrix.
I know the 1-D version of this problem. But I'm having difficulties implementing it in 2-D form. Any inputs regarding the same?
What r the constraint? I am not getting anything less than O(QN). Using prefix sum for each row.
$$$O(Q+N^2)$$$ is possible as the linked solution shows.
solution
i hope this helps you
I dont get why have we incremented at position mat[x2+1][y2+1]?
Mat[x1][y1]++; will increase from (x1,y1) => (n,n)
Mat[x1][y2+1]--; will stop the increasing after column y2 So now from (x1,y1)=> (n,y2) will only be increased
Mat[x2+1][y1]--; will stop the increasing after row x2 So now from (x1,y1) => (x2,n) will only be increased.
But notice The rows after x2 got columns from y2+1 => n Which we already decreased from step 2
And the columns after y2 got rows from x2+1 =>n Which we decreased from step 3
So as you notice that the sub-rectangle (X2+1,y2+1) => (n,n) Will be decreased twice
So we add mat[x2+1][y2+1]++;
If you still having trouble Try drawing this test 5 1 2 2 4 4