《算法竞赛进阶指南》0x03 前缀和与差分

前缀和基础概念

对于一个给定的数列

，它的前缀和数列

是通过递推能求出的基本信息之一：

前缀和的作用

一个部分和，即数列

某个下标区间内的数的和，可表示为前缀和相减的形式

对于多维空间，同样可以定义前缀和，求部分和配合 容斥原理 即可实现

具体“容斥原理”会在数论章节讲解

例如 二维前缀和：

差分基础概念

对于一个给定的数列

，它的差分数列

定义为：

差分的作用

“前缀和” 与 “差分” 互为逆运算：

1. 差分序列

的前缀和序列就是原序列

；

1. 前缀和序列

的差分序列也是原序列

；

把序列

的区间

加

（即把

都加上

），其差分序列

的变化为：

这有助于我们把原序列的 “区间操作” 转化为差分序列上的 “单点操作” 进行计算，从而降低求解难度

差分也可以在树上进行运用，会在图的章节进行讲解

习题

激光炸弹

题目描述

地图上有

个目标，用整数

表示目标在地图上的位置，每个目标都有一个价值

。

注意：不同目标可能在同一位置。

现在有一种新型的激光炸弹，可以摧毁一个包含

个位置的正方形内的所有目标。

激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆炸范围，即那个正方形的边必须和

，

轴平行。

求一颗炸弹最多能炸掉地图上总价值为多少的目标。

输入格式

第一行输入正整数

和

，分别代表地图上的目标数目和正方形的边长，数据用空格隔开。

接下来

行，每行输入一组数据，每组数据包括三个整数

,

,

，分别代表目标的

坐标，

坐标和价值，数据用空格隔开。

输出格式

输出一个正整数，代表一颗炸弹最多能炸掉地图上目标的总价值数目。

数据范围

,

,

,

输入样例：

2 1
0 0 1
1 1 1

输出样例：

1

解析

二维前缀和

值得注意的一点，虽然“目标”位于网格线的交点，而我们的前缀和是以方格为单位累加的

因此我们不妨把“目标”统一偏移到网格的方格中：

且偏移后，新问题与原问题等价，并且新边界变得更好处理

for (int i = 1; i < N; i ++ )
    for (int j = 1; j < N; j ++ )
        s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
for (int i = m; i < N; i ++ )
    for (int j = m; j < N; j ++ )
        res = max(res, s[i][j] - s[i - m][j] - s[i][j - m] + s[i - m][j - m]);

增减序列

题目描述

给定一个长度为

的数列

，每次可以选择一个区间

，使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

输入格式

第一行输入正整数

。

接下来

行，每行输入一个整数，第

行的整数代表

。

输出格式

第一行输出最少操作次数。

第二行输出最终能得到多少种结果。

数据范围

,

输入样例：

4
1
1
2
2

输出样例：

1
2

解析

一维差分

区间修改，联想到用差分数组来维护，最终目标是使差分数组 除首元素外全为 0

每次修改一个区间，对于维护的差分数组变化情况分类：

1. 修改

：b[l] -- , b[r + 1] ++ 或 b[l] ++ , b[r + 1] --

1. 修改

：b[1] -- , b[r + 1] ++ 或 b[1] ++ , b[r + 1] --

1. 修改

：b[l] -- 或 b[l] ++

1. 修改

：b[1] -- 或 b[1] ++ （多余操作）

观察易得:

1. 操作 4 是多余操作（不影响除首元素外元素值，相当于浪费一次操作，必然不是最优解）
2. 操作 2 和操作 3 一次只能改变 1 个元素的值，操作 1 一次可以改变 2 个元素的值
3. 操作 2 会改变首元素的值

为了让操作次数尽可能少，应尽可能使用操作 1

因此不妨设

中正数总和为

，

中负数总和为

然后让正负数配对，尽量执行操作 1，执行次数为

剩余

个要么全是正数，要么全是负数，调用操作 2 或操作 3 都可，执行次数为

次

由于每次调用操作 2 时会改变一次首元素的值，因此首元素的可能值就有

种可能

因此最终答案为：

和

long long p = 0, q = 0;
for (int i = 2; i <= n; i ++ )
{
    if (b[i] > 0) p += b[i];
    else if (b[i] < 0) q -= b[i];
}
cout << max(p, q) << endl << abs(p - q) + 1 << endl;

最高的牛

题目描述

有

头牛站成一行，被编队为

，每头牛的身高都为整数。

当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。

现在，我们只知道其中最高的牛是第

头，它的身高是

，剩余牛的身高未知。

但是，我们还知道这群牛之中存在着

对关系，每对关系都指明了某两头牛

和

可以相互看见。

求每头牛的身高的最大可能值是多少。

输入格式

第一行输入整数

，数据用空格隔开。

接下来

行，每行输出两个整数

和

，代表牛

和牛

可以相互看见，数据用空格隔开。

输出格式

一共输出

行数据，每行输出一个整数。

第

行输出的整数代表第

头牛可能的最大身高。

数据范围

,

,

,

输入样例：

9 3 5 5
1 3
5 3
4 3
3 7
9 8

输出样例：

5
4
5
3
4
4
5
5
5

注意： 此题中给出的关系对可能存在重复

解析

我们希望每对牛之间可以相互看见，并且每头牛的高度最高

一开始不妨假设所有牛的高度都是给出的最高牛的高度

要使第

头牛与第

头牛可以互相看见，那么只需让区间

的牛高度减少 1 即可

可以直接用差分序列来维护原序列，则每次修改操作为：b[x + 1] -- , b[y] ++

int b[N];
set<PII> S;
int main()
{
    cin >> n >> p >> h >> m; b[1] = h;
    while (m -- )
    {
        int x, y;
        cin >> x >> y;
        if (x > y) swap(x, y);
        if (S.count({x, y})) continue;
        S.insert({x, y});
        b[x + 1] -- , b[y] ++ ;
    }
    for (int i = 1; i <= n; i ++ )
    {
        b[i] = b[i - 1] + b[i];
        cout << b[i] << endl;
    }
    return 0;
}