Алгоритми та структури даних · Junior · Запитання 67 з 75
Що таке масив префіксних сум?
- 1Масив перших символів кожного рядка
- ✓Правильна відповідь: Елемент
iмістить суму першихiелементів оригіналу - 3Вихідний масив, один раз відсортований за зростанням
Пояснення
Після одного проходу за O(n) сума будь-якого діапазону [l, r) дорівнює prefix[r] - prefix[l] і обчислюється за O(1). Це головний прийом, коли той самий масив багато разів питають про суми діапазонів.