Generate prefix sum of the matrix
vector < vector < int > > prefsum ( n , vector < int > ( m ) ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int x = 0 ; x < m ; x ++ ) { if ( x == 0 ) prefsum [ i ] [ x ] = grid [ i ] [ x ] ; else prefsum [ i ] [ x ] = prefsum [ i ] [ x - 1 ] + grid [ i ] [ x ] ; } }