Prefix, difference, and hashed state · HTML
If interval (j,i] is valid exactly when relation(P[i],P[j]) holds, query the required historical key while scanning P[i], then insert the current prefix.
Recognition signals
- The task counts or finds intervals with a target sum, equal remainder, balance, or parity state.
- Negative values make sum-based sliding windows nonmonotone.
- An interval property is expressible by subtracting, XORing, or equating two prefixes.
- The requested result is a count, maximum length, or existence of intervals.
False friends
| Signal | Why it is different |
|---|
| One range-sum query | Plain prefix sum is simpler; no historical hash is needed. |
| No compact state encoding | If prefix summaries grow in dimension with n, hash-state storage may be impractical. |
Core invariant
Before processing position i, the table contains exactly the historical prefixes allowed as left boundaries; query-before-insert avoids using a future or self state accidentally.
State, transition, and processing order
| Item | Definition |
|---|
| State | Current prefix P, state-to-frequency for counting or state-to-earliest-index for length, and the accumulated answer. |
| Transition | Update P, derive and query the matching historical key, contribute to the answer, then record current P. |
| Frontier / order | All prefixes to the left of the scan, compressed by state in a hash table rather than expanded as intervals. |
Python skeleton
def count_target_sum(values, target):
prefix = 0
frequency = {0: 1}
answer = 0
for value in values:
prefix += value
answer += frequency.get(prefix - target, 0)
frequency[prefix] = frequency.get(prefix, 0) + 1
return answer
Correctness sketch
- The sum of j..i is P[i+1]-P[j], equal to target exactly when historical P[j]=P[i+1]-target.
- frequency stores the number of eligible occurrences of each historical prefix, so the lookup counts exactly the valid intervals ending here.
- Every interval is counted in the unique iteration for its right endpoint, preventing omissions and duplicates.
Complexity
| Time | Space | Parameters |
|---|
| Expected O(n) | O(n) | n is item count; hashing is expected O(1), with at most n+1 distinct prefix states. |
Edge cases
- Initialize the empty prefix appropriately; sum counting usually starts with {0:1}.
- For target zero, repeated prefixes create multiple intervals.
- Negative values are fully supported and motivate this method over sliding windows.
- For maximum length, store the earliest index and never overwrite it.
Error patterns
| Pattern | Why it fails / fix |
|---|
| Forgetting the empty prefix | Every valid interval starting at index zero is lost. |
| Inserting before querying | Some targets then count a zero-length interval; define and respect boundary semantics. |
| Using the wrong table payload | Counts need frequency; longest length needs earliest index. |
Selection and exclusion rules
- First write interval property = current prefix ○ historical prefix.
- Store frequencies for counts, earliest positions for maximum length, and a set for existence.
- With nonnegative sums and a threshold-length objective, a window may use less space.
Original micro-example
| Part | Detail |
|---|
| Result | There are 3 valid intervals. |
| Setup | Values [2,-2,2], target sum 2. |
| Trace | Prefixes are 2,0,2; each 2 matches a prior zero, and the final 2 has more than one possible left boundary. |
Recall prompts
My notes