Сумма любого куска списка за один шаг

В последних уроках окно двигалось по списку, а сумма обновлялась на ходу. Это работает, когда окно одно и движется в одну сторону. С дашбордом иначе. Он задаёт сотни вопросов, и каждый про свой кусок списка, никак не связанный с другими. Скользящее окно тут не поможет.

У тебя дашборд с метриками. На каждую минуту одно число: запросы, байты, ошибки, что угодно. Пользователь двигает ползунок времени и спрашивает: «сколько всего запросов было с 40-й минуты по 90-ю?» Ты складываешь эти 51 число и показываешь ответ.

Потом он двигает ползунок снова: с 5-й минуты по 800-ю. Ты складываешь 796 чисел. Он двигает ещё раз, и ты снова складываешь новый кусок с нуля. Ползунок выдаёт новый диапазон через каждые несколько пикселей движения мыши. Каждый раз ты заново складываешь тысячи чисел. А можно отвечать на любой вопрос «сумма отсюда досюда» одним вычитанием, какой бы длины ни был диапазон.

На некоторых чеках рядом с каждым товаром печатают ещё и итог на этот момент. Допустим, нужно узнать, сколько вместе стоят три товара из середины чека. Складывать их заново не нужно. Возьми итог, напечатанный после третьего из них, и вычти итог, напечатанный прямо перед первым. Разница и есть цена этих трёх товаров.

На этом всё и держится. Один раз запиши итог на каждой позиции. После этого сумма любого куска равна одному итогу минус другой. Это одно вычитание, какой бы длины ни был кусок.

Пройди список один раз и веди накопленную сумму: после каждого числа записывай сумму всех чисел до него включительно. Назови этот список накопленных сумм prefix.

Главное правило: сумма куска равна накопленной сумме в его конце минус накопленная сумма прямо перед его началом. Всё, что стоит до начала куска, при вычитании пропадает. Остаётся ровно тот кусок, который ты просил.

Чтобы индексы сходились, начни список с нуля, ещё до первого числа. Тогда prefix[0] = 0, а каждая следующая ячейка равна предыдущей плюс очередное число: prefix[i] = prefix[i-1] + nums[i-1]. Теперь prefix[i] означает «сумма первых i чисел». Сумма диапазона от l до r (оба конца включены) равна:

prefix[r+1] - prefix[l]

Благодаря начальному нулю диапазон, который начинается с самой первой позиции, считается по той же формуле, без отдельного случая. Без этого нуля каждый диапазон съехал бы на одну позицию.

Проследим на nums = [2, 4, 1, 3].

• Строим prefix: 0, потом 0 + 2 = 2, потом 2 + 4 = 6, потом 6 + 1 = 7, потом 7 + 3 = 10. Получаем prefix = [0, 2, 6, 7, 10].
• Диапазон [1, 3] (числа 4, 1, 3): prefix[4] - prefix[1] = 10 - 2 = 8. Проверка: 4 + 1 + 3 = 8.
• Диапазон [0, 0] (только 2): prefix[1] - prefix[0] = 2 - 0 = 2.

Ничего не пришлось складывать заново.

Массив prefix строится за один проход по данным: O(n). После этого каждый вопрос про диапазон решается одним вычитанием: O(1). Для q вопросов всё вместе стоит O(n + q).

Память O(n) на сам массив prefix. Ты тратишь место размером с копию данных, и за это вопросы становятся дешёвыми.

Выигрыш заметен, когда вопросов много. Если складывать каждый диапазон вручную, это O(n) на вопрос и O(n·q) всего. Если один раз посчитать prefix, каждый вопрос стоит постоянное время. Разницу видно уже на одном ползунке дашборда.

Дашборды временных рядов и сводки мониторинга считают сумму за любой диапазон дат и не перечитывают исходные строки. Так же работают накопительные отчёты по выручке и использованию. И любой аналитический API, где одни и те же данные запрашивают по множеству разных диапазонов.

Двумерная версия называется «интегральное изображение». Так фильтры изображений считают сумму любого прямоугольника за постоянное время. Это ускоряет размытие и поиск признаков при распознавании лиц. Приём тот же, только измерений на одно больше.