前缀和

要想知道差分算法，就要先知道前缀和算法， 应为差分是前缀和的逆运算。

定义

对于一个数组a，某一个数的前缀和表示这个数以及前面所有数的和

例如：

• 对于数组a₁,a₂,……,a_n
• 存在一个数组b₁,b₂,……,b_n
• 使得b₁ = a₁, b_i = a₁+…+a_i = a_i+b_i-1

前缀和公式

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

前缀和的应用

对于前缀和算法，应用的场景是：在区间内进行查询或对子数组进行其他操作

1.利用前缀和计算区间的和

输入一个长度为n的整数序列。

接下来再输入m个询问，每个询问输入一对l, r。

对于每个询问，输出原序列中从第l个数到第r个数的和。
输入格式

第一行包含两个整数n和m。

第二行包含n个整数，表示整数数列。

接下来m行，每行包含两个整数l和r，表示一个询问的区间范围。
输出格式

共m行，每行输出一个询问的结果。

数据范围

1≤l<r ≤n,

1≤n, m ≤100000,

-1000≤数列中元素的值≤1000

#include<iostream>
using namespace std;
const int N = 1e5+10;
int w[N], s[N];   //w存储数组，s存储前缀和
int n, m, l, r; 
int main(){
  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> w[i];
  for(int i = 1; i <= n; i++) s[i] = s[i-1]+w[i]; //更新前缀和
  for(int i = 0; i < m; i++){
    cin >> l >> r;
    cout << s[r]-s[l-1] << endl;    //区间和等于右边界前缀和-左边界前面的和
  } 
  return 0;
}

2.利用前缀和进行优化

【AcWing每日一题】4644. 求和

差分

定义

差分是在前缀和的基础上定义的，是前缀和的逆运算

• 对于一个数组b₁,b₂,……,b_n
• 设其前缀和组成的数组为a₁,a₂,……,a_n
• 即①a₁ = b₁; ②a₂ = b₁+b₂; ③a₃ = b₁+b₂+b₃……
• 则称数组a的差分是数组b

差分的应用

差分的应用场景：对于一个数组在区间[l,r]上对每个数进行操作

1.对区间的每个数进行操作

输入一个长度为n的整数序列。

接下来输入m个操作，每个操作包含三个整数l,r,c，表示将序列中[,r]之间的每个数加上c。

请你输出进行完所有操作后的序列。
输入格式

第一行包含两个整数n和m。

第二行包含n个整数，表示整数序列。

接下来m行，每行包含三个整数l， r, c，表示一个操作。
输出格式

共一行，包含n个整数，表示最终序列。

数据范围

1≤n, m ≤100000, 1<l<r ≤n,

-1000<c≤1000,

-1000≤整数序列中元素的值≤1000
思路：

• 由于a是b的前缀和，所以b在第i个位置的数加（减）c就等价于他的前缀和从i位置的数之后都加（减）一个c
• 当限定在一个[l,r]区间内，需要两次操作：
  首先，在b的第l个位置加c，使得原数组第l个位置后面都加c。但是r后面多加了c！
• 然后，在b的第r+1个位置减c，使得原数组只有[l,r]区间内加了c。
• 由于这个题最终要落实到原数组，所以，利用原数组是差分数组的前缀和，将差分数组的前缀和填入原数组即可。

#include<iostream>
using namespace std;
const int N = 1e5+10;
int w[N], s[N];   //w存储原数组，s存储差分数组
int n, m, l, r, c; 
int main(){
  cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> w[i];
  for(int i = 1; i <= n; i++) s[i] = w[i]-w[i-1]; //更新差分数组
  for(int i = 0; i < m; i++){
    cin >> l >> r >> c;
    s[l] += c;
    s[r+1] -= c;
  }
  for(int i = 1; i <= n; i++) w[i] = s[i]+w[i-1];
  for(int i = 1; i <= n; i++) cout << w[i] << " " ;
  return 0;
} 

2. 前缀和与差分的综合

【AcWing每日一题】4655. 重新排序