the key to this is to realize that only certain ranges (l...,r) will ever occur during the binary search: it always starts with (0...,n) and divides that at the center, and then continues either left or right and divide that half again and so forth. another way of looking at it is : every entry of the suffix array occurs as central point of exactly one possible range during binary search. so there are exactly n distinct ranges (l...m...r) that can possibly play a role during binary search, and it suffices to precompute lcp(l,m) and lcp(m,r) for those n possible ranges. so that is 2*n distinct precomputed values, hence lcp-lr is o(n) in size.