Алгоритми та структури даних · Senior · Запитання 33 з 75
Яка структура дозволяє знайти всі інтервали, що містять точку, за O(log n + k)?
- 1Trie з меж інтервалів
- ✓Правильна відповідь: Дерево інтервалів
- 3Хеш-таблиця за початком
Пояснення
Дерево інтервалів - збалансоване BST, впорядковане за початком, де кожен вузол ще зберігає максимальний кінець у своєму піддереві, тож цілі гілки можна пропускати. Його використовують календарі й інструменти для геномів.