Динамические структуры данных
Иногда в задачах требуется построить структуру данных на массиве очень большого размера (таком, что он не помещается в память). При этом известно, что количество запросов к структуре невелико. Типичная задача: Дан массив размером $n\ (1 \le n \le 10^9)$, изначально заполненный нулями. Необходимо ответить на $q\ (1 \le q \le 10^5)$ запросов одного из двух типов:
- Изменить значение элемента.
- Посчитать сумму на отрезке.
Решение
ЗамечаниеМы умеем решать эту задачу с помощью дерева отрезков, но сталкиваемся с недостатком памяти. Иногда это можно побороть, если воспользоваться техникой сжатия координат. Писать неявное ДО в такой ситуации — стрелять из пушки по воробьям.
Сделаем в дереве отрезков ряд изменений. Во-первых, напишем его на структурах и указателях. Каждая вершина дерева отрезков — это объект, который хранит указатели на своего левого и правого сына. Давайте решать эту задачу так, как мы решали бы ее обычным деревом отрезков, но не вызовем операцию построения. То есть изначально наше дерево отрезков — это корень. Создавать вершины мы будем в операциях обновления, если вершина еще не была создана (похожим на [отложенные операции] образом). При get-запросе считаем, что если вершина не создана, то сумма в ней 0 (логично ведь). Тогда за один запрос мы создадим $O(\log n)$ вершин, суммарно все будет работать за $O(q \log n)$ времени и $O(q \log n)$ памяти.
Код будет добавлен сюда
Use Cases
Используемая в статье техника полезна при работе с: