前缀和和差分笔记

前缀和和差分笔记

一维前缀和

示意图如下：

代码：

**核心公式：sum[i]=sum[i-1]+a[i];（计算前缀和的）**

#include<bits/stdc++.h>
using namespace std;
const int N=10000;
#define ll long long
int a[N],sum[N];
int main(){cin>>a[0];sum[0]=a[0];for(int i=1;i<num;i++){cin>>a[i];sum[i]=sum[i-1]+a[i];}
}

应用：

用于计算区间和，公式为sum[R]-sum[L-1]（计算第L位到第R位的区间和）

P8218 【深进1.例1】求区间和 - 洛谷

二维前缀和

示意图

在写核心公式之前先明确几个概念

什么是sum[x] [y]

代码

核心公式

1.ans=sum[x2] [y2]-sum[x1-1] [y2]-sum[x2] [y1-1]+sum[x1-1] [y1-1]

怎么记？首先混搭，然后一行变一行就不变，且x2不变，最后减掉都变

如：x2不变则x1变，变为x1-1

sum[x2] [y2]-sum[x1-1] [y2]-sum[x2] [y1-1]-sum[x1-1] [y1-1]

默写完毕

2. sum[i] [j]=sum[i-1] [j]+sum[i] [j-1]-sum[i-1] [j-1]+g[i] [j];

左右都加顺便加自己减去重复的

记得在那之前要写好你的三个条件

	if(!x1&&!y1)return sum[x2][y2];
//	如果起点在00，则直接输出sumif(!x1)return sum[x2][y2]-sum[x2][y1-1];if(!y1)return sum[x2][y2]-sum[x1-1][y2];
//口诀就是固定那个，那个位置就不变（如固定x1，则x2不变，y1变则需要减掉的就是sum[x2][y1-1]）

//二维前缀和
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 10000;
int n = 3, m = 4;
int g[3][4] = {{1, 2, 6, 8},{9, 6, 7, 3},{5, 3, 2, 4}
};
int sum[N][N];
void presum() {sum[0][0] = g[0][0];for (int i = 1; i < n; i++) {sum[i][0] = sum[i - 1][0] + g[i][0];//第一列,固定列，前缀和}for (int i = 1; i < n; i++) {sum[0][i] = sum[0][i - 1] + g[0][i]; //第一行，固定行，前缀和}for (int i = 1; i < n; i++) {for (int j = 1; j < m; j++) {sum[i][j] = g[i][j] + sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];}}
}
int getsum(int x1, int y1, int x2, int y2) {if (!x1 && !y1)return sum[x2][y2];
//	如果起点在00，则直接输出sumif (!x1)return sum[x2][y2] - sum[x2][y1 - 1];if (!y1)return sum[x2][y2] - sum[x1 - 1][y2];return sum[x2][y2] - sum[x2][y1 - 1]-sum[x1-1][y2]+sum[x1-1][y1-1];}
int main() {presum();cout<<getsum(1,1,2,2);return 0;
}

P1719 最大加权矩形 - 洛谷

通过这道题我们能将这个过程再次简化

//最大加权矩形
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=10000;
ll ans=INT_MIN;
ll g[N][N];
ll sum[N][N];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>g[i][j];sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+g[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int k=i;k<=n;k++){for(int q=j;q<=n;q++){ans=max(sum[k][q]-sum[k][j-1]-sum[i-1][q]+sum[i-1][j-1],ans);}}}}cout<<ans;return 0;
}

一维差分：

差分可以看成前缀和的逆运算。

不用差分的话每次操作都必须要循环一次，时间复杂度比较高

那么久简单啦，每次操作我们就只需要操作两位数，比如，我操作【2,4】都加2就等价于d【2】+v, d[4+1]-v

为什么呢，我们知道，前缀和会怎么样，会加上前面的数，我的前面比原来大了2，那么通过前缀和求出来的现在的值也就大了2，那后面我不想改变怎么办，简单，在不想改变的那个位置减2，不就抵消了吗?

d为差分数组

sumd为对差分数组求前缀和

二分思想

二分查找和二分答案其实本质都是二分思想，二分思想的本质模版其实就是

int bsearch(int l, int r)
{//l为初值，r为末尾值//当左边和右边不相遇时while (l < r){//求取中间用（l+r)/2int mid = (l + r )>> 1;//判断标准，如果标准符合，让其中一方缩小范围if (check(mid)) r = mid;else l = mid + 1;}//最后返回一个你想要的值（左边一般是最小值，右边一般是最大值）return l;
}

