算法模板

数论

//最大公约数
int gcd(int a, int b) {
  if (a < b) return gcd(b, a);
  if (a % b == 0) return b;
  return gcd(b, a%b);
}

统计

并查集

struct UF{
    int n;
    int cnt;
    vector fa;
    vector sz;
    UF(int _n) : n(_n), cnt(_n), fa(_n), sz(_n, 1) {
        iota(fa.begin(), fa.end(), 0);
    }
    int find(int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    bool merge(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx == fy) return false;
        if (sz[fx] < sz[fy]) swap(fx, fy);
        fa[fy] = fx;
        sz[fx] += sz[fy];
        cnt--;
        return true;
    }
    bool connected(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        return (fx == fy);
    }
};

树状数组

struct BIT {
    vector tree;
    BIT(int n): tree(n+1){}
    static constexpr int lowbit(int x) {
        return x & (-x);
    }
    void update(int index, int delta) {
        // x是从1开始的下标
        for (int i = index; i < tree.size(); i += lowbit(i)) {
            tree[i] += delta;
        }
    }
    //查询区间（0,x)的和
    long long query(int x) {
        long long res = 0;
        // 从右到左查询,最小到1，不能等于0
        for (int i = x; i > 0; i -= lowbit(i)) {
            res += tree[i];
        }
        return res;
    }
    // 查询区间[l, r]的和
    long long query(int l, int r) {
        return query(r+1) - query(l);
    }
};