前缀和

---

前缀和定义

对于数列A，它的前缀和数列S[i]就表示数列A从第一个元素到第i个元素的总和。

计算公式

// 前缀和数列S   原数列A
S[i] = S[i - 1] + A[i];
//S[i - 1] 表示i-1个元素的和加上A[i],就构成了前i个元素的和S[i]

具体应用

前缀和的主要用处：求任意区间的区间和

一般通过遍历求和的时间复杂度是O(n),通过前缀和可以减少为O(1)

具体解法如下:

​ 前缀和计算区间[l,r]的区间和：S[r] – S[l – 1]

模板

ACWing 795前缀和

#include 
const int N = 100010;
int a[N],b[N];
int main(void){
    int n,m;
    scanf("%d %d",&n,&m);
    for (int i = 1;i 

Tips:

​ 让元素下标从1开始。也就是下标为0的元素赋值为0

​ 这样的好处是可以计算前i个元素的和，减少特判的情况。

二维前缀和计算公式

//二维前缀和
S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] +A[i][j];
//二维前缀和的作用也是为了快速计算区块和
res = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1];

二维前缀和模板

ACWing 796 子矩阵的和

#include 
const int N = 1010;
int a[N][N],b[N][N];
int main(){
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for (int i = 1;i 

差分（前缀和的逆运算)

定义

给定一个数列 A 那么它的差分数列 B中的B[i] 表示为 A 中第i个元素与第i – 1个元素的差。

B[i] = A[i] - A[i - 1] (1 

具体应用

// 差分的主要应用 就是快速的给 A 的区间[l,r] 加上d
// 将A[l,r]加d ==> 将差分数列 B[l] 加 d 再将B[r + 1]减d

模板

ACWing 797.差分

#include 
const int N = 100010;
int a[N],b[N];
int main(void){
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i = 1;i 

二维差分公式

// 对A矩阵中该区块的每个元素加上d的操作 相当于对B进行四个操作
B[x1][y1] += d;
B[x2 + 1][y1] -= d;
B[x1][y2 + 1] -= d;
B[x2 + 1][y2 + 1] += d;

二维差分模板

ACWing 789.差分矩阵

#include 
const int N = 1010;
int a[N][N],b[N][N];
void insert (int x1,int y1,int x2,int y2,int d) {
    b[x1][y1] += d;
    b[x2 + 1][y1] -= d;
    b[x1][y2 + 1] -= d;
    b[x2 + 1][y2 + 1] += d;
}
int main(void){
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for (int i = 1;i 

机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net