字典树

前缀查询和模糊查询

struct Node{
    Node* son[26];
    int end;
    Node(){
        end = 0;
        for(int i = 0; i < 26; i++) son[i] = nullptr; 
    }
};
Node* root = new Node();
void insert(string word){
    auto p = root;
    for(auto w: word){
        int u = w - 'a';
        if(!p->son[u]) p->son[u] = new Node();
        p = p->son[u];
    }
    p->end++;
}
int query(string word){
    auto p = root;
    for(auto w: word){
        int u = w - 'a';
        if(!p->son[u]) return 0;
        p = p->son[u];
    }
    return p->end;
}

并查集

求连通分量和连通分量中的最大集合

int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

if(find(a) != find(b)) p[find(a)] = find(b);

KMP字符串匹配

$O(m+n)$

单调栈

左边(右边)第一个比它小的数

线段树

线段树是一种非常灵活的数据结构，它可以用于解决多种范围查询问题，比如在对数时间内从数组中找到最小值，最大值，总和，最大公约数，最小公倍数等。
注意：
下标从1开始
三个步骤:
1. 建立线段树
2. 修改元素时更新线段树
3. 使用线段树进行区域和检索

class NumArray {
public:
    vector<int> tree;
    int n;
    NumArray(vector<int>& nums) {
        n = nums.size();
        tree.resize(n<<2);
        for(int i = n, j = 0; i < 2*n; i++, j++) tree[i] = nums[j];
        for(int i = n-1; i > 0; i--) tree[i] = tree[i<<1] + tree[i<<1|1];
    }

    void update(int pos, int val) {
        pos += n;
        val -= tree[pos];
        while(pos){
            tree[pos] += val;
            pos >>= 1;
        }  
    }

    int sumRange(int left, int right) {
        int res = 0;
        for(left += n, right += n; left <= right; left >>=1, right >>= 1){
            if(left&1) res += tree[left++];
            if(right&1^1) res += tree[right--];
        }
        return res;
    }
};

树状数组

下标必须从1开始

class NumArray {
public:
    int n;
    vector<int> num, C;

    NumArray(vector<int>& nums) {
        n = nums.size();
        num.resize(n+1);
        C.resize(n + 1);

        for(int i = 0; i < n; i++){ 
            update(i, nums[i]);
        }
    }
    //这一步比较关键 这里的插入点和查询点都是从0开始，所以需要手动增加一位
    void update(int i, int val) {
       for(int x = i+1; x <= n; x += lowbit(x)) C[x] += (val - num[i+1]); //更新
       num[i+1] = val;
    }

    int sumRange(int i, int j) {
        return query(j+1) - query(i);
    }
    inline int lowbit(int x){
        return x&(-x);
    }

    //查询
    int query(int pos){
        int sum = 0;
        while(pos){
            sum += C[pos];
            pos -=lowbit(pos);
        }
        return sum;
    }
};