Preprocessing to calculate sum from i to j
for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < matrix [ i ] . size ( ) ; j ++ ) { matrix [ i ] [ j ] = ( j > 0 ? matrix [ i ] [ j - 1 ] : 0 ) + matrix [ i ] [ j ] ; } } }