前缀和算法解析：牛客网NC20242区间统计问题
1. 项目背景与核心价值
"小红统计区间"是牛客网算法题库中的一道经典题目，编号为NC20242。这道题在编程面试准备阶段具有极高的训练价值，尤其适合准备校招笔试和算法竞赛的初学者。作为一道被标记为"easy"难度的题目，它能够帮助学习者快速掌握前缀和算法的核心思想。
我在刷题过程中发现，很多初次接触区间统计问题的同学容易陷入暴力求解的误区。这道题的精妙之处在于，它用看似简单的题干（给定一个数组和区间范围，统计满足条件的子区间数量），引导我们思考如何用O(n)时间复杂度替代O(n²)的暴力解法。
2. 问题描述与抽象建模
2.1 原始题目描述
给定一个长度为n的数组a，以及两个整数L和R。要求统计数组中连续子数组（即子区间）的个数，这些子数组的元素和大于等于L且小于等于R。
输入示例：
a = [1,2,3] L = 2 R = 3输出示例：
3解释：满足条件的子区间为[1,2]（和为3）、[2]（和为2）、[3]（和为3）
2.2 问题抽象化
这个问题可以抽象为：在给定数组的所有连续子区间中，找出满足sum ∈ [L, R]的区间数量。关键在于如何高效计算这些区间，避免O(n²)的暴力枚举。
3. 算法思路解析
3.1 暴力解法及其缺陷
最直观的解法是双重循环枚举所有子区间：
count = 0 n = len(a) for i in range(n): current_sum = 0 for j in range(i, n): current_sum += a[j] if L <= current_sum <= R: count += 1 return count时间复杂度O(n²)，当n较大时（如1e5）会超时。
3.2 前缀和优化思路
前缀和（Prefix Sum）是解决区间求和问题的利器。我们预处理一个前缀和数组prefix，其中prefix[i]表示a[0]到a[i-1]的和。这样任意区间[i,j]的和可以表示为prefix[j+1] - prefix[i]。
但直接应用前缀和仍需双重循环，我们需要更聪明的办法。
3.3 数学转换技巧
将问题拆解为：
- 计算区间和≤R的数量（记为count_R）
- 计算区间和<L的数量（记为count_L）
- 最终结果 = count_R - count_L
这样就将原问题转化为两个更易处理的子问题。
4. 最优解法实现
4.1 基于前缀和的有序统计
使用归并排序的思想统计前缀和的有序性：
def countRangeSum(nums, lower, upper): prefix = [0] for num in nums: prefix.append(prefix[-1] + num) def merge_sort(l, r): if l == r: return 0 mid = (l + r) // 2 count = merge_sort(l, mid) + merge_sort(mid+1, r) # 统计满足条件的区间数 i = j = mid + 1 for left in prefix[l:mid+1]: while i <= r and prefix[i] - left < lower: i += 1 while j <= r and prefix[j] - left <= upper: j += 1 count += j - i # 合并两个有序数组 prefix[l:r+1] = sorted(prefix[l:r+1]) return count return merge_sort(0, len(prefix)-1)4.2 时间复杂度分析
采用分治策略后，时间复杂度降至O(n log n)，空间复杂度O(n)。这是目前最优的解决方案。
5. 代码实现细节
5.1 边界条件处理
特别注意几个关键边界：
- 空数组情况
- L > R的情况
- 整数溢出问题（当元素值很大时）
5.2 测试用例设计
完整的测试应包含：
test_cases = [ ([], 0, 0, 0), # 空数组 ([1,2,3], 2, 3, 3), # 示例 ([1,1,1], 1, 2, 5), # 重复元素 ([-1,-2,-3], -3, -2, 3), # 负数情况 ([10**9]*1000, 10**9, 10**9, 1000) # 大数据测试 ]6. 同类问题扩展
掌握这个解法后，可以解决一系列变种问题：
- 乘积小于K的子数组个数（LeetCode 713）
- 和等于K的子数组个数（LeetCode 560）
- 最接近K的子数组和（LeetCode 363）
7. 刷题经验分享
在牛客网刷题时，我有几个实用建议：
- 先自己思考20分钟再查看题解
- 对每道题记录3种解法：暴力→优化→最优
- 建立错题本，记录错误原因和突破点
- 定期复习已AC的题目，确保真正掌握
这道题教会我们：看似简单的区间统计问题，往往蕴含着精妙的算法思想。前缀和+分治的组合拳，是解决这类问题的利器。