BigSegmentedArray by Tolia

Мне предоставили реализовать класс, который наследует SegmentedArray и характеризуется следующим:

  • принимает большой массив
  • частые запросы get(), min();

Поскольку команда set задает значение на интервале, я решил сделать «дерево отрезков». Которое устроено как бинарное дерево относительно индекса (в задании большое количество запросов get(), следовательно будет быстрее искать элемент по индексу), имея в себе левый и правые концы интервала, а также значение на этом интервале.

Основная операция в данной структуре — set(). И она самая сложная по своей схеме. Когда приходить запрос на установление значения на интервале, надо проверить, возможно узел пуст, следовательно такого интервала еще не задавали, и тогда можно его создать. Если же узел не пуст, то надо проверить, в данном узле ли задается наш интервал, или же надо перейти к другому. Если же в данном узле надо задать интервал, то у нас вырисовывается три ситуации: когда задаваемый интервал не превосходит интервала узла, когда заданный интервал превосходить  интервал узла и когда одна точка заданного интервала лежит внутри интервала узла, а другая, вне его. В первом случаем, просто разбиваем внутренний интервал на три подинтервала: левая часть внутреннего интервала, заданный интервал и правая часть внутреннего интервала. Во-втором, необходимо увеличить границы внутреннего интервала до задаваемого, и удалить все интервалы(в левом и правом узлах), которые данный новый интервал перекрыл. В третьем необходимо разбить интервал узла на подинтервал до внутренней точки задаваемого интервала, и на то, что осталось. Потом удалить все интервала, которые мы перекрыли.

Untitled

Метод поиска значение по индексу осуществляется как и в бинарном дереве, пока не попадем на нужный нам интервал, или значение данного индекса еще не было установлено.

Метод нахождения минимума на подинтервала спускается по дереву, пока не попадет на нужный интервал, и потом проверяет значения на каждом из интервалов и выбирает минимальный.

Поскольку у нас дерево отсортировано по индексу, то искать индекс элемента по значению сложнее, необходимо пройти все интервалы от индекса, который нам дали в начале, пока не встретим искомое значение, или же выведем, что его нет.

Теоретическая оценка сложности методов:

  • get(i): O(log(count(set)));
  • set(x, y, val): O(log(count(set)));
  • indexof(val, index): O(count(set() — interval(index)));
  • min(x, y) : O(count(set()))
Ссылка на ideone.

 

2 thoughts on “BigSegmentedArray by Tolia

  1. Замечания:
    1) Почему у Вас все индексы класса Integer, а не Int — это ведь замедляет выполнение программы, в чем смысл этого?
    2) по оформлению:
    а) не хватает тестового вывода,
    б) не хватает ссылки на ideone.
    3) а вот теперь с содержанием: пояснение гораздо легче бы читалось, если был бы какой-то поясняющий рисунок. Может у Вас получится построить или найти в интернете или применить какой-либо визуализатор структур данных — например визуализатор двоичных деревьев. Вы могли бы показать для примера какое дерево получается.
    4) Хотя я и не очень вчитывался, но все же — одна из ключевых Ваших операций — это поиск минимума. Пускай Вы ищете минимум во всем массиве. Это точно займет O(log(count(set()))) операций (я правильно расшифровал это как логарифм от количества операций set)?

    • По первому пункту вы правы, поменял как надо, что ускорило структуру.
      Оформил.
      Нарисовал картинку в онлайн фотошопе, в которой изобразил все три ситуации, описанные в данном посте.
      Да, вы правильно поняли, зависит от количества функций set и без логарифма,а на данном промежутке, но это мелочь, так то пусть будет просто от количества set. Его можно оптимизировать, добавив балансировку и избавившись еще от пары этапных моментов. Но количество set у нас не большое, так что структура будет работать быстро и экономно.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *