目录
一维前缀和
如果直到原数组arr的所有元素，那么我们只需要重新构造一个前缀和数组nums即可，从下标1可以开始进行赋值，每次nums[i] 得到的结果就是【0 ~ i】 下标的所有arr数组的和，即arr数组的前缀和！
那么前缀和有什么作用呢？！！！
当我们想要知道一维数组的某个连续的区间的数组和，就可以直接在O(1) 的时间复杂的来直接进行获取该值，eg：
int sum = nums[2] - nums[0]; // 等价于 arr[1] + arr[2]就表示的是下标为2的位置 减去 下标为0 位置的前缀和数组，得到的结果就是原数组arr[1] + arr[2]的结果。
由此就可以看出，前缀和数组，是在以空间换取时间的前提下，O(n)下遍历数组，得到一个空间复杂度也为O(n) 的nums数组，在O(1) 的条件下，直接得到关于[l,r]区间内的arr数组的和。
void fn() {
vector<int> arr = {0,1,2,3,4,5};
vector<int> nums(arr.size(),0);
for(int i = 1; i < arr.size(); i++) {
nums[i] = nums[i - 1] + arr[i];
}
for(auto e : nums) cout<<e<<" ";cout<<endl; // 0 1 3 6 10 15
}由于nums会存在[i - 1] 区间，那么一般下标都是从1开始，防止越界，所以只要将arr数组从所有元素往后移动一位，也从1开始，就正好实现了nums 与 arr数组的下标对应；
学会了一维前缀和？？？那么直接上强度！！！
重新排序：蓝桥杯一道经典的前缀和算法题，直接暴力90%的测试用例！重新排序
题目意思也很好理解，就是用最优的排序，来比较排序前后所选择的所有区间内，数字总和的最大差值！
细心的小伙伴这个时候就能想到啦，只要每次排序都记录重复次数最多的区间，然后把最大值放到这个重复次数最多的区间就可以啦！ 没错这就是暴力前缀和的思想，只需要求出一个前缀和数组nums，然后重复m次，选择区间[l,r]内的数字总和时,在O(1)下就能得到结果，sum = nums[r] - nums[l - 1];
最关键的就是，要记录每个区间重复的次数，这里就要开辟新的数组来记录重复出现的次数，在重复得到m次区间sum的条件下，又要在 r - l 的次数内记录当前下标出现的次数在index数组内，也就是O(m * n) 的时间复杂度，这里就会发现，过不了最后一个测试用例！！！（超时）
那么我们上面本身就是要遍历数组是O(n),如果在m次操作下，任然要再次遍历数组来记录重复出现的下标次数，未免时间复杂度太高，也就是在这里进行优化，也就是后面要进行学习的差分思想~~~~ 现在可以尝试着手撕暴力代码，然后继续学习后面的差分思想
#include <bits/stdc++.h>
using namespace std;
#define int long long
void fn() {
int n;cin>>n;
vector<int> nums(n + 1);
auto a = nums;
auto b = nums;
auto nums_begin = nums;
for(int i = 1; i <= n; i++) {
cin>>b[i];
nums[i] = nums[i - 1] + b[i];
}
vector<int> index(n + 1); //记录重复最多的位置
int ret_min = 0;
int m;cin>>m;
int p = m;
vector<int> ll;
auto rr = ll;
while(m--) {
int l,r;cin>>l>>r;
ll.push_back(l);
rr.push_back(r);
int sum = nums[r] - nums[l - 1];
ret_min += sum;
for(int i = l; i <= r; i++) index[i]++;
}
map<int,vector<int>> hash;
for(int i = 0; i < index.size(); i++) {
hash[index[i]].push_back(i);
}
// for(auto& e : hash) {
// cout<<e.first<<":";
// for(auto& k : e.second) {
// cout<<k<<" ";
// }
// cout<<endl;
// }
sort(b.begin(),b.end(),greater<int>());
// for(auto e : nums) cout<<e<<" ";cout<<endl<<endl;
for(auto& e : hash) {
for(auto& k : e.second) {
a[k] = b.back();
b.pop_back();
}
}
// for(auto e : a) cout<<e<<" ";cout<<endl;
// cout<<endl;
int rep = 0;
for(int i = 1; i <= n; i++) {
nums_begin[i] = nums_begin[i-1] + a[i];
}
int ret_max = 0;
for(int i = 0; i < ll.size(); i++) {
int sum = nums_begin[rr[i]] - nums_begin[ll[i] - 1];
ret_max += sum;
}
cout<<ret_max - ret_min<<endl;
}
signed main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t = 1;while(t--) fn();
return 0;
}一维差分
差分是什么？
以O(n)的时间复杂度 ，在数组arr内进行m次修改 不同 [l, r]区间内的值；
一般进行这样的操作，正常来说就是遍历m次，然后再遍历数组从i = l 开始到 i = r结束来进行修改数组，也就是说O(m * n)的条件下才能完成这个操作
先说结论：
[L, R] + V <=> d[L] + V ,d[R] - V
可能你现在看不懂，没关系，看到下面的讲解，你会豁然开朗，也许你会跟我一样，认为这是哪个天才想到的这么完美的办法~~~~
这里只是操作了一次，那么我们将他推广到3次或者更多次不同区间的操作：
那么这里就能看出，上面给出的结论是正确的，不需要再次遍历数组，而只是需要求出每次的差值进行计算d[l] + v,d[r + 1] - v即可！！！那么他的原理是什么呢？？？
从图中我们可以看出差分数组d从下标L开始进行改变，那么前缀和数组sumd 后续的值都会跟着进行改变，知道我们想要停止的那个区间R后面的一个值进行减掉相应的值既可停止后续前缀和的改变！！！也就是说现在我们就能理解为什么会有当前公式的存在~~~~直接改变差分数组的变量值，操作m次后，最后再求差分数组的前缀和sumd数组也就是修改不同区间的值后最后能够得到的修改结果，由于最后要遍历差分数组d，最后的时间复杂度就是O(n)
那么通过上面的学习也不知道你是否有跟我一样的感受，被当前的操作给惊艳到！下面就是上面题目的优化代码：
核心：我们的目的还是为了求出index数组，也就是求出最后操作m次不同区间数组的最终修改值，那么我们就用当前差分思想，能够将原来的时间复杂度O(m * n) 优化到O(n) 当m足够大的时候这总优化也是一种质的飞跃~~~~
while(m--) {
int l,r;cin>>l>>r;
ll.push_back(l);
rr.push_back(r);
int sum = nums[r] - nums[l - 1]; // 前缀和相减
ret_min += sum;
// for(int i = l; i <= r; i++) index[i]++; // 暴力
d[l]++;
if(r + 1 <= n) d[r+1]--;
}
for(int i = 1; i <= n; i++) {
index[i] = index[i - 1] + d[i]; // 修改后的前缀和
} 最终：ac代码的结果，整体来说大差不差，只是多了一个差分的优化思想！
#include <bits/stdc++.h>
using namespace std;
#define int long long
void fn() {
int n;cin>>n;
vector<int> nums(n + 1); //前缀和数组
auto a = nums; //排序后数组
auto b = nums; //原始数组
auto nums_begin = nums;
auto d = nums;
auto sumd = nums;
auto index = nums;
for(int i = 1; i <= n; i++) {
cin>>b[i];
nums[i] = nums[i - 1] + b[i];
}
// vector<int> index(n + 1); //记录重复最多的位置
int ret_min = 0;
int m;cin>>m;
int p = m;
vector<int> ll;
auto rr = ll;
while(m--) {
int l,r;cin>>l>>r;
ll.push_back(l);
rr.push_back(r);
int sum = nums[r] - nums[l - 1]; // 前缀和相减
ret_min += sum;
// for(int i = l; i <= r; i++) index[i]++; // 暴力
d[l]++;
if(r + 1 <= n) d[r+1]--;
}
for(int i = 1; i <= n; i++) {
index[i] = index[i - 1] + d[i]; // 修改后的前缀和
}
// for(auto e : index) cout<<e<<" ";cout<<endl;
map<int,vector<int>> hash;
// 重新排序 记录出现次数最多的位置
for(int i = 0; i < index.size(); i++) {
hash[index[i]].push_back(i);
}
// for(auto e : sumd) cout<<e<<" ";cout<<endl;
sort(b.begin(),b.end(),greater<int>());
// for(auto e : nums) cout<<e<<" ";cout<<endl<<endl;
for(auto& e : hash) {
for(auto& k : e.second) {
a[k] = b.back();
b.pop_back();
}
}
// for(auto e : a) cout<<e<<" ";cout<<endl;
// cout<<endl;
int rep = 0;
for(int i = 1; i <= n; i++) {
nums_begin[i] = nums_begin[i-1] + a[i];
}
int ret_max = 0;
for(int i = 0; i < ll.size(); i++) {
int sum = nums_begin[rr[i]] - nums_begin[ll[i] - 1];
ret_max += sum;
}
cout<<ret_max - ret_min<<endl;
}
signed main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t = 1;while(t--) fn();
return 0;
} 二维前缀和
从图中可以看出，要求出二维数组前缀和就是当前位置[i , j] 的左侧方块nums[i][j - 1] + 上侧方块nums[i - 1][j]然后再减去二者方块重复的面积（粉色面积） 加上当前放各的大小即可。
一般，我们都会为原数组都开一行 和 一列，这样求出前缀和数组nums的时候就会防止越界，arr[i][j]的下标就会一一对应，如果没有多开一行 和 一列，那么计算前缀和数组的时候就只需要单独考虑数组越界情况arr[i - 1][j - 1];
vector<vector<int>> arr(5,vector<int>(5));
auto nums = arr;
for(int i = 1; i <= 4; i++) {
for(int j = 1; j<= 4; j++) {
arr[i][j] = i + j - 1 - 1;
}
}
for(int i = 1; i <= 4; i++) {
for(int j = 1; j <= 4; j++) {
nums[i][j] = nums[i - 1][j] + nums[i][j - 1] - nums[i - 1][j - 1] + arr[i][j];
}
}
for(int i = 0; i <= 4; i++) {
for(int j = 0; j <= 4; j++) {
cout<<nums[i][j]<<" ";
}
cout<<endl;
}
// for(int i = 0; i <= 4; i++) {
// for(int j = 0; j <= 4; j++) {
// cout<<arr[i][j]<<" ";
// }
// cout<<endl;
// }可以看出二维前缀和数组跟一维前缀和数组没有什么区别，都是对当前位置的值 再加上前面一层和一列所包含的数组大小
那么就拥有跟一维前缀和数组一样的性质，就是再O(n * n) 的时间复杂度的条件下，来构建这个二维前缀和数组，可以再O(1) 的条件下来得到关于任意两点之间所围成的面积大小：
当我想要得到红色框框所框选的数字和，那么就可以再O(1)下通过加减法直接得到：
int x1,x2,y1,y2;cin>>x1>>y1>>x2>>y2;
int sum = nums[x2][y2] - nums[x2][y1-1] - nums[x1-1][y2] + nums[x1-1][y1-1];二维差分
学会了一维差分，二维差分就非常简单了~~~~
先说结论：
d[x1][y1] += v
d[x2+1][y1] -= v
d[x1,y2+1] -= v
d[x2+1][y2+1] += v
如图：
当我按照差分思想构造差分数组的时候，对某一个范围[x1][y1]~[x2][y2]这个矩形范围进行修改不同的值的时候，我就要考虑后续的其他地方不会被我修改到，也就是要将这个矩形的三个角落进行还原，看图就能非常的清晰观察到，最后有一块矩形的地方被重复-1，要将他还原只能再次+1
步骤：
1.首先就是创建新的差分数组d，然后进行填表，按照[L,R]m次的不同区间进行差分；
2.得到d后创建index前缀和差分数组；
3.最后一步，与原数组结合，得到最终的修改数组
vector<vector<int>> arr(5,vector<int>(5));
auto nums = arr;
auto d = arr;
auto index = arr;
arr = {
{0,0,0,0,0},
{0,1,5,6,8},
{0,9,6,7,3},
{0,5,3,2,4}
};
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 5; j++) {
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
int m;cin>>m;
while(m--) {
int x1,y1,x2,y2,v;cin>>x1>>y1>>x2>>y2>>v;
d[x1][y1] += v;
if(x2 + 1 < 4) d[x2+1][y1] -= v;
if(y2 + 1 < 5) d[x1][y2+1] -= v;
if(x2 + 1 < 4 && y2 + 1 < 5) d[x2 + 1][y2 + 1] += v;
}
cout<<endl;
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 5; j++) {
cout<<d[i][j]<<" ";
}
cout<<endl;
}
for(int i = 1; i < 4; i++) {
for(int j = 1; j < 5; j++) {
index[i][j] = index[i-1][j] + index[i][j-1] - index[i-1][j-1] + d[i][j];
}
}
cout<<endl;
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 5; j++) {
cout<<index[i][j]<<" ";
}
cout<<endl;
}
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 5; j++) {
arr[i][j] += index[i][j];
}
}
cout<<endl;
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 5; j++) {
cout<<arr[i][j]<<" ";
}
cout<<endl;
}