Возможно ли реализовать универсальное дерево отрезков (или другую структуру данных), которое поддерживает модификацию на интервале и запрос на интервале?
Под универсальным, подразумевается реализация в виде шаблона, у которого функция «комбинирования значений» (F1) и функция «комбинирования модификаций» (F2) являются параметрами шаблона.
Например:
1) (запрос минимума/присвоение на отрезке): F1 = min, F2 = assign
2) (запрос XOR-a/прибавление на отрезка): F1 = XOR, F2 = add
С более частными случаями ((обновление значения/запрос отрезка), (обновление отрезка/запрос значения)) обобщенная реализация, вроде, получается, но (обновление отрезка/запрос отрезка) — ни в какую. И что-то мне подсказывает, что либо это невозможно, либо F1 и F2 должны обладать какими-то дополнительными свойствами, либо нужная еще какая-нибудь функция F3..
Другими словами: если это возможно, то как? и если нет, то какими дополнительными свойствами должны обладать F1 и F2, чтобы это было возможно?
Бонус-вопрос: правильно ли я понимаю, что дерево (инвертирование однобитных чисел на интервале и запрос суммы) в 242E - XOR на отрезке также использует особые свойства этих функций и не подлежит обобщению?
Спасибо заранее!