区间和计数问题详解：前缀和、树状数组与离散化实战（P5459）

上周刷洛谷的时候，碰上了 P5459 [BJOI2016] 回转寿司 这道题。名字看着像模拟，结果是一道非常标准的“区间和计数”问题。我一开始想用双指针滑窗，卡了半天才反应过来，这题里每个寿司的价值 a_i 有正有负，前缀和根本不单调，滑窗直接失效。后来换成“前缀和 + 值域统计”的思路，用树状数组配合离散化才顺利 AC。

这篇文章适合正在备考 CSP/NOIP 的信奥选手，也适合想搞懂“子区间和满足某个取值范围”这类题目通用解法的朋友。我会把从读题到建模型、再到两种主流写法的完整过程都拆开讲，最后还附上我本地调试时踩过的几个坑。

1. 先读懂“回转寿司”到底在问什么

1.1 题目背景和我第一遍读题时的反应

题意可以简单概括成一句话：有一个长度为 n 的数组 a，表示每个寿司的价值（价值可以为负），问有多少个连续子区间，使得这个子区间内所有元素的和落在区间 [L, R] 之间。

我第一次读题的时候，脑子里闪过的第一个念头是“这不就是个双指针滑窗吗”。因为如果是问“和 ≥ K 的子数组个数”，那确实可以用双指针，前提是数组全是非负数。可当你把 a_i 允许为负时，窗口右边扩展并不代表和一定变大，窗口左边收缩也不代表和一定变小。指针移动失去了单调性，双指针就完全没法用了。

我随手试了个例子：a = [1, -3, 5]，如果 L = 1，R = 3，双指针根本没法判断该不该收缩窗口，因为跳过中间的 -3 之后，和反而更可能靠近目标区间。所以这道题真正要解决的不是“怎么滑”，而是“怎么数”。

1.2 为什么看到“区间和”，第一反应必须是前缀和

如果对前缀和这个工具还不熟悉，先花三十秒建立一下直觉：定义一个数组 s，其中 s[0] = 0，s[i] 表示数组 a 前 i 个元素的和。那么区间 [l, r] 的和，就等于 s[r] - s[l-1]。

这个变形看起来很朴素，但它把“连续区间”的问题一下子转换成了“两个前缀和之差”的问题。我们不再枚举每一个区间左端点和右端点，而是把目光集中在所有前缀和上：只要找到所有满足条件的下标对 (i, j)，其中 i < j，并且 L ≤ s[j] - s[i] ≤ R，那么每一对 (i, j) 就唯一对应一个合法区间。

用一个生活化的例子：你有一个记账本，第 i 天的累计余额就是 s[i]。你问“从第 i+1 天到第 j 天一共花了多少钱”，其实就是“第 j 天的累计余额减去第 i 天的累计余额”。现在要统计所有“连续一段时间内消费金额落在 [L, R]”的时间段数量，本质就是在统计“哪两个日期的余额差值落在目标范围内”。

从暴力 O(n²) 枚举区间，到把问题变成统计“前缀和对”，这一步是整个题目的分水岭。只要这一步想明白了，后面就是数据结构的问题了。

2. 卡住我的地方：怎么高效统计满足条件的数对

2.1 把不等式变形，找到“对每一个 j，查什么”

有了前缀和数组 s[i] 之后，对于每一个右端点 j，问题就变为：我们需要统计所有满足下述条件的 i：

L ≤ s[j] - s[i] ≤ R

两边同时减掉 s[j]，再取相反数，可以改写为：

s[j] - R ≤ s[i] ≤ s[j] - L

也就是说，当我们固定了当前的前缀和 s[j]，真正要找的其实是：所有已经出现过的前缀和中，落在区间 [s[j] - R, s[j] - L] 里的有多少个。

这里有一个关键细节：s[i] 对应的 i 必须是严格小于 j 的。也就是说，在处理 s[j] 之前，它自己还不能被统计进数据结构里。我们要维护的是一个“已经扫描过的前缀和集合”，每次查询完当前 s[j] 对应的区间之后，再把 s[j] 插入集合中，供后面的 j 使用。

