前缀和：前缀和顾名思义一般是指数组中前n项的和，通常用另一个数组来存储，如定义一个前缀和数组prefix[n]表示的是a1+a2+--an，这与等差数列中的Sn有着相像之处，但如何用代码实现的呢？
只需要定义一个前缀和数组--prefix[n]
for(int i=1;i<=n;i++)
{
prefix[i]=prefix[i-1]+a[i];
}这样就以O(n)的复杂度求了前缀和数组，那么这有什么用呢？
前缀和数组求的是前n项的和，是否可以求特定区间段的和呢？答案是可以，如我要求a[n]数组中区间[L,R]的和，那么结果就是前R项的和减去前L-1项的和，用前缀和数组表示就是prefix[R]-prefix[L-1],这样就以O(1)的复杂度求得了特定区间的和
利用这个技巧就可以解决洛谷P8218 【深进1.例1】求区间和，代码如下
#include<stdio.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
int a[N];
ll prefix[N];
int main()
{
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
prefix[i] = prefix[i - 1] + a[i];
}
int m; scanf("%d", &m);
while (m--)
{
int l, r; scanf("%d %d", &l, &r);
printf("%lld\n", prefix[r] - prefix[l - 1]);
}
return 0;
}这就是最简单的前缀和啦，但这只是一维上的前缀和，如果要求二维上的前缀和呢？如矩阵上的某块区域上的和呢？
如定义一个二维数组a[n][n],给定一个坐标(x,y)求（1，1）到（x，y）的矩形内所有元素的和，定义一个二维前缀和prefix[n][n]，可以从（1，1）递推到（n,n)
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
prefix[i][j]=prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+a[i][j];
}
}这就是二维前缀和的递推过程
从前向后递推如果我要求prefix[x][y],那么prefix[x-1][y]和prefix[x][y-1]我一定已经求过，如上图阴影部分，阴影重叠部分为prefix[x-1][y-1],加了两次，要减去一个，再加上a[x][y],就可求得prefix[x][y]
那么怎么求特定矩阵的和呢?依旧要从二维前缀和上考虑，如我要求(x1,y1)到(x2,y2)的矩阵上的和
可以从面积上考虑,代码如下
ans=prefix[x2][y2]-prefix[x1-1][y2]-prefix[x2][y1-1]+prefix[x1-1][x2-1];图解
考虑重叠部分为prefix[x1-1][y1-1]被减了两回，要加回来一个
这就是二维前缀和的基础使用啦，会了这个，就可以尝试解决蓝桥3811闪耀的灯光
以下为AC代码，要注意的是每次操作前后没有关联
#include<iostream>
using namespace std;
using ll = long long;
const int N = 305;
ll a[N][N];
ll prefix[N][N];
int main()
{
ll n, m, c; cin >> n >> m >> c;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
prefix[i][j]=prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1]+a[i][j];
}
}
int t; cin >> t;
while (t--)
{
ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
ll k; cin >> k;
k = k % (c + 1);
int num = (x2 - x1 + 1) * (y2 - y1 + 1) * k;
ll ans=prefix[x2][y2]-prefix[x1-1][y2]-prefix[x2][y1-1]+prefix[x1-1][y1-1];
cout << ans - num << endl;
}
return 0;
}然后就是差分：
差分一般是对数组进行差分，如定义一个差分数组diff[n]对a[n]进行差分,diff[i]=a[i]-a[i-1],
for(int i=1;i<=n;i++)
{
diff[i]=a[i]-a[i-1];
}那差分有什么用呢？差分可以让某一个区间加上一个 数值d，并且差分是可叠加的，对某一区间加d的操作为
diff[l]+=d,diff[r+1]-=d;看到这可能会奇怪这怎么就给区间加上d呢？这时区间还没有变化，在差分结束后需要对差分数组
做一个前缀和回复给原数组
for(int i=1;i<=n;i++)
{
a[i]=a[i-1]+diff[i];
} 开出的数组diff［］是为了记录每一个a［i］与a［i-1］的差，对diff［l］+=x，diff［r+1］-=x
是对从l到r的区间都加上x，再通过前缀和还原为原数组，a［i］=a［i-1］+diff［i］，当i等于l时
，a［l］就多了一个x，后继因为a［l+1］=a［l］+diff［l+1］，a［l］多x，则a［l+1］多x依次类推，直到a［r+1］=a［r］+diff［r+1］，a［r］多了x，diff［r+1］少了x，则a［r+1］恢复正常
并且差分操作前后无影响，但在多次差分的过程中不可以查看此时a[n]具体的值
到这可以看出差分与前缀和的一些关系，如果我对a[n]求前缀和，得到前缀和数组prefix[n]，那么反过来看我对prefix[n]进行差分，即prefix[i]-prefix[i-1]=a[i],prefix[i]的差分数组即为a[n]，对a[n]进行
差分得到diff[n]，diff[n]求前缀和就得到了a[n]，二者可逆
此外还有一种对区间加上某值的方法，直接初始化diff[n]全为0，不对其求a[n]的差分，直接对diff[l]+=d,diff[r+1]-=d;最后对diff[n]做前缀和，会发现除了标记的[l,r]区间内加上了d，其余diff[i]还是
0，可以对每个a[i]加上diff[i]即为值
while(t--)
{
cin>>d;
diff[l]+=d;
diff[r+1]-=d;
}
for(int i=1;i<=n;i++)
{
diff[i]+=diff[i-1];
a[i]+=diff[i];
}-这时可以尝试蓝桥1276小明的彩灯
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
long long a[N];
long long diff[N];
void solve(int n,int q)
{
for(int i=1;i<=n;i++)diff[i]=a[i]-a[i-1];
while(q--)
{
long long l,r,x;
cin>>l>>r>>x;
diff[l]+=x;
diff[r+1]-=x;
}
for(int i=1;i<=n;i++)
{
a[i]=a[i-1]+diff[i];
}
for(int i=1;i<=n;i++)
{
if(a[i]<0)
{
a[i]=0;
}
cout<<a[i]<<" ";
}
}
int main()
{
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
solve(n,q);
return 0;
}蓝桥3291区间更新
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+3;
int a[N]={0};
int diff[N];
void solve(int n,int m)
{
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)//差分
{
diff[i]=a[i]-a[i-1];
}
while(m--)//对区间进行m次操作，得到最后的结果
{
int x,y,z;
cin>>x>>y>>z;
diff[x]+=z;
diff[y+1]-=z;
}
for(int i=1;i<=n;i++)//前缀和还原
{
a[i]=a[i-1]+diff[i];
}
for(int i=1;i<=n;i++)//每次输出
cout<<a[i]<<" \n"[i==n];
}
int main()
{
int n,m;
while(cin>>n>>m)//多次输入
{
solve(n,m);
}
return 0;
}接下来是二维差分，对矩阵某一块加上d
定义diff[n][n],依旧从面积上考虑，对diff[x][y]+=d后，进行前缀和，其实是对从a[x][y]到a[n][n]的
矩形都加上了d，代码如下
diff[x1][y1]+=d;
diff[x2+1][y1]-=d;
diff[x1][y2+1]-=d;
diff[x2+1][y2+1]+=d;图解
考虑重叠部分，所以diff[x2][y2]+=d;
就可以写蓝桥18440二维差分啦，AC代码如下
//二维差分
#include<bits/stdc++.h>
using namespace std;
int a[1005][1005];
int diff[1005][1005];
int main()
{
int n,m,t;cin>>n>>m>>t;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
int x1,y1,x2,y2,d;
while(t--)
{
cin>>x1>>y1>>x2>>y2>>d;
diff[x1][y1]+=d;
diff[x2+1][y1]-=d;
diff[x1][y2+1]-=d;
diff[x2+1][y2+1]+=d;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
diff[i][j]+=diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1];
a[i][j]+=diff[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
} 最后是离散化：
离散化概述：
离散化是程序设计中一个非常常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中“只考虑我需要用的值”。离散化可以改进一个低效的算法，甚至实现根本不可能实现的算法。要掌握这个思想，必须从大量的题目中理解此方法的特点。
以下是一个简单的例题
这道题有很多种写法，以下提供两种
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
pair<int,int> p[N];
int a[N];
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
p[i]={a[i],i};
}
sort(p+1,p+1+n);
int rk=0;
for(int i=1;i<=n;i++)
{
if(i==1||p[i].first!=p[i-1].first)
{
rk++;
}
a[p[i].second]=rk;
}
for(int i=1;i<=n;i++)cout<<a[i]<<" ";
return 0;
} 利用pair分别记录值和下标，排序即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> num;
int a[100005];
int main()
{
int n;cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
num.push_back(a[i]);
}
sort(num.begin(),num.end());
num.erase(unique(num.begin(),num.end()),num.end());
for(int i=1;i<=n;i++)
{
int rk=lower_bound(num.begin(),num.end(),a[i])-num.begin();
cout<<rk+1<<" ";
}
return 0;
}利用c++库函数，排序后去重再二分查找
标签：前缀,int,差分,离散,prefix,x2,diff From： https://blog.csdn.net/zjy200646/article/details/145066886