二维前缀和 & 二维差分

二维前缀和

求二维前缀和后，能够实现 \(O(1)\) 求原数组二维区间和，但是不支持修改。

ll n, m, sum2[N][N], c[N][N];

void Sum2_pre()
{
    fr(i, 1, n)
        fr(j, 1, m)
            sum2[i][j] = sum2[i-1][j] + sum2[i][j-1] - sum2[i-1][j-1] + c[i][j];
}

ll Sum2(ll x1, ll y1, ll x2, ll y2)
{
    return sum2[x2][y2] + sum2[x1-1][y1-1] - sum2[x1-1][y2] - sum2[x2][y1-1];
}

二维差分

先预处理出差分数组，之后可以实现 \(O(1)\) 原数组二维区间修改。

将差分数组还原为原数组的复杂度是 \(O(n^2)\) 的。

ll n, m, cha2[N][N], c[N][N];

void Cha2_pre() // 预处理差分数组
{
    fr(i, 1, n)
        fr(j, 1, m)
            cha2[i][j] = c[i][j] - c[i][j-1] - c[i-1][j] + c[i-1][j-1];
}

void Cha2(ll x1, ll y1, ll x2, ll y2, ll K) // 原数组二维区间修改
{
    cha2[x1][y1] += K;
    cha2[x2 + 1][y1] -= K;
    cha2[x1][y2 + 1] -= K;
    cha2[x2 + 1][y2 + 1] += K;
}

void Cha2_nxt() // 还原差分数组
{
    fr(i, 1, n)
        fr(j, 1, m)
        {
            cha2[i][j] = cha2[i-1][j] + cha2[i][j-1] - cha2[i-1][j-1] + cha2[i][j];
            c[i][j] = cha2[i][j];
        }
}


int main()
{
    n = re; m = re;
    Cha2_pre();
    fr(i, 1, 5)
    {
        ll a = re, b = re, c = re, d = re, e = re;
        Cha2(a, b, c, d, e);
    }
    Cha2_nxt();

    fr(i, 1, n)
    {
        fr(j, 1, m) W(c[i][j], ' ');
        puts("");
    }
    return 0;
}

输入

10 10
1 1 10 10 1
2 2 9 9 1
3 3 8 8 -1
4 4 7 7 2
5 5 6 6 1

输出

1 1 1 1 1 1 1 1 1 1 
1 2 2 2 2 2 2 2 2 1
1 2 1 1 1 1 1 1 2 1
1 2 1 3 3 3 3 1 2 1
1 2 1 3 4 4 3 1 2 1
1 2 1 3 4 4 3 1 2 1
1 2 1 3 3 3 3 1 2 1
1 2 1 1 1 1 1 1 2 1
1 2 2 2 2 2 2 2 2 1
1 1 1 1 1 1 1 1 1 1