蓝桥杯差分与前缀和|树木打药问题|树木维护问题(C++)

差分与前缀和是一对互逆的操作，常常用于处理区间问题，差分法是解决区间加减问题，前缀和是解决区间求和问题的常用办法。

差分法

差分法的应用主要是用于处理区间问题。当某一个数组要在很多不确定的区间，加上相同的一个数。我们如果每个都进行加法操作的话，那么复杂度 O(nm) 是平方阶的，非常消耗时间。
如果我们采用差分法，将数组拆分，构造出一个新的拆分数组，通过对数组区间的端点进行加减操作，最后将数组和并就能完成原来的操作。
这样处理后，时间复杂度降低为 O(N)，虽然感觉操作变得更加复杂了，但是只用对边界操作确实比操作一整个区间的方法要优秀的多。
差分法的特点：

1. 将对于区间的加减操作转化为对于端点的操作；
2. 时间复杂度为 O(n)；
3. 用于维护区间的增减但不能维护乘除；
4. 差分后的序列比原来的数组序列多一个数。
   差分算法解题的基本思路：
5. 设定 b[1]=a[1]；
6. 对于第 2 项到第 n 项，利用差分式 b[i]=a[i]−a[i−1]；
7. 对于区间端点进行加减操作；
8. 进行差分还原（即前缀和）；
9. 注意，这里从 1 开始。如果从 0 开始，还需讨论 i=0 的情况。使用 1 的话，b[1]=a[1]−a[0]=a[1]。

如果对差分后的b数字其中一个数字+1会怎么样?

恢复后从这一项开始的每一项都上了1。

同样的-1，等于+(-1)，如果对差分后的某一项-1，那么恢复后等于对从此项开始的每一项都-1.
形式化的写为:
如果b[l]=b[]+x(任意值) -> a[l,n]+=x
如果b[r]=b[r]-x -> a[r,n]-=x
若 r>l,则有 a[],a[l+1],a[l+2],..a[r-1],a[r],a[r+1]...a[n]
等效于:a[l,r-1]+=x

即对差分后的数组 b[l]+=x b[r]-=x就能转化为 区间a[l,r-1]+=x

差分法的一般步骤：
假设有一个数组：

a = [1, 2, 3, 4, 5, 7, 2]

差分后：

b = [1, 1, 1, 1, 1, 2, -5]

一般应用场景是对区间 [l,r] 进行 N 次加减操作。例如：

• 从第二个元素到第五个元素每个加 3
• 从第二个元素到第四个元素每个减 2
• 从第一个元素到第三个元素每个加 1
  对于每个 [l,r] 区间的加减操作都可转化为对端点 l 和 r+1 的操作。例如，从第二个元素到第五个元素每个加 3，可转化为 [l] 加 3 且 [r+1] 减 3。
  原序列变成了：

1 1 1 1 1 2 -5
1 4 1 1 1 -1 -5

然后按照 b[i]=b[i]+b[i−1] 复原：

1 5 6 7 8 7 2

去掉最后一项，跟原序列对比：

1 2 3 4 5 7 2
1 5 6 7 8 7 2

确实是都加上了 3。
继续操作：
从第二个元素到第四个元素每个减 2，可转化为 [l] 减 2 且 [r+1] 加 2。
序列变成了：

1 4 1 1 1 -1 -5
1 2 1 1 3 -1 -5

然后按照 b[i]=b[i]+b[i−1] 复原：

1 3 4 5 8 7 2

与上次复原后对比：

1 5 6 7 8 7 2
1 3 4 5 8 7 2

确实是按照操作执行了。
注意，不需要每次都复原，只需在最后一次复原即可。
最后直接做三次，最后还原：

• 从第二个元素到第五个元素每个加 3
• 从第二个元素到第四个元素每个减 2
• 从第一个元素到第三个元素每个加 1
  原序列差分后：

b = [1 1 1 1 1 2 -5]

