Выбираем интересующие темы. Структуры данных

В данном посте попробую описать список тем, которые хотелось бы разобрать в рамках подготовки, расставить приоритеты для изучения.

Структуры данных:

1. Дерево отрезков (SQRT-декомпозиция, классическое, дерево Фенвика).
2. Декартово дерево (обычное, по неявному ключу).
3. Система непересекающихся множеств (DSU - Disjoined Set Union).

Дерево отрезков (SQRT-декомпозиция, классическое, дерево Фенвика).

В общем, каждое из этих деревьев я уже не раз писал. Фенвик мне понравился своей лаконичностью, но к сожалению, не все задачи им решать легко, SQRT-декомпозиция пишется просто, вполне прокатит для задач, где Фенвика сложно применить, но время операций не слишком критично. Ну и классическое дерево отрезков - практически универсальный механизм. На сайте e-maxx.ru описано множество его применений, операции в нём выполняются быстрее всего.

• Лекционный материал : ifmo wiki(1,2), e-maxx(1,2,3). По дереву Фенвика была не плохая статья на TopCoder, но сейчас её найти не получается. В книгах разбор и описание данных структур мне не попадались.
• Приоритет изучения - высокий.

Декартово дерево (обычное, по неявному ключу).

Писал его всего один раз для задачи Тимуса 1439 "Поединок с И-Так-Понятно-Кем".
Писал его (а точнее переписывал код и пытался его понять, который мне дал Фёдор Меньшиков) весьма долго и мучительно и не особо оно мне запомнилось. Судя по контестам на Codeforces оно весьма редко появляется в соревнованиях.

• Лекционный материал: ifmo wiki (1,2), e-maxx(1). В книгах его упоминание не видел.
• Приоритет изучения - средний.

Система непересекающихся множеств (DSU - Disjoined Set Union).

Писал эту структуру несколько раз. Так как я пишу на Java, то знакомство и собственно основной подход к написанию данной структуры использую объектно-ориентированный, а не с массивами, как на e-maxx или ifmo wiki. При более детальном изучении материалов с данных ресурсов оказалось, что тот принцип, который я использовал с самого начала уже обладает приличной производительностью (NLogN против N^2) благодаря использованию весовой эвристики . Так же широко известны эвритиски "объединение по рангу (union by rank)" и "сжатие пути (path compression)". Пока что не сталкивался с необходимостью их добавления при написании структуры. Нужно подумать, как их можно удобно добавить к существующей реализации, или возможно пересмотреть её полностью.

• Лекционный материал - ifmo wiki (1,2,3), e-maxx (1), TC Algorithm Tutorials (1)
• Приоритет изучения - средний.

Ради фана почитал статьи про простейшие персистентные структуры данных, теперь знаю как писать персистентный стек :-)

На сегодня всё, до конца неделю планирую разобраться с планом изучения материала и со следующей недели начнём.