Before revision:  To obtain our results, we introduce new techniques and ideas, including a reduction to a new geometric line segment selection together with an efficient solution .
After revision:  Additionally, we show a lower bound proving that the query time is optimal for any solution using near-linear space. To achieve our bounds for random access in persistent strings we show how to reduce the problem to the following natural geometric selection problem on line segments. Consider a set of horizontal line segments in the plane. Given parameters i and j, a new geometric line segment selection together with an efficient solution .