差分
差分
差分相当于前缀和的逆运算。
目的：数组中一段数+x时间复杂度降低
具体做法：假设一个数组的前缀和为原数组
一维差分：
预处理：
1234567int a[N],b[N];/*(1)*/for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];/*(2)*/for(int i=1;i<=n;i++){ b[i]+=a[i]; b[i+1]-=a[i];}
添加数：
1234567int l,r,c;while(m--){ cin>>l>>r>>c; b[l]+=c; b[r+1]-=c;}
二维差分：
差分函数：
1234567void insert(int x1,int y1,int x2,int y2,int c){ a[x1][y1]+=c; a[x2+1][y1]-=c; a[x1][y2+1]-=c; a[x2+1][y2+1]+=c;}
预处理：
12for(int i=1;i& ...
前缀和
前缀和
目的：求原数组中某段数的和（O（1））
具体做法：做一个预处理，定义一个新数组储存原数组前i个数的和
一维前缀和：
预处理：
12int sum[N],a[N];for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
查找：（求l~r之间的数）
1num=sum[r]-sum[l-1];
二维前缀和：(当成方格形)
预处理：
1234int sum[N][M],a[N][M];for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum[i][j]=sum[i-1][j-1]-sum[i-1][j]-sum[i][j-1]+a[i][j];
查找：（求(l1,r1)~(l2,r2)之间的数）
1num=sum[l2][r2]-sum[l2][r1-1]-sum[l1-1][r2]+sum[l1][r1];
高维前缀和：（类比）
STL
STL简记
hash
哈希表
目的：将大范围的多个数映射到一个0-N的集合中
常见哈希表：
1.普通哈希表
处理冲突方式：
1.开放寻址法
image-20210911164017945
123456789101112131415161718const int N=2e5+3,num=0x3f3f3f3f;int h[N];int find(int x){ int k=(x%N+N)%N; while(h[k]!=num&&h[k]!=x) { k++; if(k==N)k=0; }}//添加int k=find(x);h[k]=x;//查找int k=find(x);if(h[k]!=num)//存在 else //不存在
2.拉链法：一个数组存储所有哈希值
image-20210911155856034
常用操作：1.添加2.查找
3.删除（额外数组进行标记，不常用）
代码
123456789101112131415161718const int N=1 ...
Introduction
学着搭了个简单的博客，用来简单记录自己的算法学习和游戏相关。