Алгоритмы и структуры данных2:Тикеты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎1. Поисковые структуры данных)
(→‎1. Поисковые структуры данных)
 
(не показано 17 промежуточных версий этого же участника)
Строка 6: Строка 6:
 
# [[АВЛ-дерево]]
 
# [[АВЛ-дерево]]
 
# [[2-3 дерево]]
 
# [[2-3 дерево]]
−
# [[B-дерево]] 0,5
+
# [[B-дерево]]  
−
## все цифры в тех
+
# взяли [[Красно-черное дерево]] 10
−
# [[Красно-черное дерево]] 10
 
 
## добавить псевдокод для операций
 
## добавить псевдокод для операций
 
## расписать доказательства теорем и утверждений подробнее
 
## расписать доказательства теорем и утверждений подробнее
 
# [[Декартово дерево]]
 
# [[Декартово дерево]]
−
# [[Декартово дерево по неявному ключу]] 1
+
# [[Декартово дерево по неявному ключу]]
−
## В псевдокоде нет проверок на ''null''
+
# [[Splay-дерево]]  
−
# [[Splay-дерево]] 0,25
 
−
## См. также
 
 
# [[Взвешенное дерево]]  
 
# [[Взвешенное дерево]]  
 
# [[Tango-дерево]] 8
 
# [[Tango-дерево]] 8
 
## Доказательство теоремы Уилбера
 
## Доказательство теоремы Уилбера
 
## А причём тут вообще она?
 
## А причём тут вообще она?
−
# [[Рандомизированное бинарное дерево поиска]] 0,25
+
# взяли [[Рандомизированное бинарное дерево поиска]] 0,25
 
## См. также
 
## См. также
 
# [[Дерево ван Эмде Боаса]]
 
# [[Дерево ван Эмде Боаса]]
−
# [[Список с пропусками]] 7
+
# взяли [[Список с пропусками]] 7
 
## \theta cделать большой буквой
 
## \theta cделать большой буквой
 
## Определение в начале мутное
 
## Определение в начале мутное
Строка 51: Строка 48:
 
# [[Статистики на отрезках. Корневая эвристика]]
 
# [[Статистики на отрезках. Корневая эвристика]]
 
# [[Дерево отрезков. Построение]]
 
# [[Дерево отрезков. Построение]]
−
# [[Реализация запроса в дереве отрезков сверху]] 0.5
+
# [[Реализация запроса в дереве отрезков сверху]]  
−
## Много пробелов в коде, отформатировать
 
−
## Заменить neutral на varepsilon, введя сначала моноид
 
−
## Добавить построение в См. также
 
−
## В примере случаи разной глубины красиво оформить
 
 
# [[Реализация запроса в дереве отрезков снизу]]
 
# [[Реализация запроса в дереве отрезков снизу]]
 
# [[Несогласованные поддеревья. Реализация массового обновления]] 3
 
# [[Несогласованные поддеревья. Реализация массового обновления]] 3
Строка 66: Строка 59:
 
## Добавить см. также
 
## Добавить см. также
 
# [[Многомерное дерево отрезков]]  
 
# [[Многомерное дерево отрезков]]  
−
# [[Сжатое многомерное дерево отрезков]]  
+
# [[Сжатое многомерное дерево отрезков]]
  
 
== 3. Дерево Фенвика ==
 
== 3. Дерево Фенвика ==
 
# [[Дерево Фенвика]]
 
# [[Дерево Фенвика]]
 
# [[Встречное дерево Фенвика]]
 
# [[Встречное дерево Фенвика]]
−
# [[Дерево Фенвика для некоммутативных операций]] 0.25
+
# взяли [[Дерево Фенвика для некоммутативных операций]] 0.25
 
## Источники информации
 
## Источники информации
−
# [[Многомерное дерево Фенвика]] 0,25
+
# взяли [[Многомерное дерево Фенвика]] 0,25
 
## См. также
 
## См. также
  
Строка 80: Строка 73:
 
# [[Сведение задачи LCA к задаче RMQ]]
 
# [[Сведение задачи LCA к задаче RMQ]]
 
# [[Сведение задачи RMQ к задаче LCA]]
 
# [[Сведение задачи RMQ к задаче LCA]]
−
# [[Метод двоичного подъема]] 3
+
# [[Метод двоичного подъема]]
−
## добавить пример работы алгоритма
 
 
# [[Решение RMQ с помощью разреженной таблицы]]
 
# [[Решение RMQ с помощью разреженной таблицы]]
 
# [[Двумерная разреженная таблица]]
 
# [[Двумерная разреженная таблица]]
−
# [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
+
# [[Алгоритм Фарака-Колтона и Бендера]]  
 
# [[Алгоритм Хьюи]]
 
# [[Алгоритм Хьюи]]
−
# [[Heavy-light декомпозиция]] 6
+
# [[Heavy-light декомпозиция]]  
−
## "решается с помощью 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>
 
# [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
−
# [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex> 0,25
+
# [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex>  
−
## См. также
 
 
# [[Link-Cut Tree]]<tex>^\star</tex>
 
# [[Link-Cut Tree]]<tex>^\star</tex>
−
# [[Rake-Compress деревья]]<tex>^\star</tex> 0,25
+
# [[Rake-Compress деревья]]<tex>^\star</tex>  
−
## Английские термины
 
−
 
 
  
  

Текущая версия на 13:58, 18 мая 2019

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

0. Поисковые структуры данных
  1. Упорядоченное множество
  2. Дерево поиска, наивная реализация
  3. АВЛ-дерево
  4. 2-3 дерево
  5. B-дерево
  6. взяли Красно-черное дерево 10
    1. добавить псевдокод для операций
    2. расписать доказательства теорем и утверждений подробнее
  7. Декартово дерево
  8. Декартово дерево по неявному ключу
  9. Splay-дерево
  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. Дерево отрезков. Построение
  3. Реализация запроса в дереве отрезков сверху
  4. Реализация запроса в дереве отрезков снизу
  5. Несогласованные поддеревья. Реализация массового обновления 3
    1. Добавить примеры массовых операций в начало
    2. В начале определение очень похоже на определение кольца, то есть возможно ДО работает на кольце. Надо бы это пояснить и кинуть интервики на кольцо (см. замечания в обсуждениях)
    3. Константы взять в tex
    4. Отформатировать псевдокод
    5. Обозначения перед псевдокодов взять в \mathtt или в \mathrm
    6. Оформить правильно источники информации
    7. Добавить см. также
  6. Многомерное дерево отрезков
  7. Сжатое многомерное дерево отрезков

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_и_структуры_данных2:Тикеты&oldid=71255»