• 第 2 个元素加 3
• 第 6 个元素减 3
• 第 2 个元素减 2
• 第 5 个元素加 2
• 第 1 个元素加 1
• 第 4 个元素减 1
  差分序列变成：

2 2 1 0 3 -1 -5

复原后：

2 4 5 5 8 7 5

与原序列对比：

1 2 3 4 5 7 2
2 4 5 5 8 7 5

所以，差分算法是非常方便快捷的。
差分与前缀和是逆操作，常在一起出现，但是先做差分还是先做前缀和就是两种不同的算法，做不做另一种操作也决定了算法不同，所以大家要根据题目分析，具体学会使用。

差分算法解决区间加减问题通用框架如下：

//读入原始数据 n,m,a

输入n,m
原始数组 a[]
差分数组 b[]

for(int i=1;i<=n;i++){

    输入a[i]
}

//差分
for(int i=1;i<=n;i++)

    b[i]=a[i]-a[i-1]

//m次区间操作
while(m--)
{
    输入l,r,value
    b[l]+=value
    b[r+1]-=value
}

//前缀和还原
for(int i=1;i<n;i++)

    a[i]=b[i]+a[i-1]

//读入原始数据 n,m,a

输入n,m
原始数组 a[]
差分数组 b[]

for i (1-n){
    输入a[i]
}

//差分
for i (1-n)
    b[i]=a[i]-a[i-1]
    
//m次区间操作
while(m--)
{
    输入l,r,value
    b[l]+=value
    b[r+1]-=value
}

//前缀和还原
for i (1-n)
    a[i]=b[i]+a[i-1]

//读入原始数据 n,m,a

输入n,m
原始数组 a[]
差分数组 b[]

for i (1-n){
    输入a[i]
}

//差分
for i (n-2)
    a[i]=a[i]-a[i-1]
    
//m次区间操作
while(m--)
{
    输入l,r,value
    a[l]+=value
    a[r+1]-=value
}

//前缀和还原
for i (1-n)
    a[i]=a[i]+a[i-1]

大学里的树木要打药

题目描述:
教室外有 N 棵树，根据不同的位置和树种，学校要对其上不同的药。
因为树的排列成线性，且非常长，我们可以将它们看作一条直线给他们编号。
树的编号从 0~N-1 且 N<1e6。
对于树的药是成区间分布，比如 3−5 号的树靠近下水道，所以他们要用驱蚊虫的药，20−26 号的树，他们排水不好，容易涝所以要给他们用点促进根系的药。
诸如此类，每种不同的药要花不同的钱。
现在已知共有 M 个这样的区间，并且给你每个区间花的钱，请问最后，这些树木花了多少药费。
输入:
输入描述:
每组输入的第一行有两个整数 N（1<=N<=1000000）和M（1<=M<=100000）。
N 代表马路的共计多少棵树
M代表区间的数目，N 和 M 之间用一个空格隔开。

接下来的 M 行每行包含三个不同的整数，用一个空格隔开，表示一个区域的起始点L 和终止点R 的坐标，以及花费。

输入样例:

500 3
150 300 4
100 200 20
470 471 19

输出描述:
输出包括一行，这一行只包含一个整数，所有的花费。
输出样例:

2662

样例:
输入样例:

3000 8
150 1130 2
1020 1200 3
470 2071 1
1123  211 6
12 222 2
13 23 2
1  213 4
1232  2523 6

输出样例:

2662

运行限制:

1. 最大运行时间：1s
2. 最大运行内存：128M

题目解析：

1. 利用b[i]=a[i]−a[i−1] 差分式。
   这里由于开始时都是 0，可以用，但是用完都还是 0，所以没有意义，所以直接跳过即可。
2. 依次读入区间的值，然后将对于区间的操作转化为对于区间端点操作加减。 由于我们从 1 开始，所以数目整体区间要右移 1 位。
   对于每个 [l,r] 区间的加减操作都转化为对端点 l,r+1 的操作。
3. 差分还原(前缀和)。

