算法05：前缀和、双指针、滑动窗口与答案二分

一段传感器记录经常带来几类需求：求某个时间区间的总量、给多个区间加偏置、找总量达到阈值的最短连续段，或把任务按原顺序分配给几次执行。这些问题看起来都在操作数组，却依赖不同的性质。前缀和利用可相减的累计量，窗口利用单调性，答案二分利用可行性的分界。

1. 前缀和：把反复累加变成两次读取

定义 p[i] 为前 i 个元素之和，特意让 p[0] = 0。长度为 n 的数组因此需要 n+1 个前缀值：

$$p[i+1]=p[i]+a[i],\qquad \operatorname{sum}(l,r)=p[r]-p[l].$$

这里的查询区间是 [l,r)，包含 l，不包含 r。例如：

std::vector<long long> p(a.size() + 1, 0);
for (std::size_t i = 0; i < a.size(); ++i)
    p[i + 1] = p[i] + a[i];
// 检查 0 <= l <= r <= a.size() 后：
long long result = p[r] - p[l];

一次预处理为 O(n)，每次查询为 O(1)，额外空间 O(n)。如果有 q 次查询，总工作量由直接累加的最坏 O(nq) 变成 O(n+q)。负数不影响这个公式，因为求和仍可以相减。

前缀和适用于静态数据。 修改 a[k] 会影响后面的所有前缀，不能继续把旧 p 当作最新结果。频繁更新且实时查询时，树状数组或线段树才是下一步；它们和一次性预处理解决的需求不同。前缀最小值也不能通过“两项相减”恢复任意区间最小值。

累计值可能远大于单个样本。配套实现限定长度不超过 100000、单值绝对值不超过 1000000，再用 long long 累计；这个约束保证求和不会越过类型范围，并不意味着任意整数输入都安全。

2. 差分：批量区间更新只记录两个边界

要对 [l,r) 的每个元素加上 v，可以先在“附加量的差分”中记录：

diff[l] += v;
diff[r] -= v; // diff 有 n+1 个位置，允许 r == n

最后按从左到右的累计值恢复各位置附加量。左边界让增量生效，右边界让它停止，区间内部不需要逐项写入。

原序列 [2,1,3,4]，先给 [1,3) 加 2，再给 [2,4) 加 −1：

q 次更新和最终恢复共 O(q+n)，额外空间 O(n)。空区间 [l,l) 的两次修改相互抵消。差分适合“先全部更新、最后读取”的离线需求；每次更新后立刻恢复整个数组，仍会付出 O(nq) 的成本。

3. 双指针：为什么可以一次排除一整行候选

在非递减有序数组中找两个不同位置，使两数之和等于目标。左指针指向最小值，右指针指向最大值：

while (left < right) {
    auto sum = a[left] + a[right];
    if (sum == target) return std::pair{left, right};
    if (sum < target) ++left;
    else --right;
}

正确性依据是排序：若当前和太小，固定左端点时，任何更靠左的右端点只会让和更小，因此这个左端点已经没有答案，可以整体排除。和太大时同理排除右端点。

对 [1,2,4,7,11] 找 9：1+11=12，右端点左移；1+7=8，左端点右移；2+7=9，找到下标 (1,3)。每个指针至多移动 n 次，查找 O(n)、额外空间 O(1)。如果输入尚未排序，还需 O(n log n) 排序，并保存原下标才能返回原序列中的位置。

重复值没有问题：[4,4] 找 8 可以使用两个不同下标。单个 [4] 则不能把同一位置用两次。对无序数据直接移动指针没有上述排除依据。

4. 滑动窗口：两个循环为什么仍是线性

目标是：在非负数序列中，找总和至少为正数 target 的最短非空连续段。右端点扩张让和不下降，左端点收缩让和不增加：

std::size_t left = 0, best = a.size() + 1;
long long sum = 0;
for (std::size_t right = 0; right < a.size(); ++right) {
    sum += a[right];
    while (sum >= target) {
        best = std::min(best, right - left + 1);
        sum -= a[left++];
    }
}
// best 仍为 n+1 表示没有可行窗口；示例接口返回 0。

