本文介绍了前缀和、差分与二分查找在标准库中的实现。

所有函数均可在 NOI 系列赛事中使用（C++14 标准）。

文中所给出的定义部分经过简化，具体函数定义参见 cppreference。

预计阅读时长 5 分钟。

前缀和

C++ 在其标准库中实现了求前缀和数组的函数 std::partial_sum，在标头 <numeric> 中被定义。

该函数共有两个定义，我们分开来介绍。

定义 1

template<class InputIt, class OutputIt>
OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first);

该函数共有三个参数，其作用分别为：

• first：待求值的容器头/头指针
• last：待求值的容器尾/尾指针
• d_first：要保存到的容器头/头指针

值得注意的是，first 与 last 需要传入常量指针。

这里给出一个较为直观的例子：

题目：洛谷 B3612 【深进1.例1】求区间和

#include <bits/stdc++.h>
using namespace std;
int n, m, l, r;
int main()
{
    cin >> n;
    vector<int>a(n);
    for(auto &i : a) cin >> i;
    partial_sum(a.cbegin(), a.cend(), a.begin());
    cin >> m;
    while(m --)
    {
        cin >> l >> r;
        cout << a[r - 1] - a[l - 2] << endl;
    }
    return 0;
}

此处另外演示了在静态数组上的使用方法：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, a[N], s[N], l, r;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    partial_sum(a + 1, a + n + 1, s + 1);
    cin >> m;
    while(m --)
    {
        cin >> l >> r;
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

定义 2

template<class InputIt, class OutputIt, class BinaryOp>
OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first, BinaryOp op);

前三个参数与定义 1 无异，但第多出了第四个 op 参数。

该参数定义了前缀和中 + 的行为，此处给出一个简单的示例方便理解。

// 此处实现了前缀积
vector<int>v(10, 2);
partial_sum(v.cbegin(), v.cend(), v.begin(), multiplies<int>());

此时 v 中存储的数据是 2, 4, 8, 16, 32, ... 而不是 2, 4, 6, 8, 10, ...。

差分

C++ 在其标准库中同样实现了求差分数组的函数 std::adjacent_difference，在标头 <numeric> 中被定义。

该函数的两个定义与 partial_sum 完全相同，仅定义 2 中的“对 + 行为的定义”变为了“对 - 行为的定义”。

此处仅以一道例题辅助大家理解。

题目：洛谷 P2367 语文成绩

#include <bits/stdc++.h>
using namespace std;
int n, m, p, x, y, z;
int main()
{
    cin >> n >> p;
    vector<int>v(n);
    for(auto &i : v) cin >> i;
    adjacent_difference(v.cbegin(), v.cend(), v.begin());
    while(p --)
    {
        cin >> x >> y >> z;
        v[x - 1] += z, v[y] -= z;
    }
    partial_sum(v.cbegin(), v.cend(), v.begin());
    cout << *min_element(v.cbegin(), v.cend()) << endl;
    return 0;
}

二分查找