Binary searching through the 2d array and only checking the range in which the sub array is a part
while ( $ lo + 1 < $ hi ) { $ mid = ( int ) ( ( $ lo + $ hi ) / 2 ) ; if ( $ prefix [ $ mid ] [ $ r ] - $ prefix [ $ mid ] [ $ l - 1 ] >= $ k ) $ hi = $ mid ; else $ lo = $ mid + 1 ; } if ( $ prefix [ $ lo ] [ $ r ] - $ prefix [ $ lo ] [ $ l - 1 ] >= $ k ) $ hi = $ lo ; return $ hi ; }