Боря программирует

Деревья отрезков

Когда я учился писать деревья отрезков (ДО) в университете, у меня было примерно такое понимание. В каждой вершине дерева хранится какая-то информация. Когда заходим в вершину, нужно пропушить эту информацию детям. Когда выходим из вершины — мержим информацию из детей.

Для некоторых задач ДО можно писать без проталкивания отложенных операций. Например, если нужно прибавлять на отрезке и считать сумму на отрезке, то в каждой вершине можно запомнить, сколько нужно прибавить к ответу для всех запросов, которые включают эту вершину (e-maxx).

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

Как же улучшилась моя жизнь с приходом Rust!

В какой-то момент я решил написать ДО так, чтобы его можно было легко переиспользовать, и решать задачи на ДО стало гораздо приятнее!

Во-первых, "информацию в вершине" нужно разделить на два отдельных типа:
* Node. То, что мы хотим получить в ответе на get запрос (сумму чисел/минимум/...) и то, что нужно хранить для пересчета этой информации (количество чисел на отрезке, ...).
* Update. То, как мы хотим уметь обновлять значения.

Во-вторых, нужно понять какие условия есть на типы Node и Update:
* Нужно уметь пересчитывать информацию в Node через ее детей. fn join_nodes(left: &Node, right: &Node) -> Node.
* Нужно уметь применять Update к Node. fn apply_update(node: &mut Node, update: &Update).
* Нужно уметь выражать применение двух последовательных Update как один Update. fn join_updates(first: &Update, second: &Update) -> Update.

В-третьих, нужно перестать думать о ДО как о дереве с какой-то конкретной структурой. Не нужно думать о том, как внутри устроены отложенные операции. Не нужно думать о рекурсии. Важен только факт, что можно заимплементить три конкретные функции для нужных типов Node и Update.

А как вы пишете ДО?

www.tgoop.com/bminaiev_blog/43

2.2K viewsJul 4, 2023 at 08:34

Деревья отрезков

Когда я учился писать деревья отрезков (ДО) в университете, у меня было примерно такое понимание. В каждой вершине дерева хранится какая-то информация. Когда заходим в вершину, нужно пропушить эту информацию детям. Когда выходим из вершины — мержим информацию из детей.

Для некоторых задач ДО можно писать без проталкивания отложенных операций. Например, если нужно прибавлять на отрезке и считать сумму на отрезке, то в каждой вершине можно запомнить, сколько нужно прибавить к ответу для всех запросов, которые включают эту вершину (e-maxx).

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

Как же улучшилась моя жизнь с приходом Rust!

В какой-то момент я решил написать ДО так, чтобы его можно было легко переиспользовать, и решать задачи на ДО стало гораздо приятнее!

Во-первых, "информацию в вершине" нужно разделить на два отдельных типа:
* Node. То, что мы хотим получить в ответе на get запрос (сумму чисел/минимум/...) и то, что нужно хранить для пересчета этой информации (количество чисел на отрезке, ...).
* Update. То, как мы хотим уметь обновлять значения.

Во-вторых, нужно понять какие условия есть на типы Node и Update:
* Нужно уметь пересчитывать информацию в Node через ее детей. fn join_nodes(left: &Node, right: &Node) -> Node.
* Нужно уметь применять Update к Node. fn apply_update(node: &mut Node, update: &Update).
* Нужно уметь выражать применение двух последовательных Update как один Update. fn join_updates(first: &Update, second: &Update) -> Update.

В-третьих, нужно перестать думать о ДО как о дереве с какой-то конкретной структурой. Не нужно думать о том, как внутри устроены отложенные операции. Не нужно думать о рекурсии. Важен только факт, что можно заимплементить три конкретные функции для нужных типов Node и Update.

А как вы пишете ДО?

BY Боря программирует