Precomputing the number of 1 s
int ones [ R + 1 ] [ C + 1 ] = { 0 } ; for ( int i = 1 ; i <= R ; i ++ ) for ( int j = 1 ; j <= C ; j ++ ) ones [ i ] [ j ] = ones [ i - 1 ] [ j ] + ones [ i ] [ j - 1 ] - ones [ i - 1 ] [ j - 1 ] + ( mat [ i - 1 ] [ j - 1 ] == 1 ) ;