本文共 1389 字，大约阅读时间需要 4 分钟。
差分其实就是前缀和的逆运算；
假设有一个数组 a [ 5 ] = 1 ， 2 ， 3 ， 4 ， 5 a[5]={1，2，3，4，5} ，它的差分数组 b [ 5 ] = 1 ， 1 ， 1 ， 1 ， 1 b[5]={1，1，1，1，1} 。显然，差分数组的每个元素可以通过原数组的相邻元素之差得到，即 b [ i ] = a [ i ] − a [ i − 1 ] b[i]=a[i]-a[i-1] 。因此，我们可以推出，原数组的前缀和等于差分数组的前缀和，这也是为什么说差分就是前缀和的逆运算。
知道了这个，差分还有一个重要的应用：在二维网格中对某个区间进行加数操作，然后问操作后的某个位置的值是多少。这种方法在计算机科学和数据处理领域广泛应用。
二维差分和一维差分本质上是一样的操作。只不过，我们扩展到了二维网格中。具体来说，对于一个二维网格 x 1 , y 1 , x 2 , y 2 x1,y1,x2,y2 ，我们需要对四个角进行赋值，通常是 1 1 或 − 1 -1 。赋值完成后，我们通过以下代码来计算最终的网格值：
a[x1][y1]++; a[x2+1][y2+1]++; a[x1][y2+1]--; a[x2+1][y1]--;
这样就能完成二维差分操作啦！
#include#include #include #include using namespace std;long long f[3500][3500], a[3500][3500];long long n, m, x, y, x1, y1, x2, y2;int main() { freopen("square.in", "r", stdin); freopen("square.out", "w", stdout); scanf("%lld", &n); for (int i = 1; i <= n; i++) { scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2); a[x1][y1]++; a[x2+1][y2+1]++; a[x1][y2+1]--; a[x2+1][y1]--; } for (int i = 1; i <= 3000; i++) for (int j = 1; j <= 3000; j++) f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + a[i][j]; cin >> m; for (int i = 1; i <= m; i++) { scanf("%lld %lld", &x, &y); printf("%lld\n", f[x][y]); } return 0;}
通过上述代码，我们可以轻松完成二维差分操作，并输出最终的网格值。如果你对具体实现细节感兴趣，可以继续深入研究。
转载地址：http://bjle.baihongyu.com/