对 [2,3,1,2,4,3]、target=7，窗口第一次达标是 [0,4)，长度 4。右端点到 4 时，收缩得到 [2,5)，长度 3；到 5 时，收缩得到 [4,6)，长度 2，对应 [4,3]。

不变量是：sum 始终等于当前窗口元素之和。每次达标都先记录答案，再移除左边元素；不达标时再向右扩张。已经丢弃的左端点，以后即使又能达标，窗口也只会更长，不可能改善刚记录的长度。

虽然有嵌套 while，left 与 right 都只向右走，每个元素最多进入一次、移出一次，总时间 O(n)，额外空间 O(1)。复杂度不能只按代码缩进层数判断。

负数会破坏这个窗口

[1,-1,5]、target=5：右端点到末尾时总和为 5，代码记录长度 3，再移除 1 后总和变为 4，于是停止收缩，漏掉长度为 1 的 [5]。因为继续移除 −1 会让和重新增加，原来的单调性已经失效。

所以“数组上的连续段”不自动等于“滑动窗口”。含负数的最短达标子数组通常需要前缀和加单调队列；那是另一种不变量。下面的前缀和计数则解决“和恰好为 target 的段数”，不是最短长度。

5. 前缀和加哈希：允许负数的精确和计数

若一段 [l,r) 和为 k，则 p[r]-p[l]=k，等价于寻找此前出现了多少个 p[l]=p[r]-k。

std::unordered_map<long long, long long> count{{0, 1}};
long long prefix = 0, answer = 0;
for (auto x : a) {
    prefix += x;
    auto it = count.find(prefix - k);
    if (it != count.end()) answer += it->second;
    ++count[prefix];
}

count[0]=1 代表序列开始前的空前缀，使从下标 0 开始的段也被计入。先查询、再登记当前前缀，保证左端点严格早于右端点；反过来会在 k=0 时误计空段。

[1,-1,1] 求和为 1 的段：第一次前缀 1 匹配一个 0；第二次前缀 0 不增加答案；第三次前缀 1 匹配两个 0。总数 3，分别是首个 [1]、整个数组和末个 [1]。

这里保存频次而不是一个下标，因为多个相同前缀对应不同连续段。平均时间 O(n)、额外空间 O(n)，但依赖哈希的平均复杂度假设；需要确定的 O(n log n) 上界可以使用 std::map。全零序列、k=0 的答案为 n(n+1)/2，计数类型也要足够大。

6. 答案二分：在可行阈值中找第一项

任务工作量 [7,2,5,10,8] 必须保持原顺序，每个任务不可拆分，最多使用 2 个连续分组。求单组所需容量的最小值。这里的约束是“最多 2 组”，不是允许任意重排，也不是平均分配。

给定容量 C，从左向右尽量填满一组，放不下再开启下一组。工作量非负时，这种扫描使用的组数最少：第一组已经尽可能延伸，任何合法分组都不能在第一组中覆盖更长前缀；剩余部分重复同样的论证。

当 C 可行，任何更大的容量也可行，所以判断结果只有“不可行 → 可行”的一次分界。搜索下界是最大单项 10，上界是总量 32：

while (lo < hi) {
    auto mid = lo + (hi - lo) / 2;
    if (feasible(a, groups, mid)) hi = mid;
    else lo = mid + 1;
}
return lo;

一次判断 O(n)，搜索 O(log(S−M+1)) 次，其中 S 为总和、M 为最大单项；总时间 O(n log(S−M+1))，除输入外 O(1) 空间。判定函数比二分模板更重要：如果允许负工作量、拆分任务或改变顺序，上述证明和扫描方式就需要重新建立。

7. 完整源码与主题衔接

sequence_algorithms.cpp 包含以上六类实现和完整输入约束。它用直接累加、连续段枚举、所有切分位置枚举作为参考结果，核对 2500 组固定随机种子的短序列，并覆盖空输入、重复值、零值、负数拒绝及大累计量。

这些例子展示了减少工作的三种来源：重复求和可以缓存；不可能成为答案的端点可以丢弃；候选阈值可以利用单调性折半。继续看分治、回溯与贪心，或返回专题路线。