二维差分与前缀和

“最难原谅的人往往就是你自己。”

二维前缀和

$$sum[x][y] = \sum_{i = 1}^x \sum_{j = 1}^y a[i][j]$$

几何意义：以 为左上角， 为右下角的矩形里的元素之和。

二维差分

差分的前缀和是原来的单点值，即

$$a[x][y] = \sum_{i = 1}^x \sum_{j = 1}^y d[i][j]$$

现在想推出差分数组等于什么

$$\begin{array} {cll} d[x][y] & = & \sum_{i = 1}^x \sum_{j = 1}^y d[x][y] - \sum_{i = 1}^x \sum_{j = 1}^{y - 1} d[i][j] - \sum_{i = 1}^{x - 1} \sum_{j = 1}^y d[i][j] + \sum_{i = 1}^{x - 1} \sum_{j = 1}^{y - 1} d[i][j] \\ & = & a[x][y] - a[x][y - 1] - a[x - 1][y] + a[x - 1][y - 1] \end{array}$$

要给二维平面上的一个矩形区域 +1 ，转换成单点的加减。即要给左上角为 (xl, yl) ，右下角为 (xr, yr) 的矩形范围里的点 +1 （包括边界），转换成下面的四个单点变化：

d[xl][yl]++; d[xr + 1][yr + 1]++；
d[xl][yr + 1]--; d[xr + 1][yl]--;

例题

https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/5/DSL_5_B

The Maximum Number of Overlaps

Given a set of axis-aligned rectangular seals, find the number of overlapped seals on the region which has the maximum number of overlapped seals.
Input
The input is given in the following format.

$$\begin{aligned} &N \\ &x 1_{1} y 1_{1} x 2_{1} y 2_{1} \\ &x 1_{2} y 1_{2} x 2_{2} y 2_{2} \\ &: \\ &x 1_{N} y 1_{N} x 2_{N} y 2_{N} \end{aligned}$$

and are the coordinates of the top-left and the bottom-right corner of the -th seal respectively.
Constraints

• are given in integers
  Output
  Print the maximum number of overlapped seals in a line.

因为是求面积重合的最大值，就把每个矩形记到右下角上。即左上角要往右下移动一格。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0; bool f = 0; char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 1007
int a[N][N];

int main() {
    int n = rd();
    for (; n; --n) {
        int xl = rd() + 1, yl = rd() + 1;
        int xr = rd(), yr = rd();
        a[xl][yl]++; a[xr + 1][yr + 1]++;
        a[xr + 1][yl]--; a[xl][yr + 1]--;
    }
    int ans = 0;
    for (int i = 1; i <= 1000; ++i) 
        for (int j = 1; j <= 1000; ++j) {
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
            ans = max(ans, a[i][j]);
        }
    printf("%d\n", ans);
    return 0;
}