Function to add k to the specified submatrix ( r1 , c1 ) to ( r2 , c2 )
void update ( int D [ N ] [ M + 1 ] , int k , int r1 , int c1 , int r2 , int c2 ) { for ( int i = r1 ; i <= r2 ; i ++ ) { D [ i ] [ c1 ] += k ; D [ i ] [ c2 + 1 ] -= k ; } }