一维二维三维 差分和前缀和的计算公式_一维、二位、三维模型计算

前缀和
两步：一构造前缀和s数组，二取答案

差分
三步：构造差分数组b,执行更新操作，对b求前缀和得到原数组更新后的值。

一维差分模板https://wenku.baidu.com/view/1ccc1df01a5f312b3169a45177232f60ddcce7a6.html
一维前缀和模板题：
https://www.acwing.com/problem/content/797/

使用前缀和时的下标边界

需要减1的是起点坐标
//s[r]-s[l-1]
//s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]

差分的构造公式以及前缀和的构造公式

---

一维

构造差分数组

偶加奇减 0=
b[i]=s[i];
b[i]-=s[i-1];
1
2
3

差分数组的修改：

偶加奇减
b[x1]+=c;
b[x2+1]-=c;
1
2
3

构造前缀和数组

偶减奇加 0=
s[i]=b[i]
s[i]+=s[i-1]
1
2
3

二维

构造差分数组：

偶加奇减0=
b[i][j]=s[i][j];
b[i][j]-=s[i-1][j];
b[i][j]-=s[i][j-1];
b[i][j]+=s[i-1][j-1];
1
2
3
4
5

差分数组修改:

 //偶+奇-
            b[x1][y1]+=c;
            b[x1][y2+1]-=c;
            b[x2+1][y1]-=c;
            b[x2+1][y2+1]+=c;
1
2
3
4
5

构造前缀和数组：

s[i][j]=b[i][j];
s[i][j]+=s[i][j-1];
s[i][j]+=s[i-1][j];
s[i][j]-=s[i-1][j-1];
1
2
3
4

三维

构造差分数组：

//偶加奇减（0写成=更好和后面构造s转化）
					p=get(i,j,k)
					bp[p]=s[get(i,j,k)];
					bp[p]-=s[get(i,j,k-1)];
					bp[p]-=s[get(i,j-1,k)];
					bp[p]+=s[get(i,j-1,k-1)];
					
					bp[p]-=s[get(i-1,j,k)];					
					bp[p]+=s[get(i-1,j,k-1)];
					bp[p]+=s[get(i-1,j-1,k)];
					bp[p]-=s[get(i-1,j-1,k-1)];
1
2
3
4
5
6
7
8
9
10
11

差分数组的修改：

//偶加奇减
			b[get(x1,y1,z1)]+=c;
			b[get(x1,y1,z2+1)]+=c;
			b[get(x1,y2+1,z1)]+=c;
			b[get(x1,y2+1,z2+1)]+=c;
			
			b[get(x2+1,y1,z1)]+=c;
			b[get(x2+1,y1,z2+1)]+=c;
			b[get(x2+1,y2+1,z1)]+=c;
			b[get(x2+1,y2+1,z2+1)]+=c;
1
2
3
4
5
6
7
8
9
10

构造差分数组的前缀和s还原原数组：

//偶减奇加，0=
					p=get(i,j,k);
					s[p]=b[get(i,j,k)];
					s[p]+=s[get(i,j,k-1)];
					s[p]+=s[get(i,j-1,k)];
					s[p]-=s[get(i,j-1,k-1)];
					
					s[p]+=s[get(i-1,j,k)];					
					s[p]-=s[get(i-1,j,k-1)];
					s[p]-=s[get(i-1,j-1,k)];
					s[p]+=s[get(i-1,j-1,k-1)];
1
2
3
4
5
6
7
8
9
10
11

tips:

如果需要的话，记得数组清零，因为s和b都是从1开始，但是计算时也包括了下标为0的元素，过程中可能不为0，需要重新置零

还有开数组的大小，因为下标从1开始，在二维三维如果存在数组映射，即实际开的是一维数组，需要注意！