Comment by lilatree

“… turning an O(log N) search per segment into O(N) overall.”

Can someone explain why?