堆

struct Heap{
    priority_queue<ll>q1,q2;
    inline void push(ll x){q1.push(x);}
    inline void erase(ll x){q2.push(x);}
    inline void updata(){while(!q1.empty()&&!q2.empty()&&q1.top()==q2.top())q1.pop(),q2.pop();}
    inline ll top(){updata();return q1.top();}
}Q;

ST表

静态求区间最大值，基于倍增的思想

int N,M;
int arr[maxn],Log2[maxn];//原始数组，log2(x)数组
int f[maxn][20];//F[i][j]: arr[i~i+2^j-1]的最大值

void ST_init(){ //初始化所有长度为2^x的区间最大值
    for(int i = 1;i<=N;i++) Log2[i] = log(i)/log(2); //初始化log求值，之后O(1)取值
    for(int i = 1;i<=N;i++) f[i][0] = arr[i];
    int len = log(N)/log(2) +1;
    for(int j = 1;j<len;j++){
        for(int i = 1;i<=N-(1<<j)+1;i++){
            f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}
int query(int l,int r){ //查询arr[l~r]区间的最值
    int k = Log2[r-l+1];
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

并查集

int find(int x){
    return fa[x] == x? x: fa[x] = find(fa[x]);
}
void join(int x,int y){
    int fx = find(x),fy = find(y);
    if(fx != fy) fa[fx] = fy;
}
for(int i = 1;i<=N;i++) fa[i] = i;//一定要初始化

分块

以求和为例

ll arr[maxn],base[maxn],res[maxn],B;//B:块的大小
void init(){ //分块初始化：每一个块维护[id*B,(id+1)*B],id是块的编号
    for(int i = 1;i<=N;i++) res[i/B] += arr[i];
}
void modify(int l,int r,int v){ //sqrt(N)修改复杂度
    int bl = l/B,br = r/B;
    ll ans = 0;
    if(bl == br){
        for(int i = l;i<=r;i++) arr[i] += v,res[bl] += v;
    }else{
        for(int i = l;i<(bl+1)*B;i++) arr[i]+=v,res[bl] += v;//小块
        for(int i = bl+1;i<=br-1;i++) base[i]+=v,res[i] += (ll)v*B;//大块
        for(int i = br*B;i<=r;i++) arr[i] +=v,res[br] += v;//小块
    }
}
ll query(int l,int r){//sqrt(N)查询复杂度
    int bl = l/B, br = r/B;
    ll ans = 0;
    if(bl == br){
        for(int i = l;i<=r;i++) ans += arr[i] + base[bl];
    }else{
        for(int i = l;i<(bl+1)*B;i++) ans += arr[i] + base[bl];
        for(int i = bl+1;i<=br-1;i++) ans += res[i];
        for(int i = br*B;i<=r;i++) ans += arr[i] + base[br];
    }
    return ans;
}

奇奇怪挂的数据结构

马拉车算法

string s;
int ans[maxn],str[maxn],lef[maxn]; 
//ans：每一点的回文半径，str：插#字符后的字符串 lef：以某个为左边界的最长回文子串长度
int build(const string &s){
    int n = s.length(), m = (n + 1)*2, ret = 0;
    str[0] = '$'; str[m] = '@'; str[1] = '#'; ans[1] = 1;
    for (int i = 1; i <= n; i++) 
        str[i*2] = s[i - 1], str[i*2+1] = '#';
    ans[1] = 1;
    for (int r = 0, p = 0, i = 2; i < m; ++i){
        if (r > i) ans[i] = min(r - i, ans[p * 2 - i]); 
        else ans[i] = 1; 
        while(str[i - ans[i]] == str[i + ans[i]]) ++ans[i];
        if (i + ans[i] > r) r = i + ans[i], p = i;
        ret = max(ret, ans[i] - 1);
    }
        // 计算维护以每个位置为起点的最长回文串
        for (int i = 0; i <= m; i++) lef[i] = 0;
        for (int i = 2; i < m; i++) if (lef[i - ans[i] + 1] < i + 1) lef[i - ans[i] + 1] = i + 1;
        for (int i = 1; i <= m; i++) if (lef[i] < lef[i - 1]) lef[i] = lef[i - 1];
    return ret;//最长回文串的长度
}
 int mid(int x, bool odd){ 
     //求以x为中心的最长回文子串长度，若是求偶回文串，这里中心认为是中间靠左
        if (odd) return ans[(x + 1) << 1] - 1;
        return ans[(x + 1) << 1 | 1] - 1;
    }
int left(int x){ 
    //求以x为左端点的最长回文串的长度
    return lef[(x + 1) << 1] - ((x+1) << 1); 
}

树状数组

二维树状数组 [单点修改、区间查询]

int N,M;//N*M的矩阵
int tr[1111][1111];
int lowbit(int x){
    return x&-x;
}
void add(int x,int y,int v){
    for(int i = x;i<=N;i += lowbit(i)){
        for(int j = y;j<=M;j += lowbit(j)){
            tr[i][j] += v;
        }
    }
}
ll pre_sum(int x,int y){ //查询(1,1)到(x,y)矩阵和
    ll sum = 0;
    for(int i = x;i>=1;i -= lowbit(i)){
        for(int j = y;j>=1;j -= lowbit(j)){
            sum += tr[i][j];
        }
    }
    return sum;
}
ll query(int x1,int y1,int x2,int y2){ //查询(x1,y2)到(x2,y2)的矩阵和
    return pre_sum(x2,y2) - pre_sum(x1-1,y2) - pre_sum(x2,y1-1) + pre_sum(x1-1,y1-1);
}

二维树状数组 [区间修改，单点查询]

int tr[1010][1010];//NxN的矩阵

int lowbit(int x){
    return x&-x;
}
void add(int x,int y,int v){
    for(int i = x;i<=N;i += lowbit(i))
        for(int j = y;j<=N;j += lowbit(j))
            tr[i][j] += v;
}
int query(int x,int y){
    int sum = 0;
    for(int i = x;i>=1;i -= lowbit(i))
        for(int j = y;j>=1;j -= lowbit(j))
            sum += tr[i][j];
    return sum;
}
//给左上角(x1,y1) ，右下角(x2,y2)的矩阵+v
add(x1,y1,+v);
add(x1,y2+1,-v);
add(x2+1,y1,-v);
add(x2+1,y2+1,+v);