Задача Дан массив чисел, нужно быстро уметь отвечать на вопрос : есть ли на каком — то отрезке какое — то число.(Быстро — быстрее чем за O(длинны отрезка))

Из структур данных, позволяющих отвечать на какие то запросы на отрезках я знаю дерево отрезков, но я что то не могу придумать, как его здесь использовать.

Это задача с Тимуса http://acm.timus.ru/problem.aspx?space=1&num=1613, идет под темой Структуры данных.

Подскажите пожалуйста, какую структуру данных здесь надо исользовать?