左边是最大的最小值，右边是最小的最大值

其实就是都一样的套路，当两个指针不相遇的时候，定义mid为l+(r-1)>>1

定义一个check函数，如果可以在怎么样

其中l=mid+1，r=mid

还可以在后面加点其他思路的东西

二分查找

折半查找，这里只讲他怎么用，具体概念可以参考大佬的文章：【算法笔记】二分查找 && 二分答案 （超详细解析，一篇让你搞懂二分）-CSDN博客

使用场景

前提：这个数据是有序的，无需用sort变有序

当问题需要查找元素是否存在或者求元素的坐标的时候可以使用

方法

其实是在划分区域，如图为了找出红蓝的边界，使用上述模版，其check函数就可以判断他是蓝色还是红色，然后如此循环即可找出一个红蓝边界，mid的最终结果其实就是check函数的边界

如：check为红蓝判断函数，则mid最后结果为红蓝边界，l为蓝色，r为红色

check函数为是小于等于5，l为最后一个小于等于5的数字，mid为小于等于5的边界

以此类推

上述过程可以用代码完成，但是如果只是为了查找就会比较简单，直接用现有的函数即可

1.如果你是想要查找是否存在使用binary_search()放回一个bool值

2.查找第一个大于等于x的数组位置，lower_bound(a.begin(),a.end(),x)

3.查找第一个大于x的数组位置。upper_bound(a.begin(),a.end(),x)

代码

//二分查找
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<int>a={1,2,3,5,5,5,8,8,9,9};
//int binary(){
//	int l=-1,r=10;
//	while(l+1!=r){
//		int m=floor((l+r)/2);
//		if(a[m]==5)
//			l=m;
//		else
//			r=m;
//	}
//	return l;
//}
int main(){
//	返回一个bool值,查看这个元素是否存在int ans=binary_search(a.begin(),a.end(),15);//若不存在返回int ans1=(lower_bound(a.begin(),a.end(),5)-a.begin());int ans2=(upper_bound(a.begin(),a.end(),5)-a.begin());cout<<ans<<" "<<ans1<<" "<<ans2;return 0;
}

例题：

P1102 A-B 数对 - 洛谷

灵活运用好lower_bound(第一个大于等于)和up_bound（第一个大于）

我们用第一个大于减去第一个大于等于得到的数量不就是重复的的那一些

2 3 3 3 3 3 4

大于等于3 返回1

大于3 返回6

则可以算出3有6-1=5个

//二分查找AB数对
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[200100];
int main(){ll n,m,ans=0;cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);for(int i=0;i<n;i++){ans+=(upper_bound(a,a+n,a[i]-m)-a)-(lower_bound(a,a+n,a[i]-m)-a);}cout<<ans;return 0;
}

二分答案

那什么是二分答案呢？

使用场景

前提是这个区间是有序的，无序必须想方法变有序

对于一个问题，它的答案属于一个区间，当这个区间很大时，暴力超时。如果这个区间有序，我们则可以折半查找，选定一个标准，如果中间大于这个标准则答案在左边，如果小于则在右边，由此往复

方法及其代码

int bsearch(int l, int r)
{//l为初值，r为末尾值//当左边和右边不相遇时while (l < r){//求取中间用（l+r)/2int mid = (l + r )>> 1;//判断标准，如果标准符合，让其中一方缩小范围if (check(mid)) r = mid;else l = mid + 1;}//最后返回一个你想要的值（左边一般是最小值，右边一般是最大值）return l;
}

例题：

例题：P1678 烦恼的高考志愿 - 洛谷

其中两个简单样例

1 100000
1000000
以下省略100000个0

输出 100000000000

