前缀和与差分

前缀和与差分

前言

本文只写公式,不证明。

下文中 d \large d d​​​数组均表示差分数组, a \large a a​​​数组均表示原数组, p r e \large pre pre​​​​​数组均表示前缀和数组,下面让我们 l e t ′ s    g o \large let's\ \ go let′s  go​​

一维

d i = a i − a i − 1 a n = ∑ i = 1 n d i p r e n = ∑ i = 1 n a i = ∑ x = 1 n ∑ i = 1 x d i = ∑ i = 1 n d i × ( n − i + 1 ) \large d_i=a_i-a_{i-1} \\ \large a_n=\sum\limits_{i=1}^nd_i \\ \large pre_n=\sum\limits_{i=1}^n a_i=\sum\limits_{x=1}^n\sum\limits_{i=1}^x d_i=\sum\limits_{i=1}^nd_i\times (n-i+1) di​=ai​−ai−1​an​=i=1∑n​di​pren​=i=1∑n​ai​=x=1∑n​i=1∑x​di​=i=1∑n​di​×(n−i+1)

差分维护区间修改 [ l , r ] \large [l,r] [l,r]​
d l + = x , d r + 1 − = x \large d_l+=x,d_{r+1}-=x dl​+=x,dr+1​−=x

二维

d i , j = a i , j − a i − 1 , j − a i , j − 1 + a i − 1 , j − 1 a i , j = d i , j + d i − 1 , j + d i , j − 1 − d i − 1 , j − 1 = ∑ x = 1 i ∑ y = 1 j d x , y p r e i , j = a i , j + p r e i − 1 , j + p r e i , j − 1 − p r e i − 1 , j − 1 = ∑ x = 1 i ∑ y = 1 j a x , y = ∑ x = 1 i ∑ y = 1 j ∑ k = 1 x ∑ l = 1 y a k , l s u m   o f   s u b r e c t a n g l e { x 1 ≤ x ≤ x 2 , y 1 ≤ y ≤ y 2 } = p r e x 2 , y 2 − p r e x 1 − 1 , y 2 − p r e x 2 , y 1 − 1 + p r e x 1 − 1 , y 1 − 1 \large d_{i,j}=a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1} \\ \large a_{i,j}=d_{i,j}+d_{i-1,j}+d_{i,j-1}-d_{i-1,j-1}=\sum\limits_{x=1}^i\sum\limits_{y=1}^j d_{x,y} \\ \large pre_{i,j}=a_{i,j}+pre_{i-1,j}+pre_{i,j-1}-pre_{i-1,j-1} \\ \large =\sum\limits_{x=1}^i\sum\limits_{y=1}^ja_{x,y}=\sum\limits_{x=1}^i\sum\limits_{y=1}^j\sum\limits_{k=1}^x\sum\limits_{l=1}^ya_{k,l} \\ \large sum\ of\ subrectangle\{x_1\le x\le x_2,y_1\le y\le y_2\} \\ \large = pre_{x_2,y_2}-pre_{x_1-1,y_2}-pre_{x_2,y_1-1}+pre_{x_1-1,y_1-1} di,j​=ai,j​−ai−1,j​−ai,j−1​+ai−1,j−1​ai,j​=di,j​+di−1,j​+di,j−1​−di−1,j−1​=x=1∑i​y=1∑j​dx,y​prei,j​=ai,j​+prei−1,j​+prei,j−1​−prei−1,j−1​=x=1∑i​y=1∑j​ax,y​=x=1∑i​y=1∑j​k=1∑x​l=1∑y​ak,l​sum of subrectangle{x1​≤x≤x2​,y1​≤y≤y2​}=prex2​,y2​​−prex1​−1,y2​​−prex2​,y1​−1​+prex1​−1,y1​−1​

差分维护子矩形修改,左上角 ( x 1 , y 1 ) \large (x_1,y_1) (x1​,y1​)​,右下角 ( x 2 , y 2 ) \large (x_2,y_2) (x2​,y2​)​
d x 1 , y 1 + = w d x 2 + 1 , y 1 − = w d x 1 , y 2 + 1 − = w d x 2 + 1 , y 2 + 1 + = w \large d_{x_1,y_1}+=w \\ \large d_{x_2+1,y_1}-=w \\ \large d_{x_1,y_2+1}-=w \\ \large d_{x_2+1,y_2+1}+=w \\ dx1​,y1​​+=wdx2​+1,y1​​−=wdx1​,y2​+1​−=wdx2​+1,y2​+1​+=w

BIT

一维

Q1:区间修改,单点求和

B I T BIT BIT维护差分值即可。

Q2:区间修改,区间求和。

考虑下面的等式

