Поточна сума — це сума послідовності елементів оновлювана кожного разу коли послідовність змінюється, тобто додається новий або видаляється чи змінюється старий елемент. Нова поточна сума обчислюється використовуючи значення попередньої за сталий час.

Є дві причини зберігати значення поточної суми. По-перше, це дозволяє дізнаватись цю суму будь-коли без додавання всіх елементів послідовності. По-друге, це може зберегти місце, якщо нам не потрібно знати елементи послідовності, то ми можемо зберігати лише їхню поточну суму.

Узагальнюючи, можна обчислювати поточну суму лише для елементів, що задовольняють певну умову, наприклад, додавати лише елементи, що діляться на 3, або елементи, які більше 1000. Також можна накласти умову на позицію елемента, наприклад, сумувати тільки елементи в парних позиціях.

Поточну суму можна обчислювати і для рядків, де додавання нового рядка викливає конкатенацію до поточної суми, але підтримувати це значення у разі дій над вже наявними рядками складно.

Див. також
* Дерево Фенвіка

Примітки


