如何优化无序列表区间正整数计数的查询效率？

核心思路：前缀和数组 #

把原来每次遍历区间求和的O(n)查询复杂度，降到O(1)，只需要一次O(n)的预处理：

1. 构建前缀和数组

   • 先把原列表转换成0-1数组：正数对应1，非正数对应0。
   • 生成前缀和数组prefix，其中prefix[0] = 0，prefix[i]表示原0-1数组前i个元素的累加和（也就是原列表前i个元素中正数的总个数）。
   • 示例：原列表[2,-1,2,-2,3]转成0-1数组是[1,0,1,0,1]，对应的前缀和数组为[0,1,1,2,2,3]。

2. 快速计算区间结果
   对于1-based的查询区间[L, R]，直接用公式：

   结果 = prefix[R] - prefix[L-1]
   

   对应示例中的查询：

   • 区间[1,1]：prefix[1] - prefix[0] = 1 - 0 = 1
   • 区间[1,3]：prefix[3] - prefix[0] = 2 - 0 = 2
   • 区间[2,4]：prefix[4] - prefix[1] = 2 - 1 = 1
   • 区间[1,5]：prefix[5] - prefix[0] = 3 - 0 = 3
     完全匹配预期输出。

性能对比 #

• 原方法：每次查询遍历区间，总时间复杂度O(k*n)，当n和k都较大（比如1e5级别）时会严重超时。
• 前缀和方案：预处理O(n)，每次查询O(1)，总时间复杂度O(n + k)，能轻松应对大规模数据。

其他可选方案（按需选择） #

如果后续需要支持动态修改原列表元素（比如更新某个位置的数值后重新查询），前缀和就不适用了，这时可以用线段树或树状数组，它们的查询和更新复杂度都是O(logn)，适合有动态修改需求的场景。但如果只是静态查询，前缀和是最简单高效的选择。

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