Персистентное дерево отрезков
Общий подход к персистентности почти любой ссылочной структуры — это создавать копии всех вершин, в которых хоть что-то меняется, и менять это что-то в копиях, никогда не изменяя уже существующие вершины.
Персистентное дерево отрезков здесь не исключение. Просто будем при спуске создавать копию вершины перед тем, как что-либо менять в ней самой или её потомках. Асимптотика операций от этого не изменится, разве что общее потребление памяти увеличится до $O(m \log n)$.
Удобнее всего по аналогии с push в отложенных операциях определить функцию copy , копирующую детей текущей вершины, и просто без разбору вызывать её во всех вершинах, в которых что-то может измениться.
Теперь осталось только создать список версий, и после каждой операции копировать туда новый корень:
В качестве альтернативного подхода можно копировать не детей, а текущую вершину, и возвращать её из рекурсии и переподвешивать за родителя. Это вычислительно эффективнее, но нужно сильно изменить реализацию.
#Применения
В контексте задач на структуры данных персистентное дерево отрезков особенно часто применяют в задачах, где применили бы метод сканирующей прямой, если бы запросы были известны заранее.
#Сумма на прямоугольнике
Задача. Даны $n$ точек на плоскости. Нужно в онлайн ответить на $q$ запросов числа точек на прямоугольнике.
Если бы можно было отвечать в оффлайн, мы бы разбили запрос на два запроса на префиксах и прошлись бы сканлайном слева направо, добавляя $y$-координаты точек в дерево отрезков и отвечая на запросы суммы на подотрезках — но так делать мы не можем.
Но точки в оффлайн известны. Добавим их в таком же порядке в персистентное дерево отрезков, а не обычное, и сохраним корни деревьев с разными $x$-координатами в порядке увеличения.
Теперь мы можем ответить на запрос, так же декомпозировав его на два и перенаправив их в две разные версии дерева отрезков, соответствующие большей и меньшей $x$-координатам. Таким образом, можно отвечать на запросы в онлайн за $O(q \log n)$ времени и памяти.
#Порядковые статистики
Задача. Дан отрезок из $n$ целых чисел и $q$ запросов $k$-той порядковой статистики на подотрезке.
Во-первых, сожмем все числа, чтобы они были от 1 до $n$.
Затем, пройдёмся с персистентным деревом отрезков для суммы по массиву слева направо, и когда будем обрабатывать элемент $a_k$, добавим единицу к $a_k$-ому элементу в дереве отрезков. Заметим, что сумма с $l$ по $r$ в таком дереве будет равна количеству элементов между $l$ и $r$ на текущем префиксе.
Дальше определим разность деревьев как дерево отрезков, которое получилось бы, если бы оно было построено поверх разности соответствующих массивов.
Что будет находиться в разности $r$-го и $l$-го дерева ($r > l$)? Там будут находиться количества вхождений чисел на отрезке массива с $l$ по $r$ — какой-то массив целых неотрицательных чисел. Если в таком разностном дереве сделать спуск, который находит последнюю позицию, у которой сумма на префиксе не превышает $k$ — она и будет ответом на запрос.
Если не обязательно строить разностное дерево явно, чтобы делать по нему спуск — можно просто спускаться одновременно в двух деревьях и везде вместо суммы $s$ использовать $(s_r — s_l)$:
Отметим, что эту и предыдущую задачу также можно решить через mergesort tree за $O(n \log^2 n)$, а также двумерными структурами за такую же асимптотику.
#Доминирующий элемент
Задача. Дан массив из $n$ элементов. Требуется ответить на $m$ запросов, есть ли на отрезке $[l, r)$ доминирующий элемент — тот, который встречается на нём хотя бы $\frac$ раз.
У этой задачи есть удивительно простое решение — взять около 100 случайных элементов для каждого проверить, является ли он доминирующим. Проверку можно выполнять за $O(\log n)$, посчитав для каждого значения отсортированный список позиций, на которых он встречается, и сделав в нём два бинпоиска. Вероятность ошибки в худшем случае равна $\frac>$, и ей на практике можно пренебречь.
Но проверять 100 сэмплов — долго. Построим такое же дерево отрезков, как в прошлой задаче, и решим задачу «найти число, большее $\frac$ в массиве из $n$ неотрицательных целых чисел с суммой не более $n$» относительно разностного дерева. Это тоже будет спуском по нему: каждый раз идём в того сына, где сумма больше (потому что сын с меньшей суммой точно не доминирующий). Если в листе, куда мы пришли, значение больше нужного, возвращаем true , иначе false .
Упражнение. Придумайте, как модифицировать спуск в задаче где доминирующим считается элемент, встречающийся хотя бы $\frac$ раз для маленького $k$ (от 2 до 5).
#Как персистентный массив
С помощью дерева отрезков обычно и реализуют полностью персистентный массив — в общем случае быстрее $O(\log n)$ на запрос не получается. Персистентный массив в свою очередь можно использовать, чтобы делать персистентными не-ссылочные структуры — например, систему непересекающихся множеств.
В СНМ мы храним всё состояние в массивах, которые можно просто сделать персистентными через дерево отрезков. Асимптотика такой структуры будет $O(n \log n)$ времени и памяти — причем логарифм здесь и от самого СНМа (нужно пройтись по $O(\log n)$ предков — эвристику сжатия путей мы использовать не можем), так и от персистентного ДО (обновить значение какого-то $p_v$ и $s_v$ / $h_v$).
Источник
Порядковая статистика дерево отрезков
MikeMirzayanov → Filter for Past Contests
pakhomovee → Codeforces Round #893 (Div. 2)
PinkieRabbit → AI language models and cheating in online contests
ashwanth106121023 → Good Observations:
MrPrince22 → Answer queries for number of subarrays where sum is equal to K
Vladosiya → Codeforces Round #874 (Div. 3) Разбор
R.A.N.K.A. → Help in Permutation P[i]=P[P[i]]
Agnimandur → Codeforces Round 736 Editorial
T heQueenOfHatred → 2023 KSAAC Summer · solved.ac Arena #4 Announcement
K evin114514 → I’m Kevin114514, AMA!
abcsumits → Help me to find number of solution of this equation efficiently
Iuc_Crie → Sigh
G eothermal → I’m Geothermal. AMA!
mauryasunny088 → Help needed in EDU section Question
steveonalex → [Tutorial] Divide and Conquer Offline Query — A Niche Way to solve Static Range Query
Vladithur → Codeforces Round #890 (Div. 2) Editorial
awoo → Разбор Educational Codeforces Round 149
mustard_with_fries69420 → Help Needed
maverick_GOD → How to use gcc instead of clang on macOS, specially M1? (Help)
mohit_jx64 → [Invitation] Coding Events — Esya’23 IIIT-Delhi
Medeali → Solving Div 1 A in two hours.Is it good for gray coder?
lumibons → CEOI 2023
SriniV → Answering Queries in sub-linear time
awoo → Разбор Educational Codeforces Round 150
MikeMirzayanov → Изменение правил об использовании стороннего кода в соревнованиях Codeforces
Блог пользователя yarrr
Автор yarrr, 12 лет назад ,
Пацаны, расскажите пожалуйста, я баян придумал или нет?
2) Строим n-штук persistent segment tree, где на i -м шаге добавляем в дерево отрезков индекс элемента, который находится по i -му индексу в отсортированном массиве пар.
3) Бинпоиском находит нижнюю границу i , где в дереве отрезков i sum(l, r) ≥ k .
k-th order statistic, segment tree
Комментарии (38)
K-ю порядковую статистику на отрезке за O(log^2(n)) на запрос можно считать неперсистентным деревом отрезков. А при помощи персистентного можно досчить асимптотики O(log(n)) на запрос
Представим, что на плоскости отмечены точки с координатами (i, a[i]). Тогда ответом на запрос будет k-я по высоте точка в вертикальной полосе, края которой соответствуют границам запроса.
Сожмём координаты и построим персистентное дерево отрезков на сумме, добавляя в позицию trans(a[i]) единицу, где trans(a) — значение а в сжатых координатах (должно получиться такое дерево, что итоговая версия будет возвращать кол-во элементов, значения которых после сжатия лежат в диапазоне от l до r). Теперь, за логарифм спускаясь из корня соответствующей версии дерева, мы умеем отвечать на запрос о k-й порядковой статистике на префиксе массива. Так как деревья отрезков для разных префиксов изоморфны, то дерево для вертикальной полосы, соответствующей отрезку запроса [L; R], можно получить, вычитая из значения в каждой вершине дерева версии R значение в соответствующей вершине версии L-1. Так как нам интересны значения только в O(log(n)) вершинах этого дерева, то не станем строить его явно, а просто будем спускаться по обеим версиям и получать нужные значения в несуществующем дереве для полосы от L до R.
P.S. Кривое вышло объяснение, но без листочка, на котором можно что-нибудь схематично изобразить, лучше не могу.
Источник
Порядковая статистика дерево отрезков
MikeMirzayanov → Filter for Past Contests
pakhomovee → Codeforces Round #893 (Div. 2)
PinkieRabbit → AI language models and cheating in online contests
ashwanth106121023 → Good Observations:
MrPrince22 → Answer queries for number of subarrays where sum is equal to K
Vladosiya → Codeforces Round #874 (Div. 3) Разбор
R.A.N.K.A. → Help in Permutation P[i]=P[P[i]]
Agnimandur → Codeforces Round 736 Editorial
T heQueenOfHatred → 2023 KSAAC Summer · solved.ac Arena #4 Announcement
K evin114514 → I’m Kevin114514, AMA!
abcsumits → Help me to find number of solution of this equation efficiently
Iuc_Crie → Sigh
G eothermal → I’m Geothermal. AMA!
mauryasunny088 → Help needed in EDU section Question
steveonalex → [Tutorial] Divide and Conquer Offline Query — A Niche Way to solve Static Range Query
Vladithur → Codeforces Round #890 (Div. 2) Editorial
awoo → Разбор Educational Codeforces Round 149
mustard_with_fries69420 → Help Needed
maverick_GOD → How to use gcc instead of clang on macOS, specially M1? (Help)
mohit_jx64 → [Invitation] Coding Events — Esya’23 IIIT-Delhi
Medeali → Solving Div 1 A in two hours.Is it good for gray coder?
lumibons → CEOI 2023
SriniV → Answering Queries in sub-linear time
awoo → Разбор Educational Codeforces Round 150
MikeMirzayanov → Изменение правил об использовании стороннего кода в соревнованиях Codeforces
Блог пользователя mathAway
K-я порядковая статистика между двумя вершинами дерева
Автор mathAway, история, 3 года назад ,
Задача: есть дерево, в каждой вершине которого записано число. Требуется отвечать на запросы (u,v,k) — найти k-ю порядковкую статистику на пути между вершинами u и v. Количество вершин и количество запросов
Пока что не знаю, как решать эту задачу, но решал похожую: отвечать на запросы (u,k) — найти k-ю порядковую статистику в поддереве вершины u(Оригинал). Там я перенумеровал все вершины таким образом, что задача свелась к нахождению порядковой статистики на отрезке массива, что решается персистентным деревом отрезков. Тут же я не нашёл способа, что и как можно перенумеровать, чтобы достичь подобного эффекта.
дерево отрезков, структуры данных, порядковая статистика
Комментарии (7)
С помощью heavy-light декомпозиции задача сводится к «найти k-ю порядковую статистику в массиве на объединении log n отрезков». Это решается так же, как и обычная k-я порядковая статистика, только теперь вместо параллельного запуска из двух вершин, запускаемся из 2 * «кол-во отрезков, на которые разбился путь» вершин.
UPD. И правда, снизу предложено решение куда лучше
Зачем тут HLD? Можно в персистентном ДО хранить все числа на пути от корня до вершины, для вершины $$$i$$$ обозначим такое дерево как $$$tree_i$$$. Тогда ответ считается как спуск по $$$tree_v + tree_u — 2 \cdot tree_
Блин, а я ведь мыслил очень близко! Но если мы для каждой вершины будем хранить все числа на пути от корня до неё, то не будет ли такое решение потреблять n^2 памяти? Если сравнивать с использованием пдо для нахождения к-й порядковой статистики на отрезке, то там мы строим его так: создаём массив x размера количества различных элементов в исходном массиве, а затем бежим слева направо по этому исходному массиву и прибавляем единичку в соответствующей позиции массива x, только этот массив хранится в виде до и у нас есть все его версии, т.е. пдо. Почему объём памяти куда меньше, чем мне кажется? Если брать, к примеру случай дерева, как последовательно связанных вершин, а корнем является вершина 1.
Это будет $$$O(n \log n)$$$ памяти. Пишется аналогично задаче на массиве, просто вместо $$$tree_i = add(tree_, a_i)$$$ (тут $$$a_i$$$ — элемент массива) получается $$$tree_i = add(tree_, a_i)$$$ (тут $$$a_i$$$ — число в вершине, $$$parent_i$$$ — предок в дереве)
Всё, я наконец понял, спасибо 🙂 Я на некоторое время забыл, что обновление в пдо добавляет лишь логарифм вершин.
Автокомментарий: текст был обновлен пользователем mathAway (предыдущая версия, новая версия, сравнить).
Источник