foundation
Префиксные суммы
Предвычисляйте cumulative totals или counts, чтобы range queries стали разностями за O(1).
Prefix sums хранят cumulative totals, поэтому range sum становится разницей двух checkpoints. Та же идея работает для counts, balances, XOR и two-dimensional grids. Она особенно полезна, когда много range queries иначе повторяли бы один и тот же scan.
На интервью: Интервьюеры ожидают clear indexing, initial zero prefix и сравнение preprocessing cost с экономией на queries.
Типовые ошибки: Off-by-one ошибки часты. Prefix sums помогают immutable query workloads, но менее удобны при многих point updates; тогда лучше Fenwick или segment trees.
Чеклист: