高级算法数据结构模版

Wanderer

2026-08-16 20:03:26

发布于：广东

22阅读

0回复

0点赞

离散化

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;
}

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;
}