748
правок
Изменения
→1. Поисковые структуры данных
# [[АВЛ-дерево]]
# [[2-3 дерево]]
# взяли [[B-дерево]] 0,5## все цифры в тех# взяли [[Красно-черное дерево]] 10
## добавить псевдокод для операций
## расписать доказательства теорем и утверждений подробнее
# [[Декартово дерево]]
# взяли [[Декартово дерево по неявному ключу]] 1## В псевдокоде нет проверок на ''null''# взяли [[Splay-дерево]] 0,25## См. также
# [[Взвешенное дерево]]
# [[Tango-дерево]] 8
## См. также
# [[Дерево ван Эмде Боаса]]
# взяли [[Список с пропусками]] 7
## \theta cделать большой буквой
## Определение в начале мутное
== 2. Дерево отрезков==
# [[Статистики на отрезках. Корневая эвристика]]
# взяли [[Дерево отрезков. Построение]] 0.5## Поправить тех## Поправить псевдокод# взяли [[Реализация запроса в дереве отрезков сверху]] 0.5## Много пробелов в коде, отформатировать## Заменить neutral на varepsilon, введя сначала моноид## Добавить построение в См. также## В примере случаи разной глубины красиво оформить## Поправить псевдокод
# [[Реализация запроса в дереве отрезков снизу]]
# [[Несогласованные поддеревья. Реализация массового обновления]] 3
# [[Сведение задачи LCA к задаче RMQ]]
# [[Сведение задачи RMQ к задаче LCA]]
# [[Метод двоичного подъема]] 3## добавить пример работы алгоритма
# [[Решение RMQ с помощью разреженной таблицы]]
# [[Двумерная разреженная таблица]]
# [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
# [[Алгоритм Хьюи]]
# взяли [[Heavy-light декомпозиция]] 6## "решается с помощью heavy-light декомпозиции" — может быть решена## "Пусть A, B - ко" — дефисы нужно заменить на тире## В начале у тебя идут вершины a,b и A,B, а потом u,v и a,b. Надо сделать единообразно, чтобы начало конспекта и его конец согласовывались. Например, сделать корни путей большими буквами — норм. Тогда можно либо a,b и A,B, либо u,v и U,V.## "В данном случае корень одного из путей является вершиной другого." — а почему пути не могут пересекаться крест-на-крест?## Слишком много повтором «Пусть» в доказательстве леммы.## "Но LCA должен принадлежать двум путям. Но" — дублирование «Но»## "Предположим, что LCA не равны" — криво написано, нужно формально исходя из формулировки## Ну и вообще, как будто слов пожадничал на лемму и кое-как написал## "Построим декомпозицию." — декомпозицию чего и для чего? Очень плохо оставлять открытый контекст, особенно в начале пункта. Лучше чуть более подробно описать, чтобы было понятно## "Корень пути, на котором лежит текущая вершина.## Из всех путей выбираем тот, чья начальная вершина наиболее удалена от корня дерева." — вообще непонятно, как связано то, что мы хотим сохранить с тем, что написано потом. Нет предложения-связки## "Пусть требуется" — опять пуст## "Пусть на данной итерации" — как будто других слов нет## "LCA будет та" — это не по-русски## Возьми LCA в тексте везде в \mathrm## "Потому что бесконечно большое количество путей" — откуда в конечном дереве взялось бесконечно большое число путей?
# [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
# взяли [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex> 0,25## См. также
# [[Link-Cut Tree]]<tex>^\star</tex>
# взяли [[Rake-Compress деревья]]<tex>^\star</tex> 0,25## Английские термины
