哈希

0 Prefix Sum Basic 0.1 前缀和定义（1-indexed） 数列前n项和： 1-indexed: $$\text{prefixSum}[i] = \sum_{j=1}^{i} a[j] = a[i] = a[1] + a[2] + \cdots + a[i]$$ 0-indexed: $$\text{prefixSum}[i] = \sum_{j=0}^{i-1} a[j] = a[i]= a[0] + a[1] + \cdots + a[i-1]$$ 前缀和分为两类： 类型 预处理 查询 一维前缀和 $O(n)$ $O(1)$ 二维前缀和 $O(nm)$ $O(1)$ 区间和公式： 1-indexed：$\text{sum(l, r) = prefixSum[r] - prefixSum[l - 1]}$ 0-indexed：$\text{sum(l, r) = prefixSum[r + 1] - prefixSum[l]}$ 适用场景: 数组不变(静态),多次查询区间和 → 前缀和 数组会被修改 → 需要树状数组 / 线段树(前缀和不适用) “子数组和满足某条件"的计数问题 → 前缀和 + 哈希表 0.1.1 一维前缀和 区间[l , r]的和：$$\text{sum}(l, r) = S[r] - S[l - 1]$$ ...