前缀、差分与哈希状态 · HTML
数学 / 逻辑形态
若区间 (j,i] 合法等价于 relation(P[i],P[j])，扫描当前 P[i] 时查询所需历史 key，再把 P[i] 加入表。
识别信号
- 要统计/寻找满足目标和、同余、平衡计数或奇偶状态的连续区间。
- 数组含负数，使滑窗和不再单调。
- 区间属性可由两个前缀相减、异或或状态相等表达。
- 问题要求区间数量、最长长度或是否存在。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 只需一次区间和查询 | 普通 prefix-sum 更简单，无需哈希历史。 |
| 状态无法紧凑编码 | 若前缀摘要维度随 n 增长，哈希状态可能不可行，需要别的结构。 |
核心不变量
处理位置 i 前，哈希表精确保存所有允许作为左边界的历史前缀状态；查询先于插入可避免错误使用未来或自身状态。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 当前前缀 P、历史状态→频次（计数）或最早索引（最长），以及答案。 |
| Transition | 更新当前 P；计算匹配历史 key 并贡献答案；再记录当前 P。 |
| Frontier / order | 扫描位置左侧的全部历史前缀，被哈希表按状态压缩，而非保留所有区间。 |
Python 骨架
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
正确性思路
- 区间 j..i 的和为 P[i+1]-P[j]，等于 target 当且仅当历史前缀为 P[i+1]-target。
- frequency 保存每种合法历史前缀的出现次数，查询值正好是以当前右端结尾的合法区间数。
- 每个区间由其右端那一轮唯一计数，故既不漏也不重。
复杂度
| Time | Space | Parameters |
|---|
| 期望 O(n) | O(n) | n 为元素数；哈希操作按期望 O(1)，不同前缀状态最坏 n+1。 |
边界条件
- 空前缀必须按目标初始化，求和计数通常是 {0:1}。
- target=0 时重复前缀会产生多个区间。
- 负数完全合法，也是本模板相对滑窗的重要场景。
- 求最长时存最早索引，不要覆盖。
错误模式
| Pattern | Why it fails / fix |
|---|
| 忘记空前缀 | 从索引 0 开始的合法区间会全部漏掉。 |
| 先插入再查询 | 某些目标下会把零长度区间错误计入；明确边界语义。 |
| 计数与最长混用存储 | 计数存 frequency，最长存 earliest index，目标不同。 |
选择与排除规则
- 先写区间属性 = 当前前缀 ○ 历史前缀。
- 统计数量存频次；求最长存最早位置；求存在存集合。
- 若只有非负和且求最短/最长阈值，滑窗可能空间更省。
相关模板
| Relation | Template | Boundary |
|---|
| 单调情形替代 | 可变长滑动窗口 | 非负值使 left 可单调移动。 |
原创微型例子
| 环节 | 内容 |
|---|
| Result | 合法区间共有 3 个。 |
| Setup | 值 [2,-2,2]，目标和 2。 |
| Trace | 前缀依次 2,0,2；两次遇到 2 都能匹配历史 0，最后一次还有不同左边界。 |
Recall prompts
我的补充