如何高效统计每个元素所属子数组个数 含0和平衡子数组问题

你提到的标记后前缀和求解的方法是差分数组法，可以将区间计数的时间复杂度从暴力的O(kn)（k为区间数量，n为数组长度）降到O(k + n)，完全避免超时问题，实现逻辑如下：

1. 初始化长度为n+1的差分数组diff，所有元素初始值为0
2. 对每个闭区间(l, r)，执行两个操作：
   • diff[l] += 1
   • diff[r + 1] -= 1
3. 对diff数组计算前缀和，前n个元素就是每个位置被区间包含的次数

用你给出的示例验证：

• 数组长度n=5，初始diff = [0,0,0,0,0,0]
• 四个区间操作后得到diff = [2,1,1,-1,-2,-1]
• 前缀和计算结果为[2,3,4,3,1]，和预期输出完全一致

你要统计每个元素被多少个和为0的子数组包含，不需要枚举所有平衡子数组再逐个打标记（极端情况如全0数组会产生O(n²)个平衡子数组，依然会超时），可以结合前缀和性质和差分数组，做到O(n)时间复杂度求解，思路如下：

核心前提 #

我们知道前缀和s[0] = 0，s[i]为原数组前i个元素的和，子数组[l, r]（0≤l≤r<n）和为0等价于s[r+1] = s[l]。
我们用哈希表存储所有相同前缀和的下标列表，比如key为前缀和的值，value为严格递增的下标列表arr = [a0, a1, ..., am-1]，所有由该前缀和生成的平衡子数组都对应[a_p, a_q -1]（q>p）的区间。

批量差分操作 #

如果枚举所有q>p的区间再操作差分数组，最坏是O(n²)复杂度，我们可以批量计算所有区间对差分数组的贡献：

1. 对每个前缀和对应的下标列表arr，长度为m：
   • 对每个位置p（0≤p<m），diff[a_p] += (m - p - 1)：每个a_p作为左端点，可以匹配m-p-1个右端点，对应区间的左标记加1
   • 对每个位置q（0≤q<m），diff[a_q] -= q：每个a_q作为右端点的r+1位置，对应q个左端点，区间的右标记减1
2. 所有组处理完成后，对diff数组求前缀和，前n个元素就是每个位置被平衡子数组包含的次数

这个方法所有操作的总时间复杂度为O(n)，因为所有前缀和下标列表的总长度为n+1，没有额外冗余计算。

内容的提问来源于stack exchange，提问作者Hai