Алгоритми та структури даних · Senior · Запитання 71 з 75
На що відповідає за O(1) структура «sparse table»?
- ✓Правильна відповідь: Запити мінімуму на діапазоні незмінного масиву
- 2Перевірки належності в динамічній множині ключів
- 3Найкоротші шляхи між будь-якими двома вершинами
Пояснення
Вона заздалегідь обчислює мінімуми всіх діапазонів довжини 2ᵏ за O(n log n). Будь-який діапазон покривається двома діапазонами-степенями двійки, що перекриваються, а для min перекриття не має значення. Оновлення вимагали б перебудови.