for (int i = 1; i < n; i++)
     b[i] = a[i] - a[i - 1]

答案解析

#include <iostream>
using namespace std;
int b[100005];
int main()
{
    int n; //n层
    int m; // m个区间
    cin >> n >> m;

    while (m--)
    {
	    //因为l，r是从0开始的，差分要求从1开始，整体右移
        int l, r, value;
        cin >> l >> r >> value;
        l = l + 1;
        r = r + 1;
        b[l] += value;
        b[r+1] -= value;
    }
    
    for (int i = 1; i <= n; i++)
        b[i] = b[i] + b[i - 1];
    //统计结果
    long long sum = 0;
    for (int i = 1; i <= n; i++)
        sum += b[i];
    /*
    也可以一次性搞定
    int sum=b[1];
    for(int i=1; i<=n; i++){
    b[i]=b[i]+b[i-1];
    sum+=b[i]
    }
    */
    cout << sum << endl;
}

前缀和

前缀和法的应用主要也是用于处理区间问题。
前缀和是指某序列的前 n 项和，可以把它理解为数学上的数列的前 n 项和。当对于某一数组区间进行多次询问，[L,r] 的和时，如果正常处理，那么我们每次都要 [l,r]。查询 N 次，那么时间复杂度也是 O(nm) 也是平方阶的。
如果我们采用前缀和，构造出一个前缀和数组，通过对于端点的值的减法操作就能 O(1) 的求出 [l,r] 的和。然后 N 次查询的，就将复杂度降低为 O(n)。
同差分一样，感觉操作变得更加复杂了，但是只用对端点值的操作确实比一整个区间相加的方法要优秀的多。听到这里大家很期待了，我们接着进行讲解。
前缀和的特点：

1. 将对于区间的求和操作转化为对于端点值的减法的操作；
2. 区间求和操作的时间复杂度为 O(1)；
3. 数组存放时要从 1 开始；
4. 前缀和数组比原来的数组序列多一个数，第 0个元素为 0。
   前缀和算法解题的基本思路：
5. 利用 sum[i]=a[i]+sum[i−1] 差分式；
6. 从第 1 项到 n 项，且第 0 项无数据默认为 0；
7. 对于区间求和的操作转化为端点值相减。

设l<r:
Sum[l]=a[1]+a[2]..+a[l]
Sum[r]=a[1]+a[2]..+a[l]+a[l+1]+..a[r]

Sum[r]-Sum[l]=a[l+1]+..a[r]
所以前缀和sum[r]-sum[l] 可以转换为 l+1,r区间内a[i]的和

前缀和：

首先假设有一个数组：

1 2 3 4 5 7 2

前缀和后：

0 1 3 6 10 15 22 24

一般应用场景：

让你对区间 [l,r] 求和操作N次

如：

从第二个元素到第五个元素的和
从第二个元素到第四个元素的和
从第一个元素到第三个元素的和
....

这里我们先演示前三个：

对于每个 [l,r] 区间的求和操作转化为区间端点的加减操作

sum[l,r] =[r]-[l-1]

从第二个元素到第五个元素的和：

转化为：[5]-[1]

那么Sum[2,5]=[5]-[1]=14

且 2+3+4+5=14

确实是相等的，就是这么神奇。

我们继续操作：

从第二个元素到第四个元素的和

转化为：[4]-[1]

那么Sum[2,4]=[4]-[1]=9

且 2+3+4=9

我们继续操作：

从第一个元素到第三个元素的和

转化为：[3]-[0]

那么Sum[1,3]=[3]-[0]=6

且 1+2+3=6

符合题意，验证结束，咱么做个题目看一看

前缀和一般解题过程：

输 入 N 和 M

输入 N 个值 并计算前缀和
for( int i=1;i<=N;i++)
    输入a[i]
    并计算sum[i]=sum[i-1]+a[i]

输入 M 个区间，计算结果

