如何在O(1)时间统计子数组中1的个数？前缀和方法问题求助

你当前的前缀和数组定义方式有误，导致起始索引为0的子数组计算结果错误。正确的前缀和数组需要前置一个0元素，具体实现如下：

正确的前缀和构建方法 #

• 设原数组长度为n，创建长度为n+1的前缀和数组prefix，其中prefix[0] = 0
• 遍历原数组，对每个索引i（从0到n-1），计算prefix[i+1] = prefix[i] + 原数组[i]

以你的原数组为例：
原数组：[1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1]
正确的前缀和数组应为：[0, 1, 1, 1, 2, 3, 3, 4, 4, 4, 5, 6, 6, 7]

子数组1的个数计算方式 #

对于任意子数组（起始索引start，结束索引end，闭区间），1的个数计算公式为：

prefix[end + 1] - prefix[start]

验证你的示例：
子数组起始索引0、结束索引3，计算prefix[4] - prefix[0] = 2 - 0 = 2，与实际结果一致。

再举一个测试案例：子数组索引3到5（元素[1,1,0]），1的个数为2，计算prefix[6] - prefix[3] = 3 - 1 = 2，结果正确。

时间复杂度 #

• 预处理构建前缀和数组：O(n)
• 每次查询子数组1的个数：O(1)
  完全符合你的需求。

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