Advanced Data Structures

В тази секция ще разгледаме няколко по-сложни структури данни, които решават специфични проблеми значително по-ефективно от алтернативните им наивни имплементации с други структури. Тези структури са интересни за изучаване, тъй като обикновено се базират на интересна идея, която може да се използва и при решаване на други проблеми.

Най-често срещаните от тях, които ще разгледаме тук са индексно (binary indexed tree) и сегментно дърво (segment tree), както и тяхната генерализация - интервално дърво (interval tree). Малко по-редки (в състезателни задачи), но пък популярни в проблеми от реалния живот са квадратичната опашка (tiered vector), префиксното дърво (TRIE) и KD-дървото (KD-tree) (като последното намира голямо приложение в 3D-графиката).

Теми, които можете да прочетете, са: Индексно дърво, Сегментно дърво, Минимум в интервал, Квадратична опашка, и Префиксно дърво, и KD-дърво.

Задачите покриват само някои от изброените структури, като трябва да видите коя къде е приложима.