重量区间

算法思路

设前缀和 $s_{0}=0$，$s_{i}=\sum_{j=1}^{i}a_{j}$。

区间 $[l,r]$ 的重量为 $k$，等价于 $s_{r}-s_{l-1}=k$，整理得

因此，从左到右枚举右端点 $r$，只需统计此前有多少个前缀和等于 $s_{r}-k$。

使用哈希表 $\mathrm{cnt}[x]$ 记录已经出现的前缀和 $x$ 的次数。初始令 $\mathrm{cnt}[0]=1$，表示空前缀。

每读入一个元素并更新当前前缀和 $s$，先将 $\mathrm{cnt}[s-k]$ 加入答案，再将 $\mathrm{cnt}[s]$ 增加 $1$。

必须先查询再更新，避免在 $k=0$ 时统计空区间。前缀和、$k$ 和答案统一使用 64 位整数。

正确性证明

处理右端点 $r$ 时，哈希表恰好记录 $s_{0},s_{1},\ldots,s_{r-1}$ 的出现次数。

每个满足 $s_{j}=s_{r}-k$ 的下标 $j<r$，都唯一对应一个重量为 $k$ 的非空区间 $[j+1,r]$。因此，$\mathrm{cnt}[s_{r}-k]$ 正好是以 $r$ 为右端点的合法区间数量。

枚举所有右端点后，每个合法区间恰好被统计一次，所以算法正确。

复杂度分析

每个元素进行常数次哈希表操作，期望时间复杂度为 $O(n)$。

哈希表最多记录 $n+1$ 个不同的前缀和，空间复杂度为 $O(n)$。