while(M)
    M-=1
    输入 L , R
    计算 [r]-[l-1]，并输出

大学里的树木要维护

题目描述:
教室外有 N 棵树，根据不同的位置和树种，学校已经对其进行了多年的维护。因为树的排列成线性，且非常长，我们可以将它们看作一条直线给他们编号。
树的编号从 1−N 且 N<1e6。由于已经维护了多年，每一个树都由学校的园艺人员进行了维护费用的统计。
每棵树的前期维护费用各不相同，但是由于未来需要要打药，所以有些树木的维护费用太高的话，就要重新种植。由于维护费用也称区间分布，所以常常需要统一个区间里的树木的维护开销。
现在园艺人员想知道，某个区间内的树木维护开销是多少。共计 M 个区间需要查询。
输入描述:
每组输入的第一行有两个整数 N（1<=N<=1000000）和 M（1<=M<=100000）。
N 代表马路的共计多少棵树，M 代表区间的数目，N 和 M 之间用一个空格隔开。接下来的一行，包含 N 个数，每个数之间用空格隔开。
接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点L和终止点R的坐标。
输入样例:

10 3
7 5 6 4 2 5 0 8 5 3
1 5
2 6
3 7

输出描述:
输出包括 M 行，每一行只包含一个整数，所有的花费。
输出样例:

24
22
17

样例:
输入样例

30 28 
172 723 580 822 718 798 941 625 450 716 540 252 16 666 115 679 274 323 875 233 99 538 881 486 610 462 319 878 930 735 
6 22 
7 21 
3 16 
7 20 
9 17 
0 21 
13 27 
7 19 
10 23 
2 14 
21 22 
15 17 
6 13 
16 23 
21 21 
11 15 
5 12 
9 11 
8 22 
10 16 
3 8 
15 27 
5 16
4 8 
0 27 
4 8 
7 21 
20 21

输出样例

8140 
6804 
7918 
6705 
3708 
10617 
6576 
6472 
6207 
7847 
637 
1068 
4338 
3902 
99 
1589 
5040 
1706 
6401 
2984 
4484 
5894 
6516 
3904 
13913 
3904 
6804 
332

运行限制:

1. 最大运行时间：1s
2. 最大运行内存：128M

题目解析：

1. 利用sum[i]=a[i]+sum[i−1] 前缀和式在输入时求出前缀和；
2. 依次读入区间的值，然后将对于区间的求和操作转化为对于区间端点操作加减，对于每个 [l,r] 区间的求和操作都转化为对端点[r]-[l-1]的操作。
3. 输出答案。

答案解析

#include <iostream>
using namespace std;
int a[100005];
int sum[100005];

int main()
{
    int n;
    int m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = a[i] + sum[i - 1];
    }

    while (m > 0)
    {
        m -= 1;
        int l, r;
        cin >> l >> r;
        cout << sum[r] - sum[l - 1] << endl;
    }
}

这个代码有个问题，虽然是能通过的，但是他是一个输入对应一个输出的，我们之前讲过，这对大部分的测评机是没问题。
终端输出：

10 3
7 5 6 4 2 5 0 8 5 3
1 5
24
2 6
22
3 7
17

Process returned 0 (0x0)   execution time : 1.741 s
Press any key to continue.

但是如果有想要规规矩矩的处理，或者说题目要求必须全部读入后输出。我们可这样操作。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int sum[100005];
vector<int>ss;
int main()
{

    int n ;
    int m;
    cin>>n>>m;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=a[i]+sum[i-1];

    }

    while(m>0)
    {
        m-=1;
        int l,r;
        cin>>l>>r;
        ss.push_back(sum[r]-sum[l-1]);
    }

    for(auto sss:ss) cout<<sss<<endl;
}

终端输出：

10 3
7 5 6 4 2 5 0 8 5 3
1 5
2 6
3 7
24
22
17

Process returned 0 (0x0)   execution time : 6.235 s
Press any key to continue.

都可以，大家看自己需求和心情选择即可。