高级算法数据结构模版
2026-08-24 15:29:46
发布于：广东
50阅读
0回复
0点赞
离散化
实现步骤：
- 输入原数组，将离散化数组赋上原数组的值
- 对离散化数组排序，记录去重后数组长度为m，初始化为1
- 从离散化数组第2位开始遍历
- 如果当前这一位与第m位不同，则m+=1，意味着向离散化数组中多添加一个新的值（原地去重）
- 遍历原数组并在离散化数组中用二分查找原数组的值，可以求相对大小位置
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=a[i];
}
int m=1;
sort(b+1,b+n+1);
for(int i=2;i<=n;i++) if(b[i]!=b[m]) b[++m]=b[i];
//原地去重
//遍历原数组,在离散化数组中用二分输出排名
哈希随机函数
ull seed =chrono::steady_clock::now().time_since_epoch().count();
ull splitmix64(ull x){
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
int Hash(ull x){
return splitmix64(x + seed) % M;
}
int get(ull x){
int h = Hash(x);
while(vis[h] && a[h] != x){
h++;
if(h == M) h = 0;
}
return h;
}
归并排序
void merge_sort(int l,int r){
if(l>=r) return;
int mid=(l+r)>>1;
merge_sort(l,mid);
merge_sort(mid+1,r);
//递归左右边界,将数组拆分成长度为1的小数组后结束
int i=l,j=mid+1,cnt=0;
//合并区间,i和j实际上是在不同区间内遍历
while(i<=mid&&j<=r){
//小于等于的放前面
if(a[i]<=a[j]) b[++cnt]=a[i++];
else b[++cnt]=a[j++];
}
//防止两个区间长度不一致,检查两个区间
while(i<=mid) b[++cnt]=a[i++];
while(j<=r) b[++cnt]=a[j++];
//将排完序的区间重新写入原本的数组,准备下一次合并排序
for(int i=1;i<=cnt;i++) a[l+i-1]=b[i];
}
拓扑排序
//使用广搜实现,记录每个点入度在d数组
void BFS(){
//queue<int> q; 放入节点进行遍历,度为0的节点放入队列,可以走
for(int i=1;i<=n;i++){
if(!d[i]) q.push(i);
}
//将队列中的节点取出,消除被它控制的点(度-1)
while(q.size()){
int f=q.front();
q.pop();
//ans[++cnt]=f; 记录拓扑序
for(int v:g[f]){
if(!--d[v]) q.push(v);
}
}
}
树状数组
int lowbit(int x){
return x&-x;
}
void update(int x,int y){
//向上找祖先,每一个包含更改过节点的祖先都需要添加
for(int i=x;i<N;i+=lowbit(i)) tr[i]+=y;
}
int query(int x){
int ans=0;
for(int i=x;i>0;i-=lowbit(i)) ans+=tr[i];
return ans;
}
线段树+懒标记
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+10;
int n,m,a[N];
struct node{
int mx;
int lz;
}tr[N*4];
void push_up(int u){
tr[u].mx = max(tr[u*2].mx,tr[u*2+1].mx);
}
void push_down(int u){
if(tr[u].lz){
tr[u*2].mx+=tr[u].lz;
tr[u*2+1].mx+=tr[u].lz;
tr[u*2].lz+=tr[u].lz;
tr[u*2+1].lz+=tr[u].lz;
tr[u].lz = 0;
}
}//将懒标记下放
void build(int u,int l,int r){
if(l==r){
tr[u].mx=a[l];
return;
}
int mid =l+r>>1;
build(u*2,l,mid);
build(u*2+1,mid+1,r);
push_up(u);
}
void update(int u,int l,int r,int lc,int rc,int x){
if(l>=lc && r<=rc){
tr[u].mx+=x;
tr[u].lz+=x;//懒标记
return;
}
int mid = l+r>>1;
push_down(u);//在递归前，把没有干完的活干完
if(lc<=mid)update(u*2,l,mid,lc,rc,x);
if(rc>=mid+1)update(u*2+1,mid+1,r,lc,rc,x);
push_up(u);
}
int query(int u,int l,int r,int lc,int rc){
//区间覆盖
if(l>=lc && r<=rc){
return tr[u].mx;
}
int mid = l+r>>1;
int mx = -1e18;
push_down(u);//在递归前，把没有干完的活干完
if(lc<=mid)mx = query(u*2,l,mid,lc,rc);
if(rc>=mid+1)mx = max(query(u*2+1,mid+1,r,lc,rc),mx);
return mx;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);//建树
while(m--){
int op,l,r,x;
cin>>op;
if(op==1){
cin>>l>>r>>x;
update(1,1,n,l,r,x);
}else{
cin>>l>>r;
cout<<query(1,1,n,l,r)<<"\n";
}
}
return 0;
}
ST表
void build(){
//相当于二分,st[i][j]表示从i开始向后2^j区间内的最值
for(int j=1;(1<<j)<=m;j++){
for(int i=1;i+(1<<j)-1<=m;i++){
//将区间拆分成两个长度为2的幂的区间,分别求最值
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
}
int find(int l,int r){
//对原区间长度进行log2,以便后续拆解
int k=log2(r-l+1);
//拆解出长度为2的幂的两个区间
int ans=min(st[l][k],st[r-(1<<k)+1][k]);
return ans;
}
全部评论 8
sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());3天前 来自 上海
0
有帮助，赞一个