DmitriyH's blog

By DmitriyH, 11 years ago, In Russian

Возможно ли реализовать универсальное дерево отрезков (или другую структуру данных), которое поддерживает модификацию на интервале и запрос на интервале?

Под универсальным, подразумевается реализация в виде шаблона, у которого функция «комбинирования значений» (F1) и функция «комбинирования модификаций» (F2) являются параметрами шаблона.
Например:

1) (запрос минимума/присвоение на отрезке): F1 = min, F2 = assign
2) (запрос XOR-a/прибавление на отрезка): F1 = XOR, F2 = add

С более частными случаями ((обновление значения/запрос отрезка), (обновление отрезка/запрос значения)) обобщенная реализация, вроде, получается, но (обновление отрезка/запрос отрезка) — ни в какую. И что-то мне подсказывает, что либо это невозможно, либо F1 и F2 должны обладать какими-то дополнительными свойствами, либо нужная еще какая-нибудь функция F3..

Другими словами: если это возможно, то как? и если нет, то какими дополнительными свойствами должны обладать F1 и F2, чтобы это было возможно?

Бонус-вопрос: правильно ли я понимаю, что дерево (инвертирование однобитных чисел на интервале и запрос суммы) в 242E - XOR on Segment также использует особые свойства этих функций и не подлежит обобщению?

Спасибо заранее!

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