前缀和
一维前缀和
arr为原数组 s 为前缀和之后的数组 s[n]=s[n-1]+arr[n];
二维前缀和
| j1 | j2 | j3 | j4 | j5 | j6 | |
| i1 | 7 | 8 | 3 | 4 | 3 | 4 |
| i2 | 1 | 2 | 3 | 4 | 5 | 6 |
| i3 | 7 | 8 | 3 | 4 | 3 | 4 |
| i4 | 1 | 3 | 4 | 6 | 0 | 4 |
最上面和最左边是坐标
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+arr[i][j]; 最后求结果，一个子区间 x1,y1,x2,y2 s[x2][y2]-s[x1-1][y2]-a[x2][y1-1]+s[x1-1][y1-1]
差分
一维差分
int l,r,c; cin>>l>>r>>c; arr[l]+=c; arr[r+1]-=c; 前缀和 brr[i]=brr[i-1]+arr[i];
二维差分
int x1,y1,x2,y2,c; cin>>x1>>y1>>x2>>y2>>c; brr[x1][y1]+=c; brr[x2+1][y1]-=c; brr[x1][y2+1]-=c; brr[x2+1][y2+1]+=c;
dijkstra
朴素版的dijkstra
这主要是用邻接矩阵来存图主要用来处理数据比较少的情况（稠密图）
const int N=1e3+10; int g[N][N];//用来存两点之间的距离 int dist[N]; //用来存起始点到任意一点的距离 bool st[N];//用来表示这个点是否已经访问过 int n;//代表所要求的点 memset(dist,0x3f,sizeof(dist)); dist[1]=0;//初始化一定不能少 for (int i = 0; i < n; i++) { int t = -1; for (int j = 1; j <= n; j++) { if (!st[j] && (dist[t] > dist[j] || t == -1)) { t = j; } } st[t] = true; for (int j = 1; j <= n; j++) { dist[j] = min(dist[j], dist[t]+g[t][j]); } }
二分
第一种
int l=0,r=n; while(l<r){ int mid=l+r>>1;//int mid=(l+r)/2 if(k<=arr[mid]){ r=mid; }else{ l=mid+1; } }
第二种
int l=0,r=n; while(l<r){ int mid=l+r+1>>1//int mid=(l+r+1)/2; if(k>=arr[mid]){ l=mid; }else{ r=mid-1; } }
floyd
这是一个多源汇最短路。时间复杂度为n^3
首先第一步还是初始化，与其他初始化不同的是这个算法的初始化变为：1
接着就是存图，仍然用邻接矩阵来存图 2
最后就是算法模板
1:
for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j){ g[i][j]=0; }else{ g[i][j]=INF; } } }
2:
for(int k=1;i<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ g[i][j]=min(g[i][j],g[i][k]+g[k][j]); } } }
这个算法是基于一个动态规划的思想
g[k,i,j] 表示从i到j中间经过k个点
g[k,i,j]=min(g[k-1,i,j],g[k-1,i,k]+g[k-1,k,j])//经过第k个点和不经过第k个点，取最小值
MySQL中的索引的情况
索引(index)是什么,相当于一本书的目录,根据目录中每个章节对应的页码,就能快速地找到对应的章节,MySQL中的索引也是一样,当从数据库中进行查找的时候,例如按照一定的条件来查找
查找可以遍历表,但是遍历表操作比较低效,就需要想办法尽量的避免遍历,可以通过一些特殊的数据结构,来表示一些记录的特征,通过这些特征来减少比较的次数,加快比较的效率
索引的主要意义就是进行查找,要提高查找的效率
查找效率提高了,但同时也要付出一些代价:
书的目录是废纸的,数据库的索引也是需要额外的存储空间的,数据量越大,索引消耗的存储空间就越多,书的目录如果确定了,后续每次对书的内容进行调整,都可能影响到目录的准确性,就需要重新调整目录,数据库的索引也是一样,当进行增删改查的时候,往往需要同步的调整索引的结构
索引带来的好处:提高了查找的效率,索引带来的坏处:占用了更多的空间,拖慢了增删改的速度
