前缀和以及差分看这一篇就够了

2024-03-23 12:53:04

前缀和以及差分问题：

导论：

该博客记录前缀和问题以及差分的解题步骤与相应公式;

理解其中变化，有不完善的地方慢慢补全；

如果有错误欢迎指出！

前缀和：

首先需要知道前缀和的概念：即数组该位置之前的元素之和。

还有一个重要的点，在进行前缀和的运算时，下标从1开始，设数组a[0]=0;

比如a[5] = {0,1,2,3,4};

求a[1]的前缀和：a[1];

求a[2]的前缀和：a[1]+a[2];

......

为什么下标要从1 开始：为了方便后面的计算，避免下标转换，设为零，不影响结果

前缀和的作用： 快速求出元素组中某段区间的和

一维数组的前缀和问题:

求数组a中（l，r）区间的和 --->用到前缀和

需要定义两个数组，第一个为原始数组(a[])，第二个为前缀和数组(s[])

//初始化原数组
int[] arr = new int[x];
for (int i = 1; i <= n; i++) {
	arr[i] = sc.nextInt();
}

公式：s[i] = s[i-1]+a[i] {其中s[i]表示a数组的前i项的和}

//前缀和的计算
int[] s = new int[x];
for (int i = 1; i <=n ; i++) {
	s[i] = s[i-1]+arr[i];
}

输入区间范围(l,r)，s[r]-s[l-1]的结果就是所求区间的和

sum[r] =a[1]+a[2]+a[3]+a[l-1]+a[l]+a[l+1]......a[r];
sum[l-1]=a[1]+a[2]+a[3]+a[l-1];

sum[r]-sum[l-1]=a[l]+a[l+1]+......+a[r];

while (m-- !=0){
    int l = sc.nextInt();
    int r = sc.nextInt();
    System.out.println(s[r]-s[l-1]);
}

二维数组的前缀和问题:

方法与一维数组大体相同：需要中间数组s[i][j]

定义两个二维数组，第一个为原始数组a[][],第二个为临时数组b[][]

// 初始化原始数组
int[][] arr = new int[n+1][m+1];
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <=m ; j++) {
    	arr[i][j] = sc.nextInt();
    }
}

公式：s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + arr[i][j]

前缀和以及差分看这一篇就够了

//定义s二维数组，求解前缀和s数组
int[][] s = new int[n+1][m+1];
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <=m ; j++) {
        s[i][j] = s[i-1][j]+s[i][j-1]-s[i-1][j-1]+arr[i][j];
    }
}

输入区间范围（x1,y1,x2,y2）,s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]的结果就是所求区间的和；前缀和以及差分看这一篇就够了

//求解前缀和
while(q-- !=0){
    int x1 = sc.nextInt();
    int y1 = sc.nextInt();
    int x2 = sc.nextInt();
    int y2 = sc.nextInt();
    int res = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
    System.out.println(res);
}

差分问题：

首先明白差分的概念：差分其实就是前缀和的逆运算

差分的作用：如果对某个区间需要每个元素加上C则需要使用差分来减少时间复杂度

差分的重点是：构造临时数组b[]

b[1] = a[1]
b[2] = a[2] - a[1]
b[3 ]= a[3] - a[2]
...
b[n] = a[n] - a[n-1]

两个数组：S[],b[]，S[]称为b[]的前缀和，b[]称为S[]的差分

差分的下标也是从1开始

前缀和差分是2个互逆的运算，假设最开始的数组是a[i], 则前缀和数组sum[i]表示从a[1]+..+a[i];而差分数组b[1]+…+b[i]则表示a[i],即a[i]是差分数组b[i]的前缀和;

一维数组的差分问题：

首先初始化数组s[]

int[] b = new int[x];
for (int i = 1; i <=n ; i++) {
    s[i] = sc.nextInt();
}

按照上面构造数组方式构造b[]数组，公式：b[i] = s[i]-s[i-1]

//构造差分数组
for (int i = 1; i <=n ; i++) {
    b[i] = s[i]-s[i-1];
}

将所求区间（l,r）在b[]数组划分出来并加上c,公式：b[l] +=c,b[r+1] -=c;
```
int l,r,c;
l = sc.nextInt();
r = sc.nextInt();
c = sc.nextInt();
b[l] +=c;
b[r+1] -=c;
```
因为s[]数组是b[]数组的前缀和，b[]是s[]的差分，所以在b[]的某个区间上+c会影响的a区间上的结果
将差分数组转换成原数组，也就是求差分数组的前缀和,公式：b[i] = b[i-1] +b[i] //类比于s[i]=s[i-1]+a[i]
```
for (int i = 1; i <=n ; i++) {
    b[i] = b[i-1]+b[i];
    System.out.print(b[i]+" ");
}
```

二维数组的差分问题：

记住：a[][]数组是b[][]数组的前缀和数组，那么b[][]是a[][]的差分数组

二维差分的核心也是构造差分数组b[][],使得a数组中a[i][j]是b数组左上角(1,1)到右下角(i,j)所包围矩形元素的和；

怎么让子矩阵中的每个元素加上c;

先定义一个函数：

public static void insert(int x1,int y1,int x2,int y2,int c){
    b[x1][y1] += c;
    b[x2+1][y1] -=c;
    b[x1][y2+1] -=c;
    b[x2+1][y2+1] +=c;
}

初始化原数组a[][]

for (int i = 1; i <=n; i++) {
    for (int j = 1; j <=m ; j++) {
        a[i][j] = sc.nextInt();
    }
}

构造差分数组

初始化B数组从[1][1]到[i][j]添加元素，就是将a[][]中的元素遍历到B数组中

int[][] b = new int[x][x];
for (int i = 1; i <=n; i++) {
    for (int j = 1; j <=m ; j++) {
        insert(i,j,i,j,a[i][j]);
    }
}

输入矩形中需要+c的范围（x1,y1）(x2,y2)，在差分数组b[][]中找到相应的范围+c

while (q-- != 0){
    int x1,y1,x2,y2;
    x1 = sc.nextInt();
    y1 = sc.nextInt();
    x2 = sc.nextInt();
    y2 = sc.nextInt();
    int c = sc.nextInt();
    insert(x1,y1,x2,y2,c);
}

求b[][]数组中的前缀和-->a[][];公式：b[i][j]=a[i][j]−a[i−1][j]−a[i][j−1]+a[i−1][j−1]

for (int i = 1; i <=n ; i++) {
    for (int j = 1; j <=m ; j++) {
        b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + b[i][j];
        System.out.print(b[i][j]+" ");
    }
}

直接输出b[][]中的元素就是a[][]数组中范围所需要+c的结果

结束：

感谢各位能看到最后

码农公寓