前缀和与差分

前缀和

定义

一种预处理方式，计算前n项的和。可以用来快速求出某个区间的总和。

实现

一维前缀和

constexpr int N = 100010;  
const int a[N], S[N];
void prefix_sum()
{
	for(int i = 1;i <= N;i++)
		S[i] = a[i] + S[i - 1];
}
int sum(const int left,const int right)
{
	return S[right] - S[left - 1];
}

二维前缀和

constexpr int N = 100010;  
const int a[N][N], S[N][N];
void prefix_sum()
{
	for(int i = 1;i <= N;i++)
		for(int j = 1;j <= N;j++)
			S[i] = a[i][j] + S[i-1][j] + S[j-1][i] - S[i-1][j-1]
}
int sum(const int left,const int right,const int uppper,const lower)
{
	return S[right][lower] - S[left - 1][lower] - S[right][upper - 1] + S[left - 1][upper - 1];
}

差分

定义

一种用于高效处理区间加减的数组技巧,对区间进行加减只需要对区间的第一个差分进行加减和最后一个的下一个进行减加即可完成,对第一个差分的操作将移植延续到最后一个的下一个差分。

实现

一维差分

constexpr int N = 100010;  
const int a[N], d[N];
void calculate_d()
{
	for(int i = 1;i <= N;i++)
		d[i] = a[i] - a[i - 1];
}
int value(const int i)
{
	return d[i] + a[i - 1];
}
void apply(const int left, const int right, const int x)
{
	d[left] += x;
	d[right + 1] -= x;
}

二维差分

constexpr int N = 100010;  
const int a[N][N], d[N][N];
void calculate_d()
{
	for(int i = 1;i <= N;i++)
		for(int j = 1;j <= N;j++)
			d[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
}
int value(const int x,const int y)
{
	return d[x][y] + a[x - 1][y] + a[x][y - 1] - a[x - 1][y - 1]; 
}
void apply(const int left, const int upper, const int right, const int lower, const int x)
{  
	d[left][upper] += x;
	d[left][lower + 1] -= x;  
	d[right + 1][upper] -= x;
	d[right + 1][lower + 1] += x;
}