Comments 16
У дерева отрезков тьма-тьмущая применений окромя минимума ведь, это же моноидальная структура.
А в чем вы так красиво деревья рисуете? Есть какой-то специальный софт?
О да, специальная софтина это просто-напросто автофигуры в ворде :)
Пост я готовил в нём, и возможностей мне вполне хватило.
Пост я готовил в нём, и возможностей мне вполне хватило.
Я обычно юзаю graphViz
В Google Docs есть тип документа Drawing, в нём тоже получаются отличные рисунки
Интересно, один я вздрагиваю уже в 4-й раз за сегодня, натыкаясь на школьную задачку? Такой флешбек…
Вообще, за 12 лет практики ни разу не пригодились те олимпиадные задачки и алгоритмы, которыми нас так мучали на информатике. Кому-то пригодились? Поделитесь!
Вообще, за 12 лет практики ни разу не пригодились те олимпиадные задачки и алгоритмы, которыми нас так мучали на информатике. Кому-то пригодились? Поделитесь!
Проблема в том, что они были написаны во всех стандартных библиотеках давным-давно. Программист просто превращается в архитектора, слепляющего блоки написанных алгоритмов в единое целое.
Это надо сказать, у вас хорошая информатика была, если вы двенадцать лет назад на ней деревьями отрезков занимались в виде школьных задачек.
Это надо сказать, у вас хорошая информатика была, если вы двенадцать лет назад на ней деревьями отрезков занимались в виде школьных задачек.
Вроде бы, деревья отрезков совсем не были распространены двенадцать лет назад :)
На самом деле, это пригождается, если нужно написать какой-нибудь кусок кода, который должен обрабатывать огромные данные очень быстро.
На самом деле, это пригождается, если нужно написать какой-нибудь кусок кода, который должен обрабатывать огромные данные очень быстро.
Регулярно. Работая со встраиваемыми системами, или с системами, главное конкурентное преимущество которых — производительность, приходится выжимать из железяк тот максимум, на который они способны. Стандартные реализации в подобных условиях могут отсутствовать, либо быть недостаточно хорошими.
Хорошая статья, спасибо. К слову, описание интервальных деревьев есть в Кормене.
Для Haskell существует чистая функциональная реализация (возможно, кому-то будет интересно на неё посмотреть — особенно в контексте взвешенных моноидов):
hackage.haskell.org/packages/archive/SegmentTree/0.2/doc/html/Data-SegmentTree.html
Приходилось использовать в проекте, был зело доволен.
Для Haskell существует чистая функциональная реализация (возможно, кому-то будет интересно на неё посмотреть — особенно в контексте взвешенных моноидов):
hackage.haskell.org/packages/archive/SegmentTree/0.2/doc/html/Data-SegmentTree.html
Приходилось использовать в проекте, был зело доволен.
В следующей статье мы научимся делать запрос сверху.Обещанного три года ждут?
Два уже почти прошли :-)
Возможно ли реализовать универсальное дерево отрезков, которое поддерживает модификацию на интервале и запрос на интервале? В чем главная идея?
Под универсальным, подразумевается реализация в виде шаблона, у которого функция «комбинирования значений» (F1) и функция «комбинирования модификаций» (F2) являются параметрами шаблона.
Например:
1) <запрос минимума, присвоение на отрезке>: F1 = min, F2 = assign
2) <запрос XOR-a, прибавление на отрезка>: F1 = XOR, F2 = add
Сам пробовал это сделать через ленивую модификацию, добавив третий параметр шаблона «функция комбинирования значения и модификации» — не получилось, работало за квадрат при некотором наборе данных.
В общеизвестном пособии для начинающих есть только частные примеры.
Под универсальным, подразумевается реализация в виде шаблона, у которого функция «комбинирования значений» (F1) и функция «комбинирования модификаций» (F2) являются параметрами шаблона.
Например:
1) <запрос минимума, присвоение на отрезке>: F1 = min, F2 = assign
2) <запрос XOR-a, прибавление на отрезка>: F1 = XOR, F2 = add
Сам пробовал это сделать через ленивую модификацию, добавив третий параметр шаблона «функция комбинирования значения и модификации» — не получилось, работало за квадрат при некотором наборе данных.
В общеизвестном пособии для начинающих есть только частные примеры.
Надо уточнить, что в коде под log подразумевается двоичный логарифм, а то Си-подобный синтаксис немного сбивает с толку.
С библиотекой math.h такой логарифм реализуется: log10(x) / log(2).
С библиотекой math.h такой логарифм реализуется: log10(x) / log(2).
Sign up to leave a comment.
Задача RMQ – 2. Дерево отрезков