这个“先查询、后插入”的顺序非常容易错。我一开始写的时候，顺手就把 s[j] 先插进树状数组再查询，结果答案是错的。因为那会把 s[j] - s[j] = 0 这种长度为空的区间也算进去，而且更重要的是，同一个下标被当成 i 和 j 使用了，违反 i < j 的要求。

2.2 动态插入 + 区间查询，数据结构直觉

现在问题变得很清晰了：从左到右扫描前缀和数组，每次需要支持两种操作：

• 插入一个数值 x；
• 查询当前集合中，落在区间 [A, B] 内的数值个数。

这就是典型的“值域统计”问题。朴素做法是开一个数组 cnt，直接按值域下标计数。但本题前缀和的范围可能达到 1e9 级别，直接开数组不现实。于是很自然就想到两种方案：

• 离散化 + 树状数组或线段树；
• 平衡树，比如std::multiset配合二分，或者 pbds 的树。

我最后选了离散化 + 树状数组。原因是常数小、代码短，而且树状数组这种“单点加、前缀查”的模型和本题的“单点插入、区间计数”完全匹配。离散化本质上就是“把值域压缩成排名”，只要把所有可能出现的数收集起来排序，然后把每个原始数值映射成一个排名，就可以在压缩后的空间里做计数了。

3. 树状数组 + 离散化的完整解法

3.1 离散化时最容易漏掉的东西：查询端点

很多第一次写离散化的同学会犯一个经典的错误：只把所有 s[i] 收集起来去重，却忘了把查询区间端点 s[j] - R 和 s[j] - L 也收集进去。

为什么会漏？因为我们不仅要插入 s[i]，还要查询“小于等于某个数的个数”。树状数组的下标必须覆盖所有可能被查询到的位置。如果查询端点没有出现在离散化数组里，再用 lower_bound 去二分时，查到的位置可能是一个“插入位置”，这个位置对应的原始值和实际查询端点并不一致，统计结果就偏了。

正确的做法是先把三类数全部收集到一个 vector 里：

• 所有前缀和 s[0], s[1], ..., s[n]；
• 每个 s[j] - R；
• 每个 s[j] - L。

然后排序去重。这样每个插入值和每个查询边界都有自己明确的位置。实测下来，这个 vector 的总大小最多是 3(n+1) 左右，n ≤ 1e5 时也就 30 万级别，内存和常数都完全没问题。

3.2 左侧端点与右侧端点的二分写法

假设离散化数组是 val，去重后下标从 0 开始。树状数组里真正的索引从 1 开始，所以把一个原始数值 x 映射到树状数组位置时，可以用：

• lower_bound(val.begin(), val.end(), x) - val.begin() + 1得到 x 的排名位置。

对于查询区间 [s[j] - R, s[j] - L]，左端点用上述方法直接定位。右端点稍微有点讲究：我们要统计的是“小于等于 s[j] - L”的个数，所以应该用 upper_bound 找到第一个大于 s[j] - L 的位置，这个位置之前的元素全都满足要求。写成代码就是：

int leftPos = lower_bound(val.begin(), val.end(), s[j] - R) - val.begin() + 1; int rightPos = upper_bound(val.begin(), val.end(), s[j] - L) - val.begin();

注意，rightPos不是直接拿去查询的位置，而是代表“从 val[0] 到 val[rightPos-1] 都满足小于等于”。在树状数组前缀查询里，我们要查的就是前rightPos个位置的总和，所以答案加上：

ans += bitSum(rightPos) - bitSum(leftPos - 1);

为什么右端点不用lower_bound(s[j] - L)然后加一？因为 lower_bound 只找等于的位置，如果当前集合中有很多相同值，用 lower_bound 会精确落在第一个相等的元素上，而我们需要把所有等于的都统计进去，upper_bound 才是“第一个大于”的位置，天然包含了所有相等的元素。这两个二分函数用反，是 WA 的高频原因。

3.3 参照 AC 代码及关键注释

