前缀和和差分和dijkstra算法和二分算法和floyd算法

前缀和

一维前缀和

arr为原数组 
s 为前缀和之后的数组
s[n]=s[n-1]+arr[n];
1
2
3

例题

二维前缀和

最上面和最左边是坐标

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]
1
2
3
4

差分

一维差分

int l,r,c;
cin>>l>>r>>c;
arr[l]+=c;
arr[r+1]-=c;
前缀和
brr[i]=brr[i-1]+arr[i];
1
2
3
4
5
6

例题

二维差分

    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;
1
2
3
4
5
6

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]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

例题

二分

第一种

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;
    }
}
1
2
3
4
5
6
7
8
9

第二种

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;
    }
}
1
2
3
4
5
6
7
8
9

例题1
例题2

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;
        }
    }
}
1
2
3
4
5
6
7
8
9

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]);
        }
    }
}
1
2
3
4
5
6
7

这个算法是基于一个动态规划的思想
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个点，取最小值
1

例题

MySQL中的索引的情况

索引(index)是什么,相当于一本书的目录,根据目录中每个章节对应的页码,就能快速地找到对应的章节,MySQL中的索引也是一样,当从数据库中进行查找的时候,例如按照一定的条件来查找

查找可以遍历表,但是遍历表操作比较低效,就需要想办法尽量的避免遍历,可以通过一些特殊的数据结构,来表示一些记录的特征,通过这些特征来减少比较的次数,加快比较的效率

索引的主要意义就是进行查找,要提高查找的效率

查找效率提高了,但同时也要付出一些代价:

书的目录是废纸的,数据库的索引也是需要额外的存储空间的,数据量越大,索引消耗的存储空间就越多,书的目录如果确定了,后续每次对书的内容进行调整,都可能影响到目录的准确性,就需要重新调整目录,数据库的索引也是一样,当进行增删改查的时候,往往需要同步的调整索引的结构

索引带来的好处:提高了查找的效率,索引带来的坏处:占用了更多的空间,拖慢了增删改的速度