p r e n = ∑ i = 1 n d i × ( n − i + 1 ) − ∑ i = 1 n [ ( n + 1 ) d i − i × d i ] \large pre_n=\sum\limits_{i=1}^nd_i\times (n-i+1)-\sum\limits_{i=1}^n [(n+1)d_i-i\times d_i] pren​=i=1∑n​di​×(n−i+1)−i=1∑n​[(n+1)di​−i×di​]​​

考虑分成两部分: ( n + 1 ) d i , i d i \large (n+1)d_i,\quad id_i (n+1)di​,idi​

两个 B I T BIT BIT​​​分别维护 d i \large d_i di​​​, i d i \large id_i idi​​​ 即可。


二维

Q1:区间修改,单点求和。

一个二维 B I T BIT BIT维护二维差分数组即可。

Q2:区间修改,区间求和。

考虑下面等式

p r e x , y = ∑ i = 1 x ∑ j = 1 y ∑ k = 1 i ∑ l = 1 j d k , l \large pre_{x,y}=\sum\limits_{i=1}^x \sum\limits_{j=1}^y \sum\limits_{k=1}^i \sum\limits_{l=1}^jd_{k,l} prex,y​=i=1∑x​j=1∑y​k=1∑i​l=1∑j​dk,l​​​​​

= ∑ i = 1 x ∑ j = 1 y d i , j × ( x − i + 1 ) × ( y − j + 1 ) \large =\sum\limits_{i=1}^x\sum\limits_{j=1}^y d_{i,j}\times (x-i+1)\times (y-j+1) =i=1∑x​j=1∑y​di,j​×(x−i+1)×(y−j+1)​​​

= ∑ i = 1 x ∑ j = 1 y d i , j ( x + 1 ) ( y + 1 ) − ( y + 1 ) × i d i , j − ( x + 1 ) × j d i , j + i j d i , j \large =\sum\limits_{i=1}^x\sum\limits_{j=1}^y d_{i,j}(x+1)(y+1)-(y+1)\times id_{i,j}-(x+1)\times jd_{i,j}+ijd_{i,j} =i=1∑x​j=1∑y​di,j​(x+1)(y+1)−(y+1)×idi,j​−(x+1)×jdi,j​+ijdi,j​​

因此用 4 4 4​​个二维 B I T BIT BIT​​维护 d i , j , i d i , j , j d i , j , i j d i , j \large d_{i,j},id_{i,j},jd_{i,j},ijd_{i,j} di,j​,idi,j​,jdi,j​,ijdi,j​​​ 即可。

二维区间修改,区间求和习题

P4514 上帝造题的七分钟

// Problem: P4514 上帝造题的七分钟
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4514
// Memory Limit: 128 MB
// Time Limit: 2000 ms
// Date: 2021-07-24 19:37:56
// --------by Herio--------

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull; 
const int N=(1<<11)+1,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb emplace_back
#define SZ(a) (int)a.size()
#define IOS ios::sync_with_stdio(false),cin.tie(0) 
void Print(int *a,int n){
	for(int i=1;i<n;i++)
		printf("%d ",a[i]);
	printf("%d\n",a[n]); 
}
int n,m;
struct bit{
	#define lowbit(x) x&(-x)
	#define il inline 
	int c[N][N];
	il void add(int x,int y,int w){
		for(int i=x;i<=n;i+=lowbit(i))
			for(int j=y;j<=m;j+=lowbit(j))
				c[i][j]+=w;
	}
	il int que(int x,int y){
		int s=0;
		for(int i=x;i;i-=lowbit(i))
			for(int j=y;j;j-=lowbit(j))
				s+=c[i][j];
		return s;
	}
}a,ai,aj,aij;
void add(int x,int y,int w){
	a.add(x,y,w);
	ai.add(x,y,x*w);
	aj.add(x,y,y*w);
	aij.add(x,y,x*y*w);
}
void add(int u,int v,int x,int y,int w){
	add(u,v,w);
	add(u,y+1,-w);
	add(x+1,v,-w);
	add(x+1,y+1,w);
}
int que(int x,int y){
	return a.que(x,y)*(x*y+x+y+1)-ai.que(x,y)*(y+1)-aj.que(x,y)*(x+1)+aij.que(x,y);
}
int que(int u,int v,int x,int y){
	return que(x,y)-que(x,v-1)-que(u-1,y)+que(u-1,v-1);
}
int main(){
	char ch;
	scanf("\n%c%d%d",&ch,&n,&m);
	while(~scanf("\n%c",&ch)){
		if(ch=='\n') break;
		int a,b,x,y,w;
		if(ch=='L'){
			scanf("%d%d%d%d%d",&a,&b,&x,&y,&w);
			add(a,b,x,y,w);
		}
		else if(ch=='k'){
			scanf("%d%d%d%d",&a,&b,&x,&y);
			printf("%d\n",que(a,b,x,y));
		}
	}
	return 0;
}
上一篇:解决 IAR中 Warning[Pa082] 的警告问题


下一篇:Spring框架 - IOC和DI