Возможно ли реализовать универсальное дерево отрезков (или другую структуру данных), которое поддерживает модификацию на интервале и запрос на интервале?
Под универсальным, подразумевается реализация в виде шаблона, у которого функция «комбинирования значений» (F1) и функция «комбинирования модификаций» (F2) являются параметрами шаблона.
Например:
1) (запрос минимума/присвоение на отрезке): F1 = min, F2 = assign
2) (запрос XOR-a/прибавление на отрезка): F1 = XOR, F2 = add
С более частными случаями ((обновление значения/запрос отрезка), (обновление отрезка/запрос значения)) обобщенная реализация, вроде, получается, но (обновление отрезка/запрос отрезка) — ни в какую. И что-то мне подсказывает, что либо это невозможно, либо F1 и F2 должны обладать какими-то дополнительными свойствами, либо нужная еще какая-нибудь функция F3..
Другими словами: если это возможно, то как? и если нет, то какими дополнительными свойствами должны обладать F1 и F2, чтобы это было возможно?
Бонус-вопрос: правильно ли я понимаю, что дерево (инвертирование однобитных чисел на интервале и запрос суммы) в 242E - XOR on Segment также использует особые свойства этих функций и не подлежит обобщению?
Спасибо заранее!
У меня есть шаблон, который вам, возможно, поможет. http://ideone.com/C6CKTH И возможный вариант использования http://ideone.com/T4HPZJ. Для поиска максимума на отрезке, и добавления числа к отрезку.
Я недавно писал такое дерево, только потом отложилось. Уже не помню к чему я пришёл. Постараюсь в ближайшее время дописать и выложить код.
Эхх, а ведь это одно из домашних заданий в первом семестре на ФИВТ МФТИ)
Как минимум 3 метода придётся передавать в параметр шаблона:
1) Объединение 2 значений
2) Объединение 2 модификаций
3) Применение модификации к значению в вершине дерева
Вот пример реализации такого класса: https://code.google.com/p/fivt2013-advanced-a/source/browse/Zhuravlyov/Task3_SegmentTree/advancedTree.h
В той же папке можно посмотреть пример реализации конкретного дерева на основе универсального. В частности решены задачи с максимальной подсуммой и количеством отрезков постоянности
Какой хороший у вас ВУЗ :)
У меня в Бауманке на ИУ самое сложное алгоритмическое задание на первом курсе было "прочитать матрицу и вывести строку s[i] = MAX(i-го столбца)". Возможно, за 12 лет что-нибудь поменялось..
Спасибо за шаблон! буду медитировать..
Вас не затруднит дополнительно выложить пример использования с объявлением параметров шаблона?
Всё в той же папке лежит:
https://code.google.com/p/fivt2013-advanced-a/source/browse/Zhuravlyov/Task3_SegmentTree/
Ну, к примеру дерево отрезков с запросами максимума, минимума, суммы с присвоением и прибавлением на отезке: https://code.google.com/p/fivt2013-advanced-a/source/browse/Zhuravlyov/Task3_SegmentTree/ass_incTree.h
Запрос количества отрезков постоянности с присвоением и прибавлением на отрезке: https://code.google.com/p/fivt2013-advanced-a/source/browse/Zhuravlyov/Task3_SegmentTree/NumbOfPermanenceSegmentsTree.h
Запрос максимальной суммы на подотрезке с запросом присвоения на отрезке https://code.google.com/p/fivt2013-advanced-a/source/browse/Zhuravlyov/Task3_SegmentTree/maxSubsegmentTree.h
А все примеры работы с узкими спецификациями уже вот здесь, в тестировании: https://code.google.com/p/fivt2013-advanced-a/source/browse/Zhuravlyov/Task3_SegmentTree/Tests.h
Ссылки больше не открываются. Можете переложить куда-нибудь?
Они просто слегка переехали вот сюда.
Также, если что все еще непонятно, могу предложить и свою реализацию, там есть некоторые комментарии.
А вы так всегда дерево отрезков пишете?
Нет, конечно, олимпиадное ДО я пишу по-другому. Как уже заметил Shkiper, это задание по программированию 1 курса ФИВТа МФТИ, нацелено оно не столько на реализацию алгоритма, который, в сущности, не особо интересный, а на проектирование интерфейса, освоение полиморфизма на шаблонах и покрытие кода тестами. Хотя, может, в один прекрасный день мне будет лень писать какое-нибудь упоротое ДО и я использую это. Но для олимпиад его еще надо бы прилизать в плане производительности.