Advanced Data Structures
В тази секция ще разгледаме няколко по-сложни структури данни, които решават специфични проблеми значително по-ефективно от алтернативните им наивни имплементации с други структури. Тези структури са интересни за изучаване, тъй като обикновено се базират на интересна идея, която може да се използва и при решаване на други проблеми.Най-често срещаните от тях, които ще разгледаме тук са индексно (binary indexed tree) и сегментно дърво (segment tree), както и тяхната генерализация - интервално дърво (interval tree). Малко по-редки (в състезателни задачи), но пък популярни в проблеми от реалния живот са квадратичната опашка (tiered vector), префиксното дърво (TRIE) и KD-дървото (KD-tree) (като последното намира голямо приложение в 3D-графиката).
Теми, които можете да прочетете, са: Индексно дърво, Сегментно дърво, Минимум в интервал, Квадратична опашка, и Префиксно дърво, и KD-дърво.
Задачите покриват само някои от изброените структури, като трябва да видите коя къде е приложима.
Sheep
13
|
3
Train
15
|
35
Closest Point
31
|
25
Shoes
71
|
33
Random Sums
6
|
35
Server
3
|
50