算法基础 - 差分矩阵差分矩阵

72 阅读 0 评论 48 点赞

我是靠谱客的博主大意汽车，这篇文章主要介绍算法基础 - 差分矩阵差分矩阵，现在分享给大家，希望可以做个参考。

差分矩阵

差分数组可以将二维数组的核心操作由O(n*n)，变为O(1) 。
假设原数组 a[N][N] 是 b[N][N]数组的前缀和，那么b[ ][ ]数组为a[ ][ ]数组的差分数组。
构造差分数组

与一维差分类似，构造差分数组的目的是为了让原数组a中的子矩阵加上一个数c时所需要的时间复杂度从O(n * n) 优化到O(1)。
由于b数组为a数组的差分数组，所以将b[ i ][ j ] 加上一个数c，则原数组a[ i ][ j ]以及之后的数也都会同时加上c。
假定差分数组已被构建成功，为了使被选中的子矩阵都加上一个数c，则可以：

b[x1][y1] + = c;
b[x1,][y2+1] - = c;
b[x2+1][y1] - = c;
b[x2+1][y2+1] + = c;

初始化差分数组也可以通过将(x1, y1) - (x1 - y1) 子矩阵加上a[ i ][ j ]来实现

b[x1][y1] + = a[ i ][ j ];
b[x1,][y2+1] - = a[ i ][ j ];
b[x2+1][y1] - = a[ i ][ j ];
b[x2+1][y2+1] + = a[ i ][ j ];

复制代码

#include<iostream>
using namespace std;

const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
// 核心代码：将区间[x1, y1] - [x2, y2]中的所有值加上c
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    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 ++)
            scanf("%d", &a[i][j]);
    //构造差分数组
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            insert(i,j,i,j,a[i][j]);
    //进行操作
    while(q --)
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }
    //求出差分数组的前缀和
    for(int i = 1; i <=n; i ++)
        for(int j = 1; j <= m; j ++)
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++) printf("%d ",b[i][j]);
        puts("");
    }
            
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
using namespace std;

const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
// 核心代码：将区间[x1, y1] - [x2, y2]中的所有值加上c
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    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 ++)
            scanf("%d", &a[i][j]);
    //构造差分数组
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            insert(i,j,i,j,a[i][j]);
    //进行操作
    while(q --)
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }
    //求出差分数组的前缀和
    for(int i = 1; i <=n; i ++)
        for(int j = 1; j <= m; j ++)
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++) printf("%d ",b[i][j]);
        puts("");
    }
            
    return 0;
}