差分与前缀和

First Post:

Last Update:

差分与前缀和

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

知识点

  • 差分算法
  • 前缀和算法

差分法

差分法的应用主要是用于处理区间问题。当某一个数组要在很多不确定的区间，加上相同的一个数。我们如果每个都进行加法操作的话，那么复杂度 $O(nm)$ 是平方阶的，非常消耗时间。

如果我们采用差分法，将数组拆分，构造出一个新的拆分数组，通过对数组区间的端点进行加减操作，最后将数组和并就能完成原来的操作。

这样处理后，时间复杂度降低为 $O(N)$，虽然感觉操作变得更加复杂了，但是只用对边界操作确实比操作一整个区间的方法要优秀的多。

听到这里也是吊足了胃口，那到底怎么对区间操作呢，请大家跟随我的讲解，慢慢理解。

差分法的特点：

  1. 将对于区间的加减操作转化为对于端点的操作；
  2. 时间复杂度为 $O(n)$；
  3. 用于维护区间的增减但不能维护乘除；
  4. 差分后的序列比原来的数组序列多一个数。

差分算法解题的基本思路：

  1. 设定 $b[1]=a[1]$；
  2. 对于第 2 项到第 n 项，利用差分式 $b[i]=a[i]-a[i-1]$；
  3. 对于区间端点进行加减操作；
  4. 进行差分还原（即前缀和）；
  5. 注意，这里从 1 开始。如果从 0 开始，还需讨论 $i=0$ 的情况。使用 1 的话，$b[1]=a[1]-a[0]=a[1]$。

差分法的一般步骤：

假设有一个数组：

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

差分后：

1
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
2
1 1 1 1 1 2 -5
1 4 1 1 1 -1 -5

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

1
1 5 6 7 8 7 2

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

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

确实是都加上了 $3$。

继续操作：

从第二个元素到第四个元素每个减 $2$，可转化为 $[l]$ 减 $2$ 且 $[r+1]$ 加 $2$。

序列变成了：

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

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

1
1 3 4 5 8 7 2

与上次复原后对比：

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

确实是按照操作执行了。

注意，不需要每次都复原，只需在最后一次复原即可。

最后直接做三次，最后还原：

  • 从第二个元素到第五个元素每个加 $3$
  • 从第二个元素到第四个元素每个减 $2$
  • 从第一个元素到第三个元素每个加 $1$

原序列差分后：

1
b = [1 1 1 1 1 2 -5]
  • 第 2 个元素加 3
  • 第 6 个元素减 3
  • 第 2 个元素减 2
  • 第 5 个元素加 2
  • 第 1 个元素加 1
  • 第 4 个元素减 1

差分序列变成：

1
2 2 1 0 3 -1 -5

复原后：

1
2 4 5 5 8 7 5

与原序列对比：

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

所以，差分算法是非常方便快捷的。

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

大学里的树木要打药

题目描述:

教室外有 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$ 的坐标，以及花费。

输入样例:

1
2
3
4
500 3
150 300 4
100 200 20
470 471 19

输出描述:

输出包括一行，这一行只包含一个整数，所有的花费。

输出样例:

1
2662

样例:

输入样例:

1
2
3
4
5
6
7
8
9
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

输出样例:

1
2662

运行限制:

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

题目解析：

  1. 利用$b[i]=a[i]-a[i-1]$ 差分式。

    这里由于开始时都是 $0$，可以用，但是用完都还是 $0$，所以没有意义，所以直接跳过即可。

  2. 依次读入区间的值，然后将对于区间的操作转化为对于区间端点操作加减。 由于我们从 $1$ 开始，所以数目整体区间要右移 $1$ 位。

    对于每个 $[l,r]$ 区间的加减操作都转化为对端点 $l,r+1$ 的操作。

  3. 差分还原(前缀和)。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//读入原始数据 n,m,a

输入n,m

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

    输入a[i]
}

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

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

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

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

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

答案解析

C++ 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
int b[100005];
int main()
{
    int n; //n层
    int m; // m个区间
    cin >> n >> m;

    while (m--)
    {
        int l, r, value;
        cin >> l >> r >> value;
        b[l+1] += value;
        b[r + 1+1] -= value;
    }
    for (int i = 1; i <= n; i++)
        b[i] = b[i] + b[i - 1];
    int 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;
}

Python 解题代码

递推算法代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
b = [0] * 100005

if __name__ == '__main__':

    nm = input().split()
    n = int(nm[0])
    m = int(nm[1])
    while (m > 0):
        m -= 1
        lrv = input().split()
        l = int(lrv[0])
        r = int(lrv[1])
        value = int(lrv[2])
        b[l+1] += value
        b[r + 1+1] -= value

    for i in range(1, n+1):
        b[i] = b[i - 1] + b[i]
    sum = 0
    for i in range(1,n+1):
        sum += b[i]
    print(sum)

    #或者一次性解决
    # sum = a[0]
    #
    # for i in range(1, n+1):
    #
    #     a[i] = a[i - 1] + a[i]
    #
    #     sum += a[0]
    # print(sum)

Java 解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

import java.util.Scanner;
public class Main {
  static int b[]=new int [100005];
  public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      int n; //n层
      int m; // m个区间
      n = in.nextInt();
      m = in.nextInt();
      while(m>0)
      {
          m--;
          int l,r,value ;
          l = in.nextInt();
          r = in.nextInt();
          value = in.nextInt();
          b[l+1]+=value;
          b[r+1+1]-=value;
      }
      for(int i=1; i<=n; i++)
          b[i]=b[i]+b[i-1];