429 517
7278 2729 3355 1555 595 7805 3741 3566 9466 1505 7419 9102 3236 3500 4592 307 9203 8880 8819 1480 5376 6897 3911 610 6376 4282 8522 5673 7206 5983 4695 8365 5799 9993 2575 4003 2377 2137 2968 982 466 9513 9234 1570 2079 7938 4516 806 4672 6900 4416 7508 2156 3963 5915 9896 8067 3708 6060 7315 1620 9070 7178 1542 209 6494 9107 978 7339 7319 5048 1870 6342 7869 7372 4688 741 5358 719 7100 1676 5659 4037 5825 6059 8794 7262 4350 5907 7882 4151 9194 7494 9752 4544 7377 3826 3268 2854 1437 3292 6055 9889 259 5139 6519 3088 6456 6733 8351 1097 9763 4016 1844 1019 2539 4562 6208 1603 4645 295 8685 9661 6699 3845 7790 6676 341 1878 8984 4395 5951 7551 5434 5977 6615 2091 5684 2100 4341 7353 4783 2864 5975 1944 7786 9326 8182 463 2650 8034 1239 8187 5704 8065 1817 826 7427 3106 6072 9140 2432 4514 574 5095 7696 6485 2495 833 2279 6703 2880 6002 1093 5494 4988 859 2153 260 9333 1949 1020 7153 7197 6866 6066 4860 5000 9588 620 6179 6913 2503 8188 3921 6325 6852 8031 4735 4672 1819 1998 5729 1984 2704 8201 1157 506 1132 3840 7487 9820 8205 9424 558 9379 331 1470 5587 9410 2497 2437 3112 3507 8898 699 3808 1333 2196 5951 314 7401 5283 2467 4700 5200 6907 8993 4824 6250 9202 3645 8580 9909 5606 563 2430 5730 8434 6382 8367 9938 2751 124 7395 3495 8416 3497 7283 751 1095 3803 1694 1320 4031 1561 8769 5781 673 5315 8278 827 2343 8053 3181 8397 8241 8737 5896 3446 5572 1141 6776 7396 1959 6151 6641 8670 7894 9428 6227 34 1464 7715 1358 7628 9449 6876 2166 5231 967 173 3547 2359 3367 9742 5978 2594 1400 449 2413 2888 4657 4748 5439 4892 3186 4717 1375 4152 8380 8038 9169 7861 6949 9061 7978 4176 9313 2485 8926 1561 2787 3925 6224 4608 8499 9501 8485 3971 4344 1961 9090 7110 129 1213 9159 5502 8918 5442 50 3197 2100 3126 3966 3934 8279 8750 3208 3623 5919 8977 6416 9065 5569 5199 5114 8893 7932 6667 4551 8814 5999 4848 9479 3617 9656 5513 8725 834 3010 1507 3 7018 7104 7550 169 3774 3796 4316 3729 6407 8540 7014 6464 3535 6400 8727 8131 7747 7011 6350 4455 7090 8353 5938 5833 2378 7865 9821 1087 3294 1723 4853 3500 3815 7995 4943 5297 5196 6646 8049 1674 5481 4178 1548 5438 6142 233 
2028 4767 1452 5585 6046 3185 3919 4869 4886 1188 3349 8932 1797 5701 258 8231 115 237 5444 987 8003 2041 9922 385 548 8349 2435 1629 5438 1149 8945 8632 78 4811 4738 1085 829 5629 1096 9764 1927 8333 5213 9783 5575 1575 4872 8766 1440 6962 3793 5756 1017 716 7025 4732 1176 8533 9364 6778 8663 3759 7424 8289 1863 532 6235 2622 9246 6013 2733 4768 9963 2817 1578 6756 9838 6254 7343 1308 305 3455 8918 406 8693 8239 2571 6335 5367 7392 9398 6771 6768 448 2298 8180 6411 6568 4122 670 5873 2720 1679 4279 4046 1861 7566 2101 9415 909 2682 4685 4153 4139 7455 3688 142 626 9460 2357 8179 8681 6835 2980 5462 1822 9041 9887 7609 3187 4866 3145 3905 7033 2908 2548 8294 4758 1913 7742 6754 5985 1906 7389 9164 9400 1362 3952 4063 8116 3276 338 3543 7563 1103 7674 818 6427 9023 5926 4436 1258 3505 537 8634 6822 7986 9239 4839 9435 601 8538 5555 4898 1614 4460 3339 4641 9212 4282 6181 607 7823 3127 6878 3057 2077 4294 564 5731 5786 9872 6477 8864 5533 9878 524 5653 379 1188 7065 7666 6124 1665 6318 7250 530 8268 8231 7195 1608 7807 2406 920 9871 9008 5154 6774 6326 5612 6789 1875 1865 8467 7950 8781 2438 384 7758 4977 8832 9869 2327 9755 7596 6152 6460 20 676 5208 9756 9019 3644 486 7741 8561 739 1033 4435 5829 3352 4428 3396 968 9942 2552 5509 8257 4912 3456 5927 9093 589 6336 2953 2166 9288 4935 9554 269 5278 9337 1599 6136 2968 1104 4562 830 4037 4191 3872 4098 1845 5569 5659 4713 8083 9762 3986 9478 6027 784 7196 3985 7693 3839 5862 1201 2959 3536 9278 1882 9175 2288 3751 8208 6521 1620 4815 6406 660 7674 2707 4295 589 8924 3245 3721 6944 7685 9480 6896 6788 7365 4131 4289 8693 22 2088 6583 4622 1859 995 3998 8508 5856 1633 2880 8608 9817 7923 5547 7089 7987 6356 382 8254 9237 3247 8994 6047 9335 4764 6560 3068 9081 7108 4343 2110 3876 4265 2670 538 4964 7934 3687 5931 1279 419 1994 6227 6360 7393 2783 3060 3123 7103 200 6708 8682 4368 225 3328 6824 4863 715 3061 8569 8477 7467 9966 6178 5863 7674 559 4057 8866 8823 9709 8022 2961 4871 8415 9277 8126 770 207 806 7164 7410 9372 1284 4007 5606 5124 1921 6395 969 1189 7933 1013 7093 1942 5479 17 8709 1953 7547 5389 6813 8717 6976 6680 2451 5337 3247 5351 2494 7978 1095 6391 3229 2471 9632 294 7570 9671 5075 4509 6479 5697 2730 3298 47 8864 1185 2727 9917 3989 7475 1433 6592 1349 6461 7385 6931 2916 1289 4925 619 5637 1353 9313 2972 8303 8865 5923 8640 2168 2106 8590 5208 1276 1497 2348 2320 4420 3045 2443 1611 2427 6680 6139 6756 8287 8893 970 9291 8287 1863 9639 3617 8071 128 8212 9602 4016 7263 2594 4485 1737 1079 5251 6526 3124 5382 3668 

