倍增算法详解 倍增算法是一种高效的算法设计技巧，主要用于解决需要快速定位或计算的问题，特别是在处理区间查询、最近公共祖先(LCA)、后缀数组等问题时非常有用。

基本思想 倍增算法的核心思想是通过预处理数据，构建一个"跳跃表"或"倍增表"，使得每次查询时可以以2的幂次方的步长快速跳跃，从而将线性时间复杂度优化为对数时间复杂度。

主要应用

1. 最近公共祖先(LCA) ‌预处理‌：

构建每个节点的2^k级祖先表 时间复杂度：O(n log n) ‌查询‌：

先将两个节点调整到同一深度 然后一起向上跳跃寻找LCA 时间复杂度：O(log n) 2. 区间最值查询(RMQ) 使用ST表(Sparse Table)实现：

预处理构建区间长度为2^k的最值表 查询时通过两个重叠的区间组合得到答案 3. 快速幂计算 计算a^b时：

通过分解b的二进制表示 将问题转化为多个a^(2^k)的乘积

#include<bits/stdc++.h>
using namespace std;
int st[100005][23],lg[100005];
int ask(int l,int r){
    int k = lg[r-l+1];
    return max(st[l][k],st[r-(1<<k)+1][k]);
}
signed main(){
    int n,m;cin>>n>>m;
    lg[0] = -1;
    for(int i =1;i<=n;i++){
        lg[i] = lg[i>>1]+1;
        cin>>st[i][0];
    }
    for(int j=1;(1<<j)<=n;j++){
        for(int i =1;i+(1<<j)-1<=n;i++){
            st[i][j] = max(st[i][j-1],st[i+(1<<j-1)][j-1]);
        }
    }
    while(m--){
        int l,r;cin>>l>>r;
        cout<<ask(l,r)<<"\n";
    }
}

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。 使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。

#include<bits/stdc++.h>
using namespace std;
struct node{
	int data;
	node * next;
};
node * p, *head=NULL,*q;
void print(){
	p=head;
	while(p!=NULL){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<"\n";

}
int k,x,y;
void del(){
	cin>>y;
	if(y==1){
		p=head;
		head=p->next;
		delete p;
	}
	else{
		q=head;
		for(int i =1;i<y-1;i++){
		 	q=q->next;
		}
		p=q->next;
		q->next=p->next;
		delete p;
	}
	print();
}
void insert(){
	cin>>k>>x;
	q=head;
	p=new node;
	p->data=x;
	if(k==1){
		p->next=head;
		head=p;
	}
	else{
		for(int i =1;i<k-1;i++){
			q=q->next;
		}
		
		p->next=q->next;
		q->next=p;
	}
	print();
}
int main(){
	int n;cin>>n;
	for(int i =1;i<=n;i++){
		int w;cin>>w;
		p=new node;
		p->data=w;
		p->next=head;
		head=p;
	}
	insert();
	del();
}

对于区间[a，b]上连续不断且f（a）·f（b）<0的函数y=f（x），通过不断地把函数f（x）的零点所在的区间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫二分法。

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],x,q;
int main(){
    cin>>n;
    for(int i =1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    cin>>q;
    while(q--){
        cin>>x;
        int l = 1,r = n;
        while(l<=r){
            int mid = (l+r)>>1;
            if(a[mid]>=x) r = mid-1;
            else l = mid+1;
        }
        if(a[r+1]==x) cout<<r+1<<"\n";
        else cout<<"-1\n";
   	}
}

迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。 [1]一篇发表于2024年的论文证明了迪克斯特拉算法具有普遍最优性。

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
vector<pii>g[10005];
int dis[10005];
void dijkstra(){
	memset(dis,127,sizeof(dis));
	priority_queue<pii,vector<pii>,greater<pii>> p;
	dis[1] = 0;
	p.push({1,0});
	while(p.size()){
		int u = p.top().first,disn = p.top().second;
		p.pop();
		if(disn>dis[u]) continue;
		for(auto i:g[u]){
			int v = i.first,w = i.second;
			if(dis[v]>dis[u]+w){
				dis[v] = dis[u]+w;
				p.push({v,dis[v]});
			}
		}
	}
     cout<<dis[n];
} 
signed main(){
	int n,m;cin>>n>>m;
	for(int i =1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		g[u].push_back({v,w}); 
	}
	dijkstra();
	
}

SPFA 算法是 Bellman-Ford算法 的队列优化算法的别称，通常用于求含负权边的单源最短路径，以及判负权环。SPFA 最坏情况下时间复杂度和朴素 Bellman-Ford 相同，为 O(VE)。

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#define pii pair<int,int>
using namespace std;
int dis[100005],inq[100005];
vector<pii>g[100005];
int n,m;
void spfa(){
	memset(dis,127,sizeof(dis));
	queue<int>q;
	q.push(1);
	dis[1] = 0;
	inq[1] = 1;
	while(q.size()){
		int u = q.front();
		q.pop();
		inq[u] = 0;
		for(auto i:g[u]){
			int v = i.first,w = i.second;
			if(dis[v]>dis[u]+w){
				dis[v] = dis[u]+w;
				if(!inq[v]){
					q.push(v);
					inq[v] = 1;
				}
			}
		} 
	} 
	cout<<dis[n];
}
signed main(){
	cin>>n>>m;
	for(int i =1;i<=m;i++){
		int u,v,w;
		g[u].push_back({v,w});
	}
	spfa(); 
}