1. Індекси та контракт префіксів
Уявіть, що у вас є масив чисел — наприклад, щоденні витрати за місяць. І раптом до вас надходять запитання: «Скільки я витратив із 5-го по 12-й день?», «А з 10-го по 20-й?», «А з 1-го по 30-й?». Якщо для кожного запиту проходити масив і щоразу заново підсумовувати елементи, код буде коректним… але за великої кількості запитів він почне «грітися», як ноутбук на колінах.
Префіксні суми — це спосіб один раз виконати підготовчу роботу за O(n), а потім отримувати суму будь-якого відрізка за O(1). Тобто ви платите «вхідний квиток» лише один раз, а далі катаєтеся на атракціонах без черги.
Діапазон і індекси
Перш ніж будувати префікси, треба домовитися про найнебезпечніше місце теми: що саме ми називаємо діапазоном. У Swift ви вже бачили два типи діапазонів: ..< — напіввідкритий, правий край не включається, і ... — включний. У задачах на суми часто трапляється «людський» діапазон виду [l, r], де обидва кінці включені. Це зручно для формул, але дуже легко схопити off-by-one, якщо в голові живе ..<.
Тож зараз ми зробимо дорослу річ: зафіксуємо домовленість на рівні формули й коду. І надалі триматимемося її так само вперто, як компілятор тримається за типи.
Контракт: prefix[i] = сума numbers[0..<i]
Звучить сухувато, але саме такий контракт і рятує префікси від перетворення на випадковий набір чисел. Ми будуємо масив prefix довжини n + 1, де n = numbers.count. І визначаємо:
- prefix[0] = 0 (сума перших нуля елементів — це нуль, цілком логічно)
- prefix[i] = сума numbers[0..<i] — тобто сума перших i елементів масиву
Ця домовленість дуже зручна, бо прибирає окремі випадки. Вам не потрібно окремо думати: «А що, якщо діапазон починається з 0?», — бо prefix[0] уже існує.
Невелика примітка для допитливих: по суті, префіксні суми — це окремий випадок операції scan (накопичення проміжних результатів). У Swift Evolution навіть обговорювали додавання подібних послідовних операцій до стандартної бібліотеки, поруч із ідеями про scan і повʼязані методи.
Приклад вручну: як виглядає prefix
Не будемо вірити словам — порахуємо вручну. Нехай:
numbers = [2, -1, 3, 5]
Тоді prefix має бути довжини 5 — тобто n + 1:
| i (індекс prefix) | Що означає numbers[0..<i] | Сума | prefix[i] |
|---|---|---|---|
| 0 | |
0 | 0 |
| 1 | |
2 | 2 |
| 2 | |
1 | 1 |
| 3 | |
4 | 4 |
| 4 | |
9 | 9 |
І ось у нас уже є магія: якщо ми захочемо суму перших трьох елементів, це буде просто prefix[3].
Як побудувати prefix за один прохід
Тепер — код. Він короткий, і це приємно: рідкісний випадок, коли алгоритм швидкий і не схожий на заклинання зі стародавнього манускрипту.
import Foundation
func prefixSums(of numbers: [Int]) -> [Int] {
var prefix = Array(repeating: 0, count: numbers.count + 1)
for i in 0..<numbers.count {
prefix[i + 1] = prefix[i] + numbers[i] // накопичуємо суму
}
return prefix
}
Зверніть увагу на i + 1. Це не «костиль», а прямий наслідок домовленості prefix[i] = сума numbers[0..<i]. Коли ми додаємо елемент numbers[i], сума вже належить до діапазону 0..<(i + 1), тобто індекс у prefix — це i + 1.
3. Сума на діапазоні за O(1)
Включний діапазон [l, r]
Тепер найсмачніше: як швидко отримати суму відрізка. Припустімо, нас питають про включний діапазон [l, r] (обидва кінці включені). Тоді:
- сума numbers[0...r] дорівнює prefix[r + 1]
- сума numbers[0..<l] дорівнює prefix[l]
- отже, сума numbers[l...r] дорівнює prefix[r + 1] - prefix[l]
Ось і вся формула.
Зробімо акуратну функцію, яка повертає Int?, тому що діапазон може бути неправильним. Краще повернути nil, ніж упасти через вихід за межі масиву.
import Foundation
func rangeSum(prefix: [Int], from l: Int, to r: Int) -> Int? {
guard l >= 0, r >= l, (r + 1) < prefix.count else { return nil }
return prefix[r + 1] - prefix[l]
}
Тут важливий момент: ми перевіряємо (r + 1) < prefix.count, тому що звертаємося до prefix[r + 1]. Якщо забути про цей +1, можна отримати помилку меж — і це буде найприкріший баг, бо «ніби ж усе правильно».
Напіввідкритий діапазон [l, r)
Іноді задача формулюється в термінах [l, r), тобто лівий край включено, а правий — ні. Наприклад: «сума елементів з індексу 3 до індексу 7, не включаючи 7». Тоді формула ще простіша:
sum(numbers[l..<r]) = prefix[r] - prefix[l]
Зверніть увагу: тут немає +1, тому що r уже є межею після останнього елемента.
import Foundation
func rangeSumHalfOpen(prefix: [Int], from l: Int, toExclusive r: Int) -> Int? {
guard l >= 0, r >= l, r < prefix.count else { return nil }
return prefix[r] - prefix[l]
}
На практиці вибір між [l, r] і [l, r) найчастіше визначається формулюванням задачі або вже наявним кодом. Головне — не змішувати обидва стилі в одному проєкті абияк.
Приклад: багато запитів суми в консольному застосунку
Давайте зберемо маленьку «утиліту аналітики масиву». Ми вже вміємо читати ввід, split, Int(...) і ??, тож зробімо такий сценарій:
1) читаємо n
2) читаємо n чисел
3) будуємо prefix
4) читаємо q запитів, кожен запит — l r (включний діапазон)
5) друкуємо суму або 0, якщо запит неправильний
import Foundation
let n = Int(readLine() ?? "") ?? 0
let numbers = (readLine() ?? "")
.split(separator: " ")
.map { Int($0) ?? 0 }
let prefix = prefixSums(of: numbers)
let q = Int(readLine() ?? "") ?? 0
for _ in 0..<q {
let parts = (readLine() ?? "").split(separator: " ")
let l = parts.count > 0 ? (Int(parts[0]) ?? -1) : -1
let r = parts.count > 1 ? (Int(parts[1]) ?? -1) : -1
print(rangeSum(prefix: prefix, from: l, to: r) ?? 0)
}
Так, це трохи більше ніж 10 рядків, але тут важлива звʼязність сценарію: студент бачить, як усе використовується. Якщо хочеться зробити зовсім «книжково», можна винести парсинг пари індексів в окрему функцію — але ми ще не на тому етапі курсу, де рефакторинг важливіший за розуміння.
4. Де це корисно і скільки коштує
Префіксні суми і sliding window: не одне й те саме
Префіксні суми іноді плутають зі sliding window, бо і там, і там ви швидко рахуєте суми. Різниця в тому, хто ставить запитання.
У режимі фіксованого sliding window ви рахуєте суми всіх вікон довжини k підряд. Це «потоковий» режим: вікно рухається, а ви оновлюєте суму.
У prefix sums ви готуєтеся до того, що запити будуть довільні: сьогодні [3, 10], завтра [0, 0], післязавтра [5, 19]. Тобто це режим «багато запитів до одного й того самого масиву».
Цікавий бонус: через префікси можна так само просто порахувати суму будь-якого фіксованого вікна. Сума вікна довжини k, що починається з start, дорівнює:
prefix[start + k] - prefix[start] (якщо використовуємо напіввідкритий стиль)
import Foundation
func windowSumsUsingPrefix(numbers: [Int], k: Int) -> [Int] {
guard k > 0, numbers.count >= k else { return [] }
let prefix = prefixSums(of: numbers)
var result: [Int] = []
for start in 0...(numbers.count - k) {
result.append(prefix[start + k] - prefix[start]) // сума вікна
}
return result
}
Це не «краще» і не «гірше», ніж running sum у sliding window. Просто інший інструмент. Якщо вам потрібні суми всіх вікон підряд, running sum буде ощадливішим за памʼяттю, бо не зберігає prefix. Якщо prefix уже потрібен для інших запитів, використовувати його і для вікон цілком нормально.
Складність і памʼять
Важливо вміти пояснювати, чому це працює швидко, не вдаючись до магії та віри в удачу.
Побудова prefix робить один прохід по масиву, отже це O(n). Кожен запит суми діапазону — це буквально два звернення за індексом і одне віднімання, отже O(1). Якщо запитів q, то сумарно виходить O(n + q). Порівняно з наївним підходом O(n * q) — якщо підсумовувати діапазон циклом для кожного запиту — різниця може бути величезною.
Ціна за це — памʼять O(n): ми зберігаємо масив prefix довжини n + 1.
Ще один маленький нюанс: ми використовуємо Int, і в рідкісних задачах сума може переповнитися — особливо якщо числа великі й n теж великий. Для навчальних задач це зазвичай не критично, але в міру дорослішання проєктів ви памʼятатимете, що числа не безмежні, навіть якщо дуже в них вірити.
Мінісхема: «попереднє обчислення» → швидка відповідь
Щоб закріпити ідею, корисно побачити її як процес: спочатку будуємо, потім відповідаємо. У голові це має жити саме так, інакше ви постійно «випадково» перераховуватимете суми циклом.
flowchart TD
A[Вихідний масив numbers] --> B["Побудувати prefix за O(n)"]
B --> C["Багато запитів sum(l..r)"]
C --> D["Відповідь за O(1): prefix[r+1] - prefix[l]"]
5. Типові помилки під час роботи з префіксними сумами
Помилка № 1: prefix довжини n, а не n + 1.
Це виглядає «економно», але майже завжди призводить до зайвих умов і плутанини. Щойно у вас діапазон починається з нуля, доведеться писати окрему гілку «if l == 0». Із n + 1 та prefix[0] = 0 формула працює однаково для всіх діапазонів, і мозок відпочиває.
Помилка № 2: змішати два способи індексації в одній задачі.
Іноді студент будує prefix[i] = сума numbers[0...i] (включно з i), а потім застосовує формулу prefix[r + 1] - prefix[l], яка розрахована на numbers[0..<i]. У результаті відповіді виходять «майже правильними», а це найгірший тип помилки: тест на маленьких прикладах може пройти. Потрібно один раз вибрати контракт (0..<i) і не змінювати його на ходу.
Помилка № 3: переплутати [l, r] і [l, r).
Якщо задача просить включний діапазон, формула prefix[r] - prefix[l] буде неправильною на один елемент, тому що ви не включили numbers[r]. І навпаки, якщо задача напіввідкрита, а ви робите r + 1, ви зайдете далі, ніж треба. Лікування тут просте, хоч і нудне: спочатку словами написати «діапазон включний» або «правий край не включаємо», а вже потім друкувати формулу.
Помилка № 4: забути, що у формулі для [l, r] використовується r + 1, і не перевірити межі.
Навіть якщо r валідний для numbers, r + 1 має бути валідним для prefix. Саме тому перевірка в guard виглядає трохи незвично: ми порівнюємо з prefix.count, а не з numbers.count. Якщо робити валідацію «на око», ви рано чи пізно натрапите на падіння через вихід за межі масиву на останньому елементі.
Помилка № 5: побудувати prefix, а потім продовжувати підсумовувати діапазони циклом.
Це часта ситуація, коли ідея ще не оселилася в голові. Начебто префікси є, але рука автоматично пише for i in l...r { sum += numbers[i] }. Це не гріх, а просто звичка. Гарна самоперевірка така: якщо ви вже побудували prefix, то в коді відповіді на запит суми не має бути циклу — там мають бути лише індекси й арифметика.
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