Алгоритми та структури даних · Middle · Запитання 56 з 75
Як багато разів відповідати на «суму елементів від i до j» у незмінному масиві?
- 1Відсортувати масив і шукати бінарним пошуком на кожен запит
- ✓Правильна відповідь: Один раз порахувати префіксні суми, далі
prefix[j + 1] - prefix[i]на запит - 3Перераховувати суму циклом на кожен окремий запит
Пояснення
Підготовка займає O(n), а кожен запит O(1). Якщо масив ще й змінюється між запитами, префіксні суми ламаються, і потрібне дерево Фенвіка чи дерево відрізків.