下面是完整 AC 代码，环境是 C++17，核心逻辑都在 main 函数里：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 100005; int n; ll L, R; ll s[MAXN]; vector<ll> vals; int bit[MAXN * 3]; void add(int idx, int delta) { for (; idx <= (int)vals.size(); idx += idx & -idx) { bit[idx] += delta; } } int sum(int idx) { int res = 0; for (; idx > 0; idx -= idx & -idx) { res += bit[idx]; } return res; } int getRank(ll x) { return lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1; } int main() { scanf("%d%lld%lld", &n, &L, &R); for (int i = 1; i <= n; i++) { ll x; scanf("%lld", &x); s[i] = s[i - 1] + x; } vals.push_back(0); for (int i = 1; i <= n; i++) { vals.push_back(s[i]); vals.push_back(s[i] - R); vals.push_back(s[i] - L); } sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); ll ans = 0; add(getRank(0), 1); for (int j = 1; j <= n; j++) { int leftPos = getRank(s[j] - R); int rightPos = upper_bound(vals.begin(), vals.end(), s[j] - L) - vals.begin(); if (leftPos <= rightPos) { ans += sum(rightPos) - sum(leftPos - 1); } add(getRank(s[j]), 1); } printf("%lld\n", ans); return 0; }

代码整体还是比较短的。要注意ans必须用 long long，因为合法区间数量最大是 n(n+1)/2，n 到 1e5 时这个值接近 5e9，int 必然溢出。我本地测试时一开始开了 int，输出变负数，排查了半天才发现是这里炸了。

4. 第二种写法：用归并排序分治代替树状数组

4.1 为什么想到分治写法

树状数组 + 离散化的方案已经能 AC，但我在翻阅这道题讨论区的时候，看到有人用类似“归并排序求逆序对”的思路做，代码不用离散化，也想得很巧妙。后来我自己推了一遍，确认这确实是对前缀和数组做 CDQ 分治的一个变体。

核心思想是：整个问题的答案可以拆成三部分——左半边内部的合法数对、右半边内部的合法数对、以及跨越中间位置的合法数对。左右半边内部的答案通过递归求解，跨中点的答案则在合并之前用双指针统计。

4.2 双指针统计跨中点的数对

假设当前分治区间是 [l, r]，中点 mid。左右两边在进入当前层之前，已经被各自排序好了（归并排序的特性）。我们要统计所有满足条件的 (i, j)，其中 i 在左半边 [l, mid]，j 在右半边 [mid+1, r]，并且：

L ≤ s[j] - s[i] ≤ R

等价于：

s[i] + L ≤ s[j] ≤ s[i] + R

由于右半边是有序的，对于每一个固定的 i，可以用两个指针在右半边找到满足条件的 j 的连续范围。维护 p1 指向第一个满足 s[j] ≥ s[i] + L 的位置，p2 指向第一个满足 s[j] > s[i] + R 的位置，那么贡献就是 p2 - p1。因为右半边随着 i 的增大也是从左往右移动的，所以可以做到线性统计。

这一步统计完后，再执行正常的归并合并，保证上层看到的左右两半仍然有序。

4.3 归并解法需要注意的细节

这个写法的细节主要在两点：

第一，递归的区间是前缀和数组的下标范围 [0, n]，s[0] = 0 必须参与。因为 s[0] 对应的是“空区间左端点”，漏掉它会导致所有从数组第一个元素开始的合法区间全部丢失。我建议直接用cdq(0, n)作为入口。

第二，统计跨中点贡献时，i 和 j 分别来自两个不同的、已经有序的区间，而这两个区间内部的答案已经在递归中统计过了，所以不会重不漏。边界条件要小心：双指针 p1 和 p2 在 for 循环里不能重置回 mid+1，必须继承上次的位置继续往后扫，否则复杂度会退化成 O(n²)。

归并版本参考代码如下：

void cdq(int l, int r) { if (l == r) return; int mid = (l + r) >> 1; cdq(l, mid); cdq(mid + 1, r); int p1 = mid + 1, p2 = mid + 1; for (int i = l; i <= mid; i++) { while (p1 <= r && s[p1] < s[i] + L) p1++; while (p2 <= r && s[p2] <= s[i] + R) p2++; ans += p2 - p1; } int i = l, j = mid + 1, k = l; while (i <= mid && j <= r) { tmp[k++] = s[i] <= s[j] ? s[i++] : s[j++]; } while (i <= mid) tmp[k++] = s[i++]; while (j <= r) tmp[k++] = s[j++]; for (int t = l; t <= r; t++) { s[t] = tmp[t]; } }

