-
一维差分算法概述：
- 差分算法是一种用于计算序列中相邻元素之间差值的技术。
- 在C++中，STL（标准模板库）提供了
std::adjacent_difference函数来实现差分算法。
-
std::adjacent_difference函数：std::adjacent_difference函数位于头文件<numeric>中。- 语法：
std::adjacent_difference(first, last, result)。first和last是定义了输入序列范围的迭代器。result是存储结果的目标序列的起始位置
一维差分数组在处理连续序列中的区间更新和查询操作时非常有用。它可以帮助在常数时间复杂度内完成区间元素的增减操作，并支持常数时间复杂度的区间查询操作。以下是一维差分数组的一些主要用途和优点：
-
区间更新：对于原始数组中
[l, r]区间内的元素增加val，只需更新差分数组diff中diff[l] += val和diff[r+1] -= val，然后再根据差分数组计算更新后的原始数组。 -
查询：原始数组中位置为L的元素等于差分数组中
[L]前所有元素的和。 -
应用领域：差分数组在处理数组序列的区间操作中广泛应用，比如处理频繁的区间修改、查询问题。
代码示例（构建）：
std::vector<int> differences(nums.size());std::adjacent_difference(nums.begin(), nums.end(), differences.begin());-
二维差分算法概述：
- 二维差分算法是一种用于计算二维数组中差分的技术。
- 通过预处理数组，可以在常数时间内计算子矩阵的增减值，而不必每次都一一计算。
-
实现方式：
- 我们可以使用差分数组
diff表示相邻元素之间的差值关系。二维差分数组diff的构建规则如下：
- 我们可以使用差分数组
diff[i][j] = matrix[i][j] - matrix[i-1][j] - matrix[i][j-1] + matrix[i-1][j-1]
代码示例(构建)：
int **computeDifferenceArray(int **matrix, int rows, int cols) {int **diff = new int*[rows];for (int i = 0; i < rows; i++) {diff[i] = new int[cols]();}for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {diff[i][j] = matrix[i][j]; // 复制原始数组的值// 处理边界情况if (i > 0) diff[i][j] -= matrix[i - 1][j]; // 上方元素if (j > 0) diff[i][j] -= matrix[i][j - 1]; // 左方元素if (i > 0 && j > 0) diff[i][j] += matrix[i - 1][j - 1]; // 左上方元素}}return diff;
}代码示例（计算）：//如果对原数组(x1,y1)到(x2,y2)的矩形区域整体加上a.
void updateDiffArray(int** &diff, int x1, int y1, int x2, int y2, int a, int rows, int cols) {// Check if the indices are within boundsif (x1 >= 0 && x1 < rows && y1 >= 0 && y1 < cols &&x2 >= 0 && x2 < rows && y2 >= 0 && y2 < cols) {diff[x1][y1] += a;if (x2 + 1 < rows && y1 < cols) diff[x2 + 1][y1] -= a;if (x1 < rows && y2 + 1 < cols) diff[x1][y2 + 1] -= a;if (x2 + 1 < rows && y2 + 1 < cols) diff[x2 + 1][y2 + 1] += a;}
}最后通过二维前缀和还原到原数组即可。
P1. 洛谷p2367语文成绩
#include<iostream>
#include<numeric>
#include<vector>
#include<cmath>
using namespace std;
long long ans=0;
long long result=10000;int main()
{int n,q;cin>>n>>q;vector<int> nums,differs;for(int i=1;i<=n;i++){int a;cin>>a;nums.push_back(a);}differs.resize(n);//很重要，不然调用函数会访问到未分配的内存，发生越界错误adjacent_difference(nums.begin(),nums.end(),differs.begin());//for(int i=0;i<n;i++) cout<<differs[i]<<" ";for(int i=1;i<=q;i++){int left,right,value;cin>>left>>right>>value;differs[left-1]+=value;differs[right]-=value;}for(int i=0;i<n;i++){ans+=differs[i];result=fmin(ans,result);}cout<<result;return 0;
}P2. 洛谷p3397地毯
#include<iostream>
using namespace std;int **computeDifferenceArray(int **matrix, int rows, int cols) {int **diff = new int*[rows];for (int i = 0; i < rows; i++) {diff[i] = new int[cols]();}for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {diff[i][j] = matrix[i][j]; // 复制原始数组的值// 处理边界情况if (i > 0) diff[i][j] -= matrix[i - 1][j]; // 上方元素if (j > 0) diff[i][j] -= matrix[i][j - 1]; // 左方元素if (i > 0 && j > 0) diff[i][j] += matrix[i - 1][j - 1]; // 左上方元素}}return diff;
}void updateDiffArray(int** &diff, int x1, int y1, int x2, int y2, int a, int rows, int cols) {// Check if the indices are within boundsif (x1 >= 0 && x1 < rows && y1 >= 0 && y1 < cols &&x2 >= 0 && x2 < rows && y2 >= 0 && y2 < cols) {diff[x1][y1] += a;if (x2 + 1 < rows && y1 < cols) diff[x2 + 1][y1] -= a;if (x1 < rows && y2 + 1 < cols) diff[x1][y2 + 1] -= a;if (x2 + 1 < rows && y2 + 1 < cols) diff[x2 + 1][y2 + 1] += a;}
}int** build2DPrefixSumArray(int** matrix, int rows, int cols) {// 分配内存来存储前缀和数组int** prefixSum = new int*[rows];for (int i = 0; i < rows; i++) {prefixSum[i] = new int[cols];}// 初始化前缀和数组for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {prefixSum[i][j] = 0;}}// 计算第一行的前缀和for (int j = 1; j < cols; j++) {prefixSum[1][j] = matrix[1][j]+prefixSum[1][j-1];}// 计算第一列的前缀和for (int i = 2; i < rows; i++) {prefixSum[i][1] = prefixSum[i - 1][1] + matrix[i][1];}// 计算其他位置的前缀和for (int i = 2; i < rows; i++) {for (int j = 2; j < cols; j++) {prefixSum[i][j] = matrix[i][j] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];}}return prefixSum;
}int main()
{int n,q;cin>>n>>q;int** origin=new int*[n+1];for(int i=0;i<n+1;i++){origin[i]=new int[n+1];fill(origin[i],origin[i]+n+1,0);}int** diff=computeDifferenceArray(origin,n+1,n+1);for(int i=1;i<=q;i++){int x1,y1,x2,y2;cin>>x1>>y1>>x2>>y2;updateDiffArray(diff,x1,y1,x2,y2,1,n+1,n+1);}int** ans=build2DPrefixSumArray(diff,n+1,n+1);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)cout<<ans[i][j]<<" ";cout<<endl;}return 0;
}
