Prefix, difference, and hashed state · HTML
Define prefix[0]=0 and prefix[i+1]=prefix[i]+a[i]. The sum of half-open [l,r) is prefix[r]-prefix[l].
Recognition signals
- Many contiguous range sums are queried on one static array.
- Scanning every query would cost O(nq).
- The aggregate has an inverse difference, such as addition or XOR.
- A rectangle query can combine four 2D prefixes by inclusion-exclusion.
False friends
| Signal | Why it is different |
|---|
| Frequent point updates | Changing one value invalidates every later plain prefix; use a Fenwick or segment tree. |
| Range maximum | Max has no inverse subtraction, so two ordinary prefixes cannot recover an arbitrary interval. |
Core invariant
prefix[i] always aggregates exactly the first i elements a[0:i]; i denotes a count, not an original element index.
State, transition, and processing order
| Item | Definition |
|---|
| State | A length-n+1 prefix array, query endpoints l/r, and one consistent half-open interval convention. |
| Transition | During construction set prefix[i+1]=prefix[i]+a[i]; during a query subtract the left prefix from the right prefix. |
| Frontier / order | Construction advances left to right; after it finishes, all range queries are independent. |
Python skeleton
def build_prefix(values):
prefix = [0]
for value in values:
prefix.append(prefix[-1] + value)
return prefix
def range_sum(prefix, left, right):
# Sum over half-open interval [left, right).
if not (0 <= left <= right < len(prefix)):
raise IndexError('invalid range')
return prefix[right] - prefix[left]
Correctness sketch
- Induction on the recurrence gives prefix[i]=a[0]+…+a[i-1].
- prefix[r] consists of [0,l) plus [l,r); subtracting prefix[l] cancels the shared first part exactly.
- A query reads two verified prefixes and therefore returns the precise interval aggregate.
Complexity
| Time | Space | Parameters |
|---|
| O(n) preprocessing and O(1) per query | O(n) | n is array length; q queries total O(n+q). |
Edge cases
- An empty interval l=r sums to zero.
- The whole interval [0,n) is prefix[n]-prefix[0].
- A closed interval [l,r] uses prefix[r+1]-prefix[l].
- Cumulative values may overflow fixed-width integers.
Error patterns
| Pattern | Why it fails / fix |
|---|
| Building only n prefix slots | Without the leading zero, l=0 needs special handling and off-by-one risk rises. |
| Mixing closed and half-open ranges | Write [l,r) or [l,r] explicitly before using a formula. |
| Rebuilding after every update | Frequent changes require a dynamic range structure. |
Selection and exclusion rules
- Use prefixes for many static range queries with an invertible aggregate.
- For a single query, a direct scan may be cheaper overall.
- For interleaved updates and queries, use a Fenwick or segment tree.
Original micro-example
| Part | Detail |
|---|
| Result | The interval sum is 5. |
| Setup | Values [3,-1,4,2], query half-open [1,4). |
| Trace | prefix=[0,3,2,6,8]; compute 8-3. |
Recall prompts
My notes