Prefix Sum Reset Logic

Reset logic appears when a running aggregate must snap back to zero (or another baseline) after events like newline boundaries, session timeouts, or game level restarts—model this by tracking segment starts or subtracting previous segment totals.

Why this shows up in the real world

Pedometer apps reset daily step counts at midnight—your “prefix since wake” is really a piecewise prefix with daily resets. Call-center SLA timers reset per ticket. Telemetry burst detectors restart baseline after a quiet window.

Core idea (explained for students)

Technique A: store (segment_id, pref_within_segment) pairs. Technique B: when a reset condition hits, push the current absolute prefix into a stack or subtract it from future calculations. Technique C: difference array + prefix encodes resets as sharp -current spikes at reset indices.

Try this in Python

def segmented_prefix(a: list[int], reset_after_negative: bool) -> list[int]:
    out, cur = [], 0
    for x in a:
        cur += x
        if reset_after_negative and cur < 0:
            cur = 0
        out.append(cur)
    return out


print(segmented_prefix([2, -5, 3, 1], True))

Common mistakes

• Double-counting elements right at the reset boundary.
• Losing monotonicity proofs when resets interact with greedy choices.
• Off-by-one when midnight aligns with UTC vs local time in real systems.

Key takeaways

• Explicitly name your state variables at and after resets.
• Tests should include back-to-back resets and empty segments.
• Consider whether resets are global or per-key (per user).