相比树状数组版本，这个写法省去了离散化过程，代码结构也更“整块”。但理解门槛稍微高一点，需要熟悉归并排序自带的分治性质。两种写法的复杂度都是 O(n log n)，实际运行时间也差不太多。

5. 本地过样例、交上去却 WA 的排查过程

5.1 四个高频踩坑点，一次性说清楚

这道题坑点其实很集中，我把自己和身边同学都踩过的几个位置整理成一张表，方便大家对照：

其中第 4 个坑最隐蔽。因为样例往往很小，而且样例的前缀和数字都比较零散，就算漏掉 s[0]，也可能碰巧输出正确的结果。我拿 n = 3, a = [1, 2, 3], L = 3, R = 6 测试时，漏掉 s[0] 的代码输出是 3，正确答案是 4，差的那一个正好是子数组 [1, 2] 的和 3。

5.2 一次典型的错误输出调试过程

还有一个特别容易错的地方是查询边界判断。我刚开始写的是：

int leftPos = getRank(s[j] - R); int rightPos = getRank(s[j] - L); ans += sum(rightPos) - sum(leftPos - 1);

这看起来逻辑很通顺，但 getRank 内部用的是 lower_bound，遇到 s[j] - L 在 vals 中不存在时，lower_bound 返回的是第一个大于它的位置的排名，这会导致统计范围被“向右扩”，把一些不满足条件的较大值也统计进来。

修复方式就是改用 upper_bound 计算右端点。简单记法：左闭右闭区间 [A, B] 在离散化数组里要拆成“先定位 A 的位置”和“统计到 B 为止的个数”。如果为了让sum(rightPos)包含所有等于 B 的值，就要用 upper_bound 找到“第一个大于 B 的位置”。所有下界用 lower_bound，所有上界用 upper_bound，这个二分组合在离散化题目里几乎万能。

我调试的时候还用过一种辅助手段：在小数据上人工模拟，再在代码里加一些输出，打印每次leftPos、rightPos和查出来的数量。发现某一轮结果比手算多次 1，基本就是上界写错；发现少了从 1 开始的所有区间，基本就是 s[0] 漏了；发现到某个大点开始负数，基本就是 long long 的问题。照着这个顺序排查，WA 一般很快就能定位。

6. 从 P5459 延伸开：区间和计数题目的通用套路

6.1 抓住模式：前缀和 + 不等式变形 + 值域统计

P5459 并不是一道孤立的题。包含 CSP-J/S 在内的很多信奥题目，核心套路都是这一套组合拳：

• 先写前缀和，把“子区间和”变成“两个前缀和的差”；
• 固定其中一个前缀和，用不等式把另一个前缀和的范围求出来；
• 用数据结构或分治统计有多少个历史前缀和落在目标值域内。

一旦形成这个模式，很多题看起来都不一样，但解法骨架是雷同的。例如“统计和大于等于 K 的子数组个数”“统计和小于等于 K 的子数组个数”，都能套这同一个框架；如果把题目改成需要在线回答，就把树状数组换成动态开点线段树；如果数据带修改，就考虑树状数组套平衡树或者 CDQ 分治。

这套思维的价值在于：它把枚举区间的 O(n²) 复杂度，稳定地降到了 O(n log n)。在 n = 1e5 的数据范围下，这是能不能 AC 的分水岭。

6.2 回到这题，我学到的最大收获

这道题给我最大的提点其实是：不要看见“连续子区间”就默认用双指针。双指针适用区间和有单调性的场景，比如所有数非负。一旦数组里出现负数，第一反应应该是前缀和和“值域统计”。同理，凡是条件可以写成“s[i] 落在某个区间 [f(j), g(j)] 内”的计数题，都可以先想想树状数组 + 离散化。

对于还在备考的同学，我建议你刷完这题后，再主动试一下那个归并排序分治的版本。同一个模型，两种实现，能加深你对“分治统计跨中点贡献”这个经典套路的感觉。以后遇到“区间和 > K 的对数”“前缀和差满足某条件的对数”这类变体，你会觉得无比亲切。

最后分享一个刷题笔记里的小技巧：遇到区间和问题，永远先把 s[0] = 0 写在草稿纸上。很多代码的 bug，其实都是“0 这个虚拟边界”没有处理好导致的。P5459 是很好的训练题，吃透它，后面再看到类似题就能少掉很多头发。