数组差分&&二维矩阵的前缀和与差分，在O(n)时间内完成查询

清疚 2022-08-31 01:54 204阅读 0赞

![在这里插入图片描述][afe30f858ba7031c0d0229a370210a71.png]  
 a \[ i \] = b \[ 1 \] + b \[ 2 \] + . . . b \[ i − 1 \] + b \[ i \] a\[i\] = b\[1\] + b\[2\] + ...b\[i-1\]+b\[i\] a\[i\]=b\[1\]\+b\[2\]\+...b\[i−1\]\+b\[i\]

b \[ l \] = b \[ l \] + c b\[l\] = b\[l\] + c b\[l\]=b\[l\]\+c  
 b \[ r + 1 \] = b \[ r + 1 \] − c b\[r+1\] = b\[r+1\] - c b\[r\+1\]=b\[r\+1\]−c  
使得a数组两头的数不变，中间求前缀和时，就会自动加上c 值。

#include <iostream>
    using namespace std;
    const int maxn = 1e5+10;
    
    int a[maxn],b[maxn],sum[maxn];
    
    void insert(int l, int r, int c)
    { 
    	b[l] += c;
    	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]);
    		insert(i, i, a[i]);
    	}
    
    	while(m--)
    	{ 
    		int l, r, c;
    		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];
    		printf("%d ", a[i]);
    	}
    	return 0;
    }

--------------------

二维矩阵前缀和：  
前缀和公式：  
`s[i][j] = s[i-1] + s[i][j-1] - s[i-1][j-1] + a[i][j];`  
求差公式:  
`s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][x2-1];`

/* 求数组的前缀和*/
    #include <iostream>
    using namespace std;
    const int maxn = 1e4+10;
    
    int a[maxn][maxn],s[maxn][maxn];
    
    int main()
    { 
    	int n, m, q;
    	scanf("%d %d %d", &n, &m, &q);
    	for (int i = 1; i <= n; i++)
    		for(int j = 1; j <= m; i++)
    			scanf("%d", &a[i][j]);
    
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= m; j++)
    			s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
    
    	while(q--)
    	{ 
    		int x1, y1, x2, y2;
    		scanf("%d %d %d %d", &x1, &x2, &x3, &x4);
    		printf("%d\n", s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);
    	}
    
    
    	return 0;
    }

[afe30f858ba7031c0d0229a370210a71.png]: /images/20220829/480097ce36d0484f94f1bbf9d5db2904.png