      int sum=0;
      for(int i=1;i<=n;i++)
          sum+=b[i];
  /*

  也可以一次性搞定
  int sum=a[0];
  for(int i=1; i<n; i++){
  a[i]=a[i]+a[i-1];
  sum+=a[i]
  }
  */
      System.out.println(sum);
  }
}

前缀和

前缀和法的应用主要也是用于处理区间问题。

前缀和是指某序列的前 $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$。

前缀和算法解题的基本思路：

  1. 利用 $\text{sum}[i]=a[i]+\text{sum}[i-1]$ 差分式；
  2. 从第 1 项到 $n$ 项，且第 $0$ 项无数据默认为 $0$；
  3. 对于区间求和的操作转化为端点值相减。

前缀和的一般解题过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
首先假设有一个数组：

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$ 棵树，根据不同的位置和树种，学校已经对其进行了多年的维护。因为树的排列成线性，且非常长，我们可以将它们看作一条直线给他们编号。

树的编号从 $1-N$ 且 $N<1e6$。由于已经维护了多年，每一个树都由学校的园艺人员进行了维护费用的统计。

每棵树的前期维护费用各不相同，但是由于未来需要要打药，所以有些树木的维护费用太高的话，就要重新种植。由于维护费用也称区间分布，所以常常需要统一个区间里的树木的维护开销。

现在园艺人员想知道，某个区间内的树木维护开销是多少。共计 $M$ 个区间需要查询。

输入描述:

每组输入的第一行有两个整数 $N（1 <= N<= 1000000）$和 $M（1 <= M <= 100000）$。

$N$ 代表马路的共计多少棵树，$M$ 代表区间的数目，$N$ 和 $M$ 之间用一个空格隔开。接下来的一行，包含 $N$ 个数，每个数之间用空格隔开。

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

输入样例:

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

输出描述:

输出包括 $M$ 行，每一行只包含一个整数，所有的花费。

输出样例:

1
2
3
24
22
17

样例:

输入样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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

输出样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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
2
1. 最大运行时间：1s
2. 最大运行内存：128M

题目解析：

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

前缀和一般解题过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
输 入 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]，并输出

答案解析

C++ 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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;
    }
}

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

终端输出：

1
2
3
4
5
6
7
8
9
10
11
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.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#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;
}

终端输出：

1
2
3
4
5
6
7
8
9
10
11
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.

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

Python 解题代码

普通代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
a = [0] * 100005
sum1 = [0] * 100005
if __name__ == '__main__':

    nm = input().split()
    n = int(nm[0])
    m = int(nm[1])
    a = input().split()
    a = list(map(int, a))
    # split 分割后都是 字符 这里是转化成数字
    #print(a)
    for i in range(1, n + 1):
        # print(i)
        sum1[i] = sum1[i - 1]
        sum1[i] += a[i - 1]  # 分割完后，a[]是从0开始,所以要减1

    while m > 0:

        m -= 1
        lrv = input().split()
        l = int(lrv[0])
        r = int(lrv[1])
        print(sum1[r] - sum1[l - 1])

特殊代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
a = [0] * 100005
sum1 = [0] * 100005
if __name__ == '__main__':

    nm = input().split()
    n = int(nm[0])
    m = int(nm[1])
    a = input().split()

    a = list(map(int, a))
    # split 分割后都是 字符 这里是转化成数字
    # print(a)
    for i in range(1, n + 1):
        # print(i)
        sum1[i] = sum1[i - 1]
        sum1[i] += a[i - 1]  # 分割完后，a[]是从0开始,所以要减1

    ans = []
    while m > 0:

        m -= 1
        lrv = input().split()
        l = int(lrv[0])
        r = int(lrv[1])
        ans.append(sum1[r] - sum1[l - 1])

    for i in ans:
        print(i)

Java 解题代码

普通算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import java.util.Scanner;
public class Main {

    static int a[]=new int [100005];
    static int sum[]=new int [100005];

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n; //n层
        int m; // m个区间
        n = in.nextInt();
        m = in.nextInt();

        for(int i=1;i<=n;i++)
        {
            a[i]= in.nextInt();
            sum[i]=a[i]+sum[i-1];

        }

        while(m>0)
        {
            m--;
            int l,r;
            l = in.nextInt();
            r = in.nextInt();
            System.out.println((sum[r]-sum[l-1]));
        }
    }
}

特殊代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

import java.util.Scanner;
import java.util.Vector;

public class Main {


    static int a[]=new int [100005];
    static int sum[]=new int [100005];
    static Vector ans=new Vector<Integer>();

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int n; //n层
        int m; // m个区间
        n = in.nextInt();
        m = in.nextInt();

        for(int i=1;i<=n;i++)
        {
             a[i]= in.nextInt();
            sum[i]=a[i]+sum[i-1];

        }

        while(m>0)
        {
            m--;
            int l,r;
            l = in.nextInt();
            r = in.nextInt();
            ans.addElement(sum[r]-sum[l-1]);
        }

        for(Object ab:ans){
            System.out.println(ab);
        }
    }
}

总结

我们这节课讲了差分和前缀和的知识点，并且也讲了怎样使用差分，怎样使前缀和，也讲了差分和前缀和最常见的两种情况。

差分和前缀和是很多思维题的解题技巧，必须要掌握熟练才能拿到简单题目的全部分数。

≡