Prefix, difference, and hashed state · HTML
To add delta on closed [l,r], do diff[l]+=delta and diff[r+1]-=delta when represented. Finally a[i]=base[i]+Σ_{j≤i}diff[j].
Recognition signals
- There are many range additions or subtractions and results are read only after all updates.
- Each update applies one uniform delta to a contiguous interval.
- Only final point values, maximum coverage, or capacity violations matter.
- Touching every position for every update would cost O(nq).
False friends
| Signal | Why it is different |
|---|
| Querying immediately after each update | Unintegrated diff cannot answer current values directly; use a Fenwick or segment tree for online operations. |
| Range assignment | Overwrite priority is not simple additive superposition, so two endpoint deltas are insufficient. |
Core invariant
diff stores changes between adjacent real values; a range delta begins at l and is canceled completely at r+1.
State, transition, and processing order
| Item | Definition |
|---|
| State | A length-n or n+1 difference array, endpoints, delta, and running prefix during reconstruction. |
| Transition | Write two events per update; after all updates, scan left to right with running+=diff[i] and apply it to output. |
| Frontier / order | Updates have no pointwise frontier; during reconstruction, running is the sum of intervals that have started but not yet ended. |
Python skeleton
def apply_range_adds(length, updates):
diff = [0] * (length + 1)
for left, right, delta in updates:
if not (0 <= left <= right < length):
raise IndexError('invalid update')
diff[left] += delta
diff[right + 1] -= delta
result = [0] * length
running = 0
for i in range(length):
running += diff[i]
result[i] = running
return result
Correctness sketch
- For one [l,r] update, its prefix contribution is zero before l, delta throughout l..r, and zero again after the negative event at r+1.
- Linearity lets events from many updates add in any order.
- The final prefix at each coordinate sums exactly all update intervals covering that coordinate.
Complexity
| Time | Space | Parameters |
|---|
| O(q+n) | O(n) | q is update count and n coordinate length; each update is O(1), reconstruction O(n). |
Edge cases
- For zero length, the update collection must be empty.
- An n+1 sentinel permits writing diff[right+1] even when right=n-1.
- Negative deltas are valid.
- For a nonzero base array, add reconstructed deltas to base[i].
Error patterns
| Pattern | Why it fails / fix |
|---|
| Omitting cancellation at r+1 | The delta incorrectly leaks to every later coordinate. |
| Mixing closed and half-open endpoints | Closed [l,r] cancels at r+1; half-open [l,r) cancels at r. |
| Reading diff directly | diff is a derivative and must be prefix-integrated into point values. |
Selection and exclusion rules
- Use differences for offline batched range additions followed by one final read.
- A Fenwick tree can online the same derivative idea for point queries.
- Use a segment tree for online range aggregates or more complex updates.
Original micro-example
| Part | Detail |
|---|
| Result | The increment array is [0,4,6,6,2]. |
| Setup | Length 5; add 4 on [1,3] and 2 on [2,4]. |
| Trace | Events are +4@1,-4@4,+2@2,-2@5; integrate left to right. |
Recall prompts
My notes