基础数据结构模板（持续更新）

• • • 算法
    • • 数据结构
      • • 并查集
        • 树状数组
      • 基础算法模板
      • • 快排
        • 二分
        • 高精度加法
        • 差分
        • 位运算
        • 双指针
      • 动态规划
      • • LIS
      • 数论
      • • 质数
      • 图论
      • • 树与图的储存
        • 树的遍历
        • 拓扑排序
      • Leetcode
      • • 反转链表
        • 环形链表

//朴素并查集
//存储每个点的祖宗节点
int p[N];
//返回x的祖宗节点
int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
//初试化
for(int i=1;i<=n;i++) p[i]=i;
//合并两个集合
p[find(a)]=find(b);



//维护size的并查集
//p[]存储每个点的祖宗节点,size[]存储集合大小只有祖宗节点有意义
int p[N],size[N];

int find(int x){
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}
//初始化
for(int i=1;i<=n;i++){
    p[i]=i;
    size[i]=1;
}
//合并两个集合
size[find(b)]+=size[find(a)];
p[find(a)]=find(b);
	


//维护到祖宗节点的并查集

int tr[N];

void lowbit(int x){
    return x&-x;
}
void add(int x,int c){
    for(int i=x;i<=n;i+=lowbit(i)){
        tr[i]+=c;
    }	
}
int sum(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(x)){
        res+=tr[i];
    }
    return res;
}
//初始化
memset(tr,0,sizeof(tr));
for(int i=1;i<=n;i++){
    add(i,num[i]);
}

void quick_sort(int q[],int l,int r){
    if(l>=r) return;
    int i=l-1,j=r+1,x=q[l+r>>1];
    while(ix);
        if(i 
二分 
bool check(int x) {} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
//上升序列 返回第一个>=x的迭代器
lower_bound(nums.begin(),nums.end(),x);
//上升序列 返回第一个>x的迭代器
upper_bound(nums.begin(),nums.end(),x);

//下降序列 返回第一个<=x的迭代器
lower_bound(nums.begin(),nums.end(),x,greater());
//下降序列 返回第一个());
 
高精度加法 
差分 
位运算 
int lowbit(int x) return x&-x;
//n的第k位数字
n >> k & 1
 
双指针 
动态规划 
LIS 
朴素
 
f[i]：所有以a[i]结尾的上升子序列
 
属性：最长
 
状态计算: f[i]=max(f[i-1]+1,…f[1]+1,1)
 
#include
#include

using namespace std;

const int N=1010;
int a[N],f[N];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;ja[j]){
                f[i]=max(f[i],f[j]+1);
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++){
        res=max(res,f[i]);
    }
    cout< 
数论 
质数 
试除法
 
bool is_prime(int x){
    if(x<2) return false;
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            return false;
        }
    }
    return true;
}
 
试除法分解质因数
 
void divide(int x){
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            int s=0;
            while(x%i==0){
                x=x/i;
                s++;
            }
            cout<1){
        cout< 
图论 
树与图的储存 
(1)邻接矩阵 g[a][b]=1  a->b
(2)邻接表
//h[k] 存储每个节点的头节点指针
int h[N],e[N],ne[N],idx;
//添加a->b
void add(int a,int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    idx++;
}
idx=0;
memset(h,-1,sizeof(h));
 
树的遍历 
//深度优先遍历
int dfs(int u){
    st[u]=true;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]) dfs(j);
    }
}
queue q;
void bfs(int u){
    q.push(u);
    st[u]=true;
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=h[x];i!=-1;i=me[i]){
            int j=e[i];
            if(!st[j]) q.push(j);
        }
    }
}
 
拓扑排序 
//拓扑排序
int d[N];
bool topsort(){
    int q[N];
    int hh=,tt-1;
    for(int i=0;i 
Leetcode 
反转链表 
ListNode* reverseList(ListNode* head){
    ListNode* pre;
    ListNode* curr=head;
    while(curr){
        ListNode* ne=curr->next;
        curr->next=pre;
        pre=curr;
        curr=ne;
    }
    return pre;
}
 
环形链表 
bool hasCycle(ListNode* head) {
        if(head==NULL||head->next==NULL){
            return false;
        }
        ListNode* slow=head;
        ListNode* fast=head->next;
        while(slow!=fast){
            if(fast==NULL||fast->next==NULL){
                return false;
            }
            slow=slow->next;
            fast=fast->next->next;
        }
        return true;
    }