327-区间和的个数(Count of Range Sum)

原文链接: https://leetcode-cn.com/problems/count-of-range-sum

英文原文

Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive.

Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.

Example 1:

Input: nums = [-2,5,-1], lower = -2, upper = 2
Output: 3
Explanation: The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.

Example 2:

Input: nums = [0], lower = 0, upper = 0
Output: 1

Constraints:

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
-10⁵ <= lower <= upper <= 10⁵
The answer is guaranteed to fit in a 32-bit integer.

中文题目

给你一个整数数组 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 位 的整数

通过代码

高赞题解

忽略官方题解中的方法一，剩余的四种方法分别使用了线段树、树状数组和平衡树。这些方法都不是面试的考点，甚至在笔试中也很少出现，所以大部分读者应该是完全不知道这些都是啥神奇的数据结构的。所以我觉得这里有必要补充以下两点：

这道题需要哪些接口。
上面的这些神奇的数据结构可以提供哪些接口。

题目描述

给定数组 $A$，它的长度为 $n$，对应的元素以及下标为 $A[0], A[1], \cdots, A[n-1]$。

令 $S(i, j)$ 为 $A[i]$ 到 $A[j]$ 的和，即

$$
S(i, j) = \sum_{k=i}^j A[k]
$$

题目需要求出满足 $\textit{lower} \leq S(i, j) \leq \textit{upper}$ 的二元组 $(i, j)$ 的个数。

换成人话就是，问数组 $A$ 有多少个连续的子数组，其元素只和在 $[\textit{lower}, \textit{upper}]$ 的范围内。

题目分析

暴力的做法是使用前缀和。令 $P$ 为 $A$ 的前缀和数组，那么

$$
S(i, j) = P[j] - P[i-1]
$$

可以在 $O(1)$ 的时间求出。这里我们规定边界 $P[-1] = 0$。

这样一来，我们枚举所有的二元组 $(i, j)$，算出 $S(i, j)$ 并判断其是否在范围内即可。时间复杂度为 $O(n^2)$。

那么怎么进行优化呢？我们考虑从小到大枚举 $j$，由于

$$
\textit{lower} \leq P[j] - P[i-1] \leq \textit{upper}
$$

我们可以得到 $P[i-1]$ 应该满足的不等式

$$
P[j] - \textit{upper} \leq P[i-1] \leq P[j] - \textit{lower}
$$

因此本质上，我们需要一个数据结构支持下面的两个操作：

操作 $1$「查询」：给定一个范围 $[\textit{left}, \textit{right}]$，查询数据结构中在该范围内的元素个数。对应到本题中，我们给定的范围就是 $\big[P[j] - \textit{upper}, P[j] - \textit{lower}\big]$；
操作 $2$「更新」：给定一个元素 $x$，我们需要把它添加到数据结构中。对应到本题中，我们给定的元素就是 $P[j]$。

如果有了这样一个数据结构，我们就可以很方便地做出本题：

我们首先将 $0$ 放入数据结构中，随后我们从小到大枚举 $j$，查询 $\big[P[j] - \textit{upper}, P[j] - \textit{lower}\big]$ 范围内的元素个数并计入答案。在查询完成之后，我们将 $P[j]$ 添加进数据结构，就可以进行下一次枚举。

频数数组

很多数据结构都是基于「频数数组」。

给定数组 $t$ 以及它的下标范围 $[L, R]$，$t[x]$ 就表示元素 $x$ 在数据结构中的出现次数。基于此，上述的两个操作可以变为：

操作 $1$「查询」：给定一个范围 $[\textit{left}, \textit{right}]$，查询 $t[\textit{left}]$ 到 $t[\textit{right}]$ 的和；
操作 $2$「更新」：给定一个元素 $x$，将 $t[x]$ 增加 $1$。

这也是线段树和树状数组的基础，它们需要的空间都与数组 $t$ 的下标范围 $[L, R]$ 正相关。在本题数据规模较大的情况下（例如测试数据中，出现了元素值达到 $32$ 位有符号整数的上下界），线段树和树状数组都会超出空间限制，因此需要借助「离散化」操作，将这些元素映射到一个较小规模的区间内。

离散化

