748
правок
Изменения
Новая страница: «== 5. Поисковые структуры данных== :0. Поисковые структуры данных # [[Упорядоченное множес...»
== 5. Поисковые структуры данных==
:0. [[Поисковые структуры данных]]
# [[Упорядоченное множество]]
# [[Дерево поиска, наивная реализация]]
# [[АВЛ-дерево]]
# [[2-3 дерево]]
# [[B-дерево]]
# [[Красно-черное дерево]] 10
## добавить псевдокод для операций
## расписать доказательства теорем и утверждений подробнее
# [[Декартово дерево]]
# [[Декартово дерево по неявному ключу]] 1
## В псевдокоде нет проверок на ''null''
# [[Splay-дерево]] 0,25
## См. также
# [[Взвешенное дерево]]
# [[Tango-дерево]] 8
## Доказательство теоремы Уилбера
## А причём тут вообще она?
# [[Рандомизированное бинарное дерево поиска]] 0,25
## См. также
# [[Дерево ван Эмде Боаса]]
# [[Список с пропусками]] 7
## \theta cделать большой буквой
## Определение в начале мутное
## Оформить правильно англоязычные термины
## Для log n уровней неясно: добавить знак умножения надо, и откуда там 2 log n взялось?
## Увеличить дроби
## Пояснить подробней структуру и разделить операции по псевдокодам, добавить пояснений
## Отформатировать псевдокод
## log заменить на \log
## Расписать связь вероятности монетки с числом уровней; добавить пару слов про различные варианты честности монетки и что от них зависит
## Оформить правильно источники информации
## Добавить См. также
## Написать, почему все так любят скиплист, особенно в вычислительной геометрии
# [[Fusion tree]]
# [[Сверхбыстрый цифровой бор]] 2
## Отформатировать псевдокоды
## Сказать, почему префиксы в хеше не буду есть много памяти
## Добавить См. также
## Многоточия заменить на \ldots
# [[Rope]]
# [[AA-дерево]]
== 6. Дерево отрезков==
# [[Статистики на отрезках. Корневая эвристика]]
# [[Дерево отрезков. Построение]]
# [[Реализация запроса в дереве отрезков сверху]] 0.5
## Много пробелов в коде, отформатировать
## Заменить neutral на varepsilon, введя сначала моноид
## Добавить построение в См. также
## В примере случаи разной глубины красиво оформить
# [[Реализация запроса в дереве отрезков снизу]]
# [[Несогласованные поддеревья. Реализация массового обновления]] 3
## Добавить примеры массовых операций в начало
## В начале определение очень похоже на определение кольца, то есть возможно ДО работает на кольце. Надо бы это пояснить и кинуть интервики на кольцо (см. замечания в обсуждениях)
## Константы взять в tex
## Отформатировать псевдокод
## Обозначения перед псевдокодов взять в \mathtt или в \mathrm
## Оформить правильно источники информации
## Добавить см. также
# [[Многомерное дерево отрезков]]
# [[Сжатое многомерное дерево отрезков]]
== 7. Дерево Фенвика ==
# [[Дерево Фенвика]]
# [[Встречное дерево Фенвика]]
# [[Дерево Фенвика для некоммутативных операций]] 0.25
## Источники информации
# [[Многомерное дерево Фенвика]] 0,25
## См. также
== 8 Задача о наименьшем общем предке ==
# [[Алгоритм Мо]]
# [[Сведение задачи 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
## Английские термины
== 9. Хеширование ==
# [[Хеш-таблица]] 0,25
## См. также
# [[Разрешение коллизий]]
# [[Хеширование кукушки]]
# [[Идеальное хеширование]]
# [[Перехеширование. Амортизационный анализ]] 1
## Пояснить, почему будет O(1) на добавление при перехешировании
# [[Фильтр Блума]] 0,25
## См. также
# [[Quotient filter]] 3
## Сделать нормальное описание алгоритма, а то ничего не понятно
# [[Универсальное семейство хеш-функций]] 0.5
## Добавить ссылок
## Англоязычные термины
## Смотри обсуждения
## Заменить многоточия на \dots
## Заменить \mod на \bmod
## Заменить знаки неравенств
## Добавить "информации" в источники
# [[Расширяемое хеширование]] 5
## Красивые картинки
## Понятное описание
:0. [[Поисковые структуры данных]]
# [[Упорядоченное множество]]
# [[Дерево поиска, наивная реализация]]
# [[АВЛ-дерево]]
# [[2-3 дерево]]
# [[B-дерево]]
# [[Красно-черное дерево]] 10
## добавить псевдокод для операций
## расписать доказательства теорем и утверждений подробнее
# [[Декартово дерево]]
# [[Декартово дерево по неявному ключу]] 1
## В псевдокоде нет проверок на ''null''
# [[Splay-дерево]] 0,25
## См. также
# [[Взвешенное дерево]]
# [[Tango-дерево]] 8
## Доказательство теоремы Уилбера
## А причём тут вообще она?
# [[Рандомизированное бинарное дерево поиска]] 0,25
## См. также
# [[Дерево ван Эмде Боаса]]
# [[Список с пропусками]] 7
## \theta cделать большой буквой
## Определение в начале мутное
## Оформить правильно англоязычные термины
## Для log n уровней неясно: добавить знак умножения надо, и откуда там 2 log n взялось?
## Увеличить дроби
## Пояснить подробней структуру и разделить операции по псевдокодам, добавить пояснений
## Отформатировать псевдокод
## log заменить на \log
## Расписать связь вероятности монетки с числом уровней; добавить пару слов про различные варианты честности монетки и что от них зависит
## Оформить правильно источники информации
## Добавить См. также
## Написать, почему все так любят скиплист, особенно в вычислительной геометрии
# [[Fusion tree]]
# [[Сверхбыстрый цифровой бор]] 2
## Отформатировать псевдокоды
## Сказать, почему префиксы в хеше не буду есть много памяти
## Добавить См. также
## Многоточия заменить на \ldots
# [[Rope]]
# [[AA-дерево]]
== 6. Дерево отрезков==
# [[Статистики на отрезках. Корневая эвристика]]
# [[Дерево отрезков. Построение]]
# [[Реализация запроса в дереве отрезков сверху]] 0.5
## Много пробелов в коде, отформатировать
## Заменить neutral на varepsilon, введя сначала моноид
## Добавить построение в См. также
## В примере случаи разной глубины красиво оформить
# [[Реализация запроса в дереве отрезков снизу]]
# [[Несогласованные поддеревья. Реализация массового обновления]] 3
## Добавить примеры массовых операций в начало
## В начале определение очень похоже на определение кольца, то есть возможно ДО работает на кольце. Надо бы это пояснить и кинуть интервики на кольцо (см. замечания в обсуждениях)
## Константы взять в tex
## Отформатировать псевдокод
## Обозначения перед псевдокодов взять в \mathtt или в \mathrm
## Оформить правильно источники информации
## Добавить см. также
# [[Многомерное дерево отрезков]]
# [[Сжатое многомерное дерево отрезков]]
== 7. Дерево Фенвика ==
# [[Дерево Фенвика]]
# [[Встречное дерево Фенвика]]
# [[Дерево Фенвика для некоммутативных операций]] 0.25
## Источники информации
# [[Многомерное дерево Фенвика]] 0,25
## См. также
== 8 Задача о наименьшем общем предке ==
# [[Алгоритм Мо]]
# [[Сведение задачи 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
## Английские термины
== 9. Хеширование ==
# [[Хеш-таблица]] 0,25
## См. также
# [[Разрешение коллизий]]
# [[Хеширование кукушки]]
# [[Идеальное хеширование]]
# [[Перехеширование. Амортизационный анализ]] 1
## Пояснить, почему будет O(1) на добавление при перехешировании
# [[Фильтр Блума]] 0,25
## См. также
# [[Quotient filter]] 3
## Сделать нормальное описание алгоритма, а то ничего не понятно
# [[Универсальное семейство хеш-функций]] 0.5
## Добавить ссылок
## Англоязычные термины
## Смотри обсуждения
## Заменить многоточия на \dots
## Заменить \mod на \bmod
## Заменить знаки неравенств
## Добавить "информации" в источники
# [[Расширяемое хеширование]] 5
## Красивые картинки
## Понятное описание
