数据结构

本文内容参考 OI Wiki。

并查集

例题

• P3367 【模板】并查集。

实现

class UnionFind {
    private final int[] f, s;
    private int c;

    public UnionFind(int n) {
        c = n;
        f = new int[n];
        s = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = i;
            s[i] = 1;
        }
    }

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

    public void union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return;
        f[ry] = rx;
        s[rx] += s[ry];
        c--;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public int size(int x) {
        return s[find(x)];
    }

    public int count() {
        return c;
    }
}

树状数组

例题

• #130. 树状数组 1 ：单点修改，区间查询。
• #131. 树状数组 2 ：区间修改，单点查询。
• #132. 树状数组 3 ：区间修改，区间查询。

实现

单点修改，区间查询

class BIT {
    private final int n;
    private final long[] t;

    public BIT(int n) {
        this.n = n;
        t = new long[n + 1];
    }

    public void add(int i, int k) {
        for (; i <= n; i += i & -i) {
            t[i] += k;
        }
    }

    public long sum(int x) {
        long res = 0;
        for (; x > 0; x &= x - 1) {
            res += t[x];
        }
        return res;
    }

    public long get(int l, int r) {
        return sum(r) - sum(l - 1);
    }
}

区间修改，单点查询

class BIT {
    private final int n;
    private final long[] t;

    public BIT(int n) {
        this.n = n;
        t = new long[n + 1];
    }

    private void add(int i, int k) {
        for (; i <= n; i += i & -i) {
            t[i] += k;
        }
    }

    public void add(int l, int r, int k) {
        add(l, k);
        add(r + 1, -k);
    }

    public long sum(int x) {
        long res = 0L;
        for (int i = x; i > 0; i &= i - 1) {
            res += t[i];
        }
        return res;
    }

    public long get(int x) {
        return sum(x);
    }
}

区间修改，区间查询

class BIT {
    private final int n;
    private final long[] t1, t2;

    public BIT(int n) {
        this.n = n;
        t1 = new long[n + 1];
        t2 = new long[n + 1];
    }

    private void add(int i, int k) {
        long p = (long) k * i;
        for (; i <= n; i += i & -i) {
            t1[i] += k;
            t2[i] += p;
        }
    }

    public void add(int l, int r, int k) {
        add(l, k);
        add(r + 1, -k);
    }

    public long sum(int x) {
        long s1 = 0, s2 = 0;
        for (int i = x; i > 0; i &= i - 1) {
            s1 += t1[i];
            s2 += t2[i];
        }
        return s1 * (x + 1) - s2;
    }

    public long get(int l, int r) {
        return sum(r) - sum(l - 1);
    }
}

线段树

例题

• P3372 【模板】线段树 1。
• P3373 【模板】线段树 2。

实现

class SegmentTree {
    private final int n;
    private final long[] t, z;

    public SegmentTree(int[] a) {
        n = a.length;
        t = new long[4 * n];
        z = new long[4 * n];
        build(a, 1, 1, n);
    }

    private void build(int[] a, int i, int l, int r) {
        if (l == r) {
            t[i] = a[l - 1];
            return;
        }
        int mid = l + (r - l) / 2;
        build(a, 2 * i, l, mid);
        build(a, 2 * i + 1, mid + 1, r);
        t[i] = t[2 * i] + t[2 * i + 1];
    }

    private void lazy(int i, int lo, int hi, long k) {
        t[i] += k * (hi - lo + 1);
        z[i] += k;
    }

    private void down(int i, int lo, int hi) {
        if (z[i] == 0) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        lazy(2 * i, lo, mid, z[i]);
        lazy(2 * i + 1, mid + 1, hi, z[i]);
        z[i] = 0;
    }

    public void add(int l, int r, int k) {
        if (l > r) return;
        add(1, 1, n, l, r, k);
    }

    private void add(int i, int lo, int hi, int l, int r, int k) {
        if (lo >= l && hi <= r) {
            lazy(i, lo, hi, k);
            return;
        }
        down(i, lo, hi);
        int mid = lo + (hi - lo) / 2;
        if (l <= mid) add(2 * i, lo, mid, l, r, k);
        if (r > mid) add(2 * i + 1, mid + 1, hi, l, r, k);
        t[i] = t[2 * i] + t[2 * i + 1];
    }

    public long get(int l, int r) {
        if (l > r) return 0L;
        return get(1, 1, n, l, r);
    }

    private long get(int i, int lo, int hi, int l, int r) {
        if (lo >= l && hi <= r) {
            return t[i];
        }
        down(i, lo, hi);
        long res = 0L;
        int mid = lo + (hi - lo) / 2;
        if (l <= mid) res += get(2 * i, lo, mid, l, r);
        if (r > mid) res += get(2 * i + 1, mid + 1, hi, l, r);
        return res;
    }
}

稀疏表（Sparse Table）

例题

• P3865 【模板】ST 表。

实现

System.out.println("TODO");