Алгоритмы и структуры данных2:Тикеты

1. Поисковые структуры данных

0. Поисковые структуры данных

1. Упорядоченное множество
2. Дерево поиска, наивная реализация
3. АВЛ-дерево
4. 2-3 дерево
5. взяли B-дерево 0,5
   1. все цифры в тех
6. Красно-черное дерево 10
   1. добавить псевдокод для операций
   2. расписать доказательства теорем и утверждений подробнее
7. Декартово дерево
8. взяли Декартово дерево по неявному ключу 1
   1. В псевдокоде нет проверок на null
9. взяли Splay-дерево 0,25
   1. См. также
10. Взвешенное дерево
11. Tango-дерево 8
    1. Доказательство теоремы Уилбера
    2. А причём тут вообще она?
12. взяли Рандомизированное бинарное дерево поиска 0,25
    1. См. также
13. Дерево ван Эмде Боаса
14. Список с пропусками 7
    1. \theta cделать большой буквой
    2. Определение в начале мутное
    3. Оформить правильно англоязычные термины
    4. Для log n уровней неясно: добавить знак умножения надо, и откуда там 2 log n взялось?
    5. Увеличить дроби
    6. Пояснить подробней структуру и разделить операции по псевдокодам, добавить пояснений
    7. Отформатировать псевдокод
    8. log заменить на \log
    9. Расписать связь вероятности монетки с числом уровней; добавить пару слов про различные варианты честности монетки и что от них зависит
    10. Оформить правильно источники информации
    11. Добавить См. также
    12. Написать, почему все так любят скиплист, особенно в вычислительной геометрии
15. Fusion tree
16. Сверхбыстрый цифровой бор 2
    1. Отформатировать псевдокоды
    2. Сказать, почему префиксы в хеше не буду есть много памяти
    3. Добавить См. также
    4. Многоточия заменить на \ldots
17. Rope
18. AA-дерево
19. Техника частичного каскадирования
    1. Правильно оформить источники информации
20. Centroid decomposition

2. Дерево отрезков

1. Статистики на отрезках. Корневая эвристика
2. взяли Дерево отрезков. Построение 0.5
   1. Поправить тех
   2. Поправить псевдокод
3. взяли Реализация запроса в дереве отрезков сверху 0.5
   1. Много пробелов в коде, отформатировать
   2. Заменить neutral на varepsilon, введя сначала моноид
   3. Добавить построение в См. также
   4. В примере случаи разной глубины красиво оформить
   5. Поправить псевдокод
4. Реализация запроса в дереве отрезков снизу
5. Несогласованные поддеревья. Реализация массового обновления 3
   1. Добавить примеры массовых операций в начало
   2. В начале определение очень похоже на определение кольца, то есть возможно ДО работает на кольце. Надо бы это пояснить и кинуть интервики на кольцо (см. замечания в обсуждениях)
   3. Константы взять в tex
   4. Отформатировать псевдокод
   5. Обозначения перед псевдокодов взять в \mathtt или в \mathrm
   6. Оформить правильно источники информации
   7. Добавить см. также
6. Многомерное дерево отрезков
7. Сжатое многомерное дерево отрезков

3. Дерево Фенвика

1. Дерево Фенвика
2. Встречное дерево Фенвика
3. взяли Дерево Фенвика для некоммутативных операций 0.25
   1. Источники информации
4. взяли Многомерное дерево Фенвика 0,25
   1. См. также

4 Задача о наименьшем общем предке

1. Алгоритм Мо
2. Сведение задачи LCA к задаче RMQ
3. Сведение задачи RMQ к задаче LCA
4. Метод двоичного подъема
5. Решение RMQ с помощью разреженной таблицы
6. Двумерная разреженная таблица
7. Алгоритм Фарака-Колтона и Бендера
8. Алгоритм Хьюи
9. Heavy-light декомпозиция
10. Алгоритм Шибера-Вишкина[math]^\star[/math]
11. Алгоритм Тарьяна поиска LCA за O(1) в оффлайн[math]^\star[/math]
12. Link-Cut Tree[math]^\star[/math]
13. Rake-Compress деревья[math]^\star[/math]