第一个+r
通过对边界即加1 -r
差分改完再改为前缀即可 ,理解差分边界操作
构成都是相对左上角
且二维前缀和矩阵是相对左上角 而二维差分矩阵是相对右下角
一维
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];//a是b前缀和 b是a差分 重要关系是b[i]=a[i]-a[i-1]
//通过堆b[i]区间l,r的边界加c的修改后再求前缀和求回a
void insert(int l,int r,int c)
{
b[l] = b[l] + c;
b[r + 1] = b[r + 1] - c;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
b[i] = a[i] - a[i - 1];
}
int l, r, c;
while (m--)
{
scanf("%d%d%d", &l, &r, &c);
insert(l, r, c);
}
for (int i = 1; i <= n; i++)
{
a[i] = a[i - 1] + b[i];//通过前缀和转换成m个操作区间加c的a
printf("%d ", a[i]);
}
}
二维
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
const int N = 1010;
int n, q, m;
int a[N][N], b[N][N];//a是前缀和,b是差分
void insert(int x1, int y1, int x2, int y2, int c)
{
b[x1][y1] = b[x1][y1] + c;
b[x2 + 1][y1] = b[x2 + 1][y1] - c;
b[x1][y2 + 1] = b[x1][y2 + 1] - c;
b[x2 + 1][y2 + 1] = b[x2 + 1][y2 + 1] + c;
}
int main()
{
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
b[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];//差分矩阵的构成
while (q--)
{
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
insert(x1,y1,x2,y2,c);//对区域进行操作加c
}
//操作后通过前缀和返回a
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i-1][j-1] + b[i][j];
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
printf("%d ", a[i][j]);
}
printf("\n");
}
}