What is the main pattern used in Count of Range Sum?

The key pattern is 'binary search over the valid answer space', combined with prefix sums and merge sort to count subarrays efficiently.

Can this problem be solved without merge sort?

Yes, segment trees or binary indexed trees can be used to query prefix sum ranges dynamically, still achieving O(n log n) complexity.

Why is prefix sum necessary here?

Prefix sums allow computing any subarray sum as a simple difference, reducing the problem from O(n^2) enumeration to a more efficient approach.

What common mistakes cause incorrect counts?

Off-by-one errors, failing to include negative sums, and mismanaging overlapping ranges during merge or binary search are frequent pitfalls.

What constraints affect solution choice?

Large array sizes up to 10^5 and sum ranges up to ±10^5 require O(n log n) methods; naive O(n^2) approaches are infeasible.

#327

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

区间和的个数

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper ）之内的区间和的个数。区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j ( i ≤ j …

数组二分查找分治树状数组线段树

题目描述

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。

区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

示例 1：

输入：nums = [-2,5,-1], lower = -2, upper = 2
输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。

示例 2：

输入：nums = [0], lower = 0, upper = 0
输出：1

提示：

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
-10⁵ <= lower <= upper <= 10⁵
题目数据保证答案是一个 32 位 的整数

lightbulb

解题思路

方法一：前缀和 + 树状数组

题目要求区间和，因此我们可以先求出前缀和数组 $s$ ，其中 $s[i]$ 表示 $nums$ 中前 $i$ 个元素的和。那么对于任意的 $i \lt j$ ， $s[j+1] - s[i]$ 就是 $nums$ 中下标在 $[i, j]$ 的元素之和。

而 $lower \leq s[j+1] - s[i] \leq upper$ ，可以转换为 $s[j+1] - upper \leq s[i] \leq s[j+1] - lower$ ，也就是说，对于当前前缀和 $s[j+1]$ ，我们需要统计 $s$ 中有多少个下标 $i$ 满足 $s[j+1] - upper \leq s[i] \leq s[j+1] - lower$ 。

我们可以用树状数组来维护每个前缀和出现的次数，这样对于每个前缀和 $s[j+1]$ ，我们只需要查询树状数组中有多少个前缀和 $s[i]$ 满足 $s[j+1] - upper \leq s[i] \leq s[j+1] - lower$ 即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x, v):
        while x <= self.n:
            self.c[x] += v
            x += x & -x

    def query(self, x):
        s = 0
        while x > 0:
            s += self.c[x]
            x -= x & -x
        return s


class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        s = list(accumulate(nums, initial=0))
        arr = sorted(set(v for x in s for v in (x, x - lower, x - upper)))
        tree = BinaryIndexedTree(len(arr))
        ans = 0
        for x in s:
            l = bisect_left(arr, x - upper) + 1
            r = bisect_left(arr, x - lower) + 1
            ans += tree.query(r) - tree.query(l - 1)
            tree.update(bisect_left(arr, x) + 1, 1)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask about handling negative numbers in subarray sums.
question_mark
Probe understanding of prefix sums and why merge sort helps avoid double counting.
question_mark
Expect recognition of binary search over cumulative sums as the core optimization.

warning

常见陷阱

外企场景

error
Attempting brute-force O(n^2) sum enumeration on large arrays causes timeouts.
error
Neglecting proper handling of overlapping ranges during merge can undercount valid sums.
error
Failing to correctly compute prefix sum differences when applying binary search leads to off-by-one errors.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count of Range Sum where multiple queries on different ranges are performed, requiring dynamic updates.
arrow_right_alt
Counting subarrays with product in a range instead of sum, which changes the aggregation technique.
arrow_right_alt
Counting ranges with additional constraints, like length limits or modulo conditions.

help

常见问题

外企场景

继续练习

#315 计算右侧小于当前元素的个数 #493 翻转对 #1649 通过指令创建有序数组