输出：5865

解答

初版

这道题主要是给我们指定的分数线数组A

我们拿自己的成绩G在A中找到最后一个小于等于自己的

那么对于本身不满意度最小的要么就是这个最后一个小于等于自己的，要么就是下一个比自己大，相差虽然不能确定，但是你要知道二分答案就是一个划分区域的工具

二刷：后面的理解

是不是要找最小，那就二分，是不是找本身最小，那就本身入局，作为边界，则可以找出本身边界旁边的大小值

#include<bits/stdc++.h>
using namespace std;
#define ll long long
//const int N=100010;
//int a[N];
//我们的模版二分答案是选出正确答案，但是在实际做题的时候我们要结合实际情况
//来写check
vector<int >a;int ans(int k){int sum=0;int l=0;int r=a.size();int mid;while(l<r){mid=(l+r)>>1;if(a[mid]<=k)l=mid+1;else r=mid;}
//	比第一个还低就没救了if(k<=a[0]){sum=abs(a[0]-k);}
//	否则就得设计算法elsesum=min(abs(a[l-1]-k),abs(a[l]-k));return sum;
}
int main(){int n,m,x;cin>>n>>m;
//	高考各个学校分数线for(int i=0;i<n;i++){cin>>x;a.push_back(x);}sort(a.begin(),a.end());ll t,ansum=0;
//对每个人的成绩进行遍历for(int i=0;i<m;i++){cin>>t;ansum+=ans(t);}cout<<ansum;return 0;
}

记得开ll给ansum，因为加起来可能会爆

[P2678 NOIP 2015 提高组] 跳石头 - 洛谷

int bsearch(int l, int r)
{//l为初值，r为末尾值//当左边和右边不相遇时while (l < r){//求取中间用（l+r)/2int mid = (l + r )>> 1;//判断标准，如果标准符合，让其中一方缩小范围if (check(mid)) r = mid;else l = mid + 1;}//最后返回一个你想要的值（左边一般是最小值，右边一般是最大值）return l;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[50110],l,n,m;
bool check(int d){int cnt=0,pos=0;//记录一下被移走了多少石头,pos为当前位置for(int i=1;i<=n;i++){if(a[i]-pos<d)//这一步说明是在跳跃cnt++;//略过则直接过elsepos=a[i];//跳过就存储位置}return cnt<=m;
}
int main(){cin>>l>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}	a[++n]=l;int l1=1,r=l,mid,ans=-1;while(l1<=r){mid=(l1+r)/2;if(check(mid)){l1=mid+1;ans=mid;}else{r=mid-1;}}cout<<ans;return 0;}