给定数组元素 $[1, 22, 333, 4444, 55555]$，如果我们只关注它们之间的大小关系，那么该数组其实和 $[1, 2, 3, 4, 5]$ 是等价的。

这就是离散化的技巧。我们将所有会涉及到比较操作的数全部放入一个列表中，进行排序，再从小到大依次给它们赋予一个新的值。在离散化完成后，任何两个数之间的相对大小都不会改变，但是元素的上下界范围被限制住，这使得我们可以方便地使用一些数据结构。

在本题中，我们可以将所有的 $P[j], P[j] - \textit{upper}, P[j] - \textit{lower}$ 一起进行离散化，并将它们从小到大，依次赋予一个从 $1$ 开始的整数值。这样一来，我们所有涉及到的元素值都会在 $[1, 3(n+1)]$ 的范围内。

线段树

当我们将元素离散化后，就可以直接使用线段树了。最基础的线段树恰好就支持这两种操作：

操作 $1$「查询」：给定一个范围 $[\textit{left}, \textit{right}]$，查询 $t[\textit{left}]$ 到 $t[\textit{right}]$ 的和；
操作 $2$「更新」：给定一个元素 $x$，将 $t[x]$ 增加 $\delta$。

我们只需要时刻令 $\delta=1$ 即可。两种操作的时间复杂度均为 $O(\log n)$。

树状数组

当我们将元素离散化后，也可以直接使用树状数组了。最基础的树状数组支持这两种操作：

操作 $1$「查询」：给定一个下标 $\textit{right}$，查询 $t[1]$ 到 $t[\textit{right}]$ 的和（即前缀和）；
操作 $2$「更新」：给定一个元素 $x$，将 $t[x]$ 增加 $\delta$。

我们只需要时刻令 $\delta=1$ 即可，并且通过调用操作 $1$ 两次（即 $\textit{right}$ 和 $\textit{left}-1$）相减得到 $t[\textit{left}]$ 到 $t[\textit{right}]$ 的和。两种操作的时间复杂度均为 $O(\log n)$。

平衡树

平衡树实际上就是「平衡」的二叉搜索树，它与线段树和树状数组不同，并且它不需要借助离散化操作。支持的操作（在本题中会使用到的）主要有以下几种：

操作 $1$「lower bound」：给定一个元素 $x$，查询平衡树中最小的大于等于 $x$ 的元素；
操作 $2$「upper bound」：给定一个元素 $x$，查询平衡树中最小的大于 $x$ 的元素；
操作 $3$「rank」：给定一个元素 $x$（它必须在平衡树中），求它是第几小的元素。当存在重复元素时，会计入多次；
操作 $4$「insert」：给定一个元素 $x$，将它放入平衡树中。

所有操作的时间复杂度均为 $O(\log n)$。大部分语言自带的平衡树支持操作 $1$ 和 $2$ 和 $4$ 但不支持操作 $3$。

那么对于本题中需要的两种操作：

「查询」：我们令 $u = P[j] - \textit{upper}$，$v = P[j] - \textit{lower}$。对 $u$ 使用操作 $1$ 得到 $u’$，对 $v$ 使用操作 $2$ 得到 $v’$。我们再使用操作 $3$ 得到 $u’$ 的 rank $r_u$ 以及 $v’$ 的 rank $r_v$，那么 $r_v’-r_u’$ 就是 $\big[P[j] - \textit{upper}, P[j] - \textit{lower}\big]$ 中的元素个数。
「更新」：我们对 $x$ 使用操作 $4$ 即可。

学习方法

关于这些竞赛难度的知识点，我建议读者在学有余力的情况下学习。这些知识点对面试几乎没有任何帮助；相反，在没有完全掌握这些知识点的前提下，可能会影响读者原本正常的思维，产生「看什么题都是线段树」之类的后果。

这里我推荐两个参考资料：

OI Wiki，是一个信息学竞赛爱好者用爱发电的算法小百科。
ac-library，是日本著名算法竞赛平台 AtCoder 整理的算法模板，但其中没有平衡树。

读者也可以参考其它互联网上的博客。线段树、树状数组和平衡树在算法竞赛圈中是非常基础的知识点，优质的博客数量也很多。

统计信息

通过次数	提交次数	AC比率
25525	60940	41.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
计算右侧小于当前元素的个数	困难
翻转对	困难

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途