A prefix sum is the total of the first several entries in an ordered sequence. Store one total at each boundary of an array, and a backtest or ledger report can sum any contiguous window with two lookups and one subtraction.
Put the totals at the boundaries
For cash flows indexed from through , let be the total strictly before boundary . Start with , then build the other entries using . There are totals, including for the whole array. This is an exclusive prefix convention with the full total appended. Blelloch describes inclusive and exclusive scans.
The half-open window starts at entry and stops before entry . The prefix at contains the window and everything before it. Subtract the prefix at to remove everything before the window.
A window starting at zero uses the same formula because . When , both lookups read the same total and the empty window sums to zero.
Net cash in a window
Take a fictional single-currency ledger with flows in USD, with inflows positive. The boundary totals are . The query includes entries 1 and 2, so the net flow is USD. Adding the entries directly gives USD.
The two prefixes share the first cash flow. Subtracting the shorter prefix cancels that overlap.
These are undiscounted cash amounts in a common currency. Across successive periods, simple investment returns compound by multiplying gross returns. See time-weighted return for how performance calculations link subperiod returns across external cash flows.
The same running total can count displayed shares across the price levels of a frozen order book. The SelfMadeQuant Order Books lesson uses cumulative depth to work out the cost of a hypothetical fill. The preview is public and the full lesson requires membership.
What changes when the data change?
For a fixed array, building the prefix totals takes time and extra space, and each window sum takes time. A correction to entry changes every stored prefix at boundaries , so a correction near the start can take work. A Fenwick tree handles single-entry additions and range sums in time per operation. Laaksonen covers both cases in Chapter 9.
Adding an amount to every entry in a window is a different update. If all such updates arrive before any queries, a difference array can record each addition at its start and cancel it at its exclusive end, then a single prefix pass recovers the per-entry changes. When window additions and window-sum queries arrive interleaved, a segment tree with lazy propagation can handle both in per operation. Laaksonen explains lazy propagation in Chapter 28.
Sources
- Guy E. Blelloch, Prefix Sums and Their Applications, §1.1. Scan and prescan conventions.
- Antti Laaksonen, Competitive Programmer’s Handbook, Chapter 9. Static range sums, binary indexed trees and difference arrays.
- Antti Laaksonen, Competitive Programmer’s Handbook, Chapter 28. Range updates and sums with lazy propagation.