Arseniy_Pavlov's blog

By Arseniy_Pavlov, 11 years ago, In Russian

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

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

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

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

  • Vote: I like it
  • +7
  • Vote: I do not like it