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