数据结构

不同的数据结构各有优劣，能够处理的问题各不相同，而根据具体问题选取合适的数据结构，可以大大提升程序的效率。

珂朵莉树

珂朵莉树通过将序列划分为多个值相同（或性质相同）的连续区间来高效处理区间赋值和查询操作，是一种基于区间合并的暴力数据结构。

在 perform 以后立即对同一区间调用 assign 的情况下，珂朵莉树的时间复杂度为均摊 O(log n) ，而在操作随机的情况可以达到更优的期望时间复杂度 O(log log n) 。

若以上要求均不满足，则最坏情况下操作的复杂度退化为 O(n) ，其中 m 为操作次数，n 为珂朵莉树中最大区间个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
map<int, int> odt;  
odt[1] = 1;  
  
auto split = [&](int x) {  
    auto it = odt.upper_bound(x);  
    return odt.emplace_hint(it, x, prev(it)->second);  
};  
  
auto assign = [&](int l, int r, int c) {  
    auto itr = split(r), itl = split(l);  
    odt.erase(itl, itr);  
    odt[l] = c;  
};  
  
auto perform = [&](int l, int r) {  
    auto itr = split(r), itl = split(l);  
    for (auto it1 = itl, it2 = next(itl); it1 != itr; ++it1, ++it2) {
        // TODO
    } 
};

ST 表

ST 表是基于倍增思想，用于解决可重复贡献问题的数据结构，可以做到 Θ(nlog n) 预处理，Θ(1) 回答每个询问。

本实现为左开右闭实现，在构造函数中预处理，也提供了向 ST 表末尾新增元素的方法，复杂度 Θ(log n) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
template<typename T>  
struct SparseTable {  
    vector<vector<T> > st = {{}};  
  
    explicit SparseTable() : st(1) {  
    }  
  
    explicit SparseTable(const vector<T> &val) : st(1, val) {  
        int p = val.size(), d = __lg(p);  
        st.resize(d + 1, vector<T>(p));  
        for (int i = 0; i < d; i++) {  
            for (int j = 1 << i; j < p; j++) {  
                st[i + 1][j] = min(st[i][j], st[i][j - (1 << i)]);  
            }  
        }  
    }  
  
    void append(T t) {  
        int p = st[0].size(), d = __lg(p + 1);  
        if (d >= st.size()) st.emplace_back(p);  
        st[0].emplace_back(t);  
        for (int i = 0; i < d; i++) {  
            st[i + 1].emplace_back(min(st[i][p], st[i][p - (1 << i)]));  
        }  
    }  
  
    T query(int l, int r) {  
        int d = __lg(r - l);  
        return min(st[d][r], st[d][l + (1 << d)]);  
    }  
};

并查集

以下代码实现了包含路径压缩和启发式合并的并查集，将 fa 数组和 sz 数组合并为 p 数组以优化空间，其中负数代表集合大小的相反数，正数代表父节点编号，每个操作的均摊复杂度为 O(α(n)) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct DSU {  
    vector<int> p;  
  
    explicit DSU(int n) : p(n, -1) {  
    }  
  
    int find(int x) {  
        return p[x] < 0 ? x : p[x] = find(p[x]);  
    }  
  
    bool same(int x, int y) {  
        return find(x) == find(y);  
    }  
  
    int merge(int x, int y) {  
        x = find(x), y = find(y);  
        if (x == y) return -1;  
        if (p[x] > p[y]) swap(x, y);  
        p[x] += p[y], p[y] = x;  
        return x;  
    }  
};

带权并查集

带权并查集在并查集的基础上额外维护每个节点到根节点的一个权值，并在路径压缩与合并时维护权值和判定矛盾，提供了一种节点之间的关系维护方法。

以下代码实现了带路径压缩和启发式合并的带权并查集，维护节点之间距离，每个操作的均摊复杂度为 O(α(n)) 。

dist(x, y) 代表查询节点 x 到节点 y 的距离，若两者不在同一集合中，则返回 inf 。

try_merge(x, y, d) 代表添加一维距离约束 y = x + d ，若冲突则返回 −1，否则合并 x 和 y 并返回新的根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct DSU {  
    vector<int> p, dt;  
  
    explicit DSU(int n) : p(n, -1), dt(n) {  
    }  
  
    int find(int x) {  
        if (p[x] < 0) return x;  
        int rt = find(p[x]);  
        dt[x] = dt[x] + dt[p[x]];  
        return p[x] = rt;  
    }  
  
    int dist(int x, int y) {  
        int rx = find(x), ry = find(y);  
        if (rx != ry) return inf;  
        return dt[y] - dt[x];  
    }  
  
    int try_merge(int x, int y, int d) {  
        int rx = find(x), ry = find(y);  
        if (rx == ry) return dt[y] - dt[x] == d ? rx : -1;  
        d -= dt[y] - dt[x];  
        if (p[rx] > p[ry]) swap(rx, ry), d = -d;  
        p[rx] += p[ry], p[ry] = rx, dt[ry] = d;  
        return rx;  
    }  
};

分块

分块是一种思想，而不是一种数据结构。

使用分块可以以简单的代码实现复杂的数据结构才能实现的功能，下面给出常见分块实现。

普通分块

实现了单点修改前缀和查询的普通分块，用法几乎同树状数组，维护前缀和可以实现区间修改单点查询，也可维护权值（称为值域分块），$O(\sqrt{n})$ 修改，O(1) 查询。

如果分块直接维护值而不是前缀和（即交换 add 与 sum 的实现逻辑）可以做到 O(1) 修改，$O(\sqrt{n})$ 查询。

视具体境况选用不同的维护方式，可以平衡算法各部分复杂度，从而使总复杂度最优。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template<typename T>
struct Block {
    int n, len;
    vector<T> prea, preb;

    explicit Block(int n) : prea(n), preb(n) {
        this->n = n;
        len = (int) sqrt(n);
    }

    void add(int x, T v) {
        int id = x / len;
        for (int i = x; i < min((id + 1) * len, n); i++) prea[i] += v;
        for (int i = id + 1; i < min(n / len + 1, n); i++) preb[i] += v;
    }

    T sum(int x) {
        return prea[x] + preb[x / len];
    }
};

分块 RMQ

基于分块的 RMQ 实现，原理是将数组分成固定大小的块，预处理每块的前缀/后缀最大值和块间稀疏表，查询时结合块内和块间结果得出答案。

预处理时间复杂度为 O(n) ，查询时间复杂度为期望 O(1) 。

在最坏情况下查询需要遍历块内元素，单次查询 $O(\sqrt{n})$ ，但通过微调块长可以规避，无法卡掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
template<typename T, typename Cmp = less<T> >  
struct BlockRMQ {  
    int n, len;  
    const vector<T> &arr;  
    vector<T> pre, suf;  
    vector<vector<T> > bmin;  
    T neu;  
    Cmp cmp;  
  
    explicit BlockRMQ()  
        : n(), len(), arr(), pre(), suf(), bmin(), neu(), cmp() {  
    }  
  
    explicit BlockRMQ(const vector<T> &val, T neu = T(), Cmp cmp = Cmp())  
        : n(val.size()), arr(val), pre(val.size()), suf(val.size()), bmin(), neu(neu), cmp(cmp) {  
        len = max(1, (int) sqrt(n) + (rand() % 5 - 2));  
        int N = (n + len - 1) / len;  
        bmin.assign(N, vector<T>(N, neu));  
        for (int b = 0; b < N; b++) {  
            int L = b * len, R = min(L + len, n);  
            pre[L] = arr[L], suf[R - 1] = arr[R - 1];  
            for (int i = L + 1; i < R; i++) pre[i] = min(pre[i - 1], arr[i], cmp);  
            for (int i = R - 2; i >= L; i--) suf[i] = min(suf[i + 1], arr[i], cmp);  
            bmin[b][b] = suf[L];  
        }  
        for (int i = 0; i < N; i++) {  
            for (int j = i + 1; j < N; j++) {  
                bmin[i][j] = min(bmin[i][j - 1], bmin[j][j], cmp);  
            }  
        }  
    }  
  
    T query(int l, int r) {  
        int L = l / len, R = (r - 1) / len;  
        T res = neu;  
        if (L == R) {  
            for (int i = l; i < r; i++) res = min(res, arr[i], cmp);  
        } else {  
            res = min(suf[l], pre[r - 1], cmp);  
            if (L + 1 <= R - 1) res = min(res, bmin[L + 1][R - 1], cmp);  
        }  
        return res;  
    }  
};

块状数组

以简单通用的方式实现的块状数组，可以方便地修改分块逻辑，本实现中原数组和块状数组均为 1-base 。

1
2
3
4
5
6
7
8
int len = (int) sqrt(n), N = 0;  
vector<int> bk(n + 1), bs, be;  
for (int i = 1; i <= n; i++) {  
    bk[i] = (i - 1) / len + 1; // 下标到块编号的映射关系计算
    while (N <= bk[i]) bs.push_back(inf), be.push_back(0), N++;  
    bs[bk[i]] = min(bs[bk[i]], i);  
    be[bk[i]] = max(be[bk[i]], i + 1);  
}

前后缀分块/区间众数

通过预处理块内前后缀和块间答案的思路可以广泛运用于各种序列问题，在线查询区间众数就是其中一个经典问题。

前缀计数数组 pre ：记录每个块的前缀和，用于快速统计任意块区间内元素的出现次数。

块间众数数组 ma ：对每个块区间 [i, j]，预计算其众数。

查询时只有整块的众数和零散块中的数可能成为答案，复杂度 $O(\sqrt{n})$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
vector pre(N, vector<int>(b.size() + 1));  
for (int i = 1; i < N; i++) {  
    pre[i] = pre[i - 1];  
    for (int j = bs[i]; j < be[i]; j++) pre[i][a[j]]++;  
}
  
vector<int> cnt(b.size() + 1);  
vector ma(N, vector<int>(N));  
for (int i = 1; i < N; i++) {  
    cnt.assign(b.size() + 1, 0);  
    int maxa = 0;  
    for (int j = i; j < N; j++) {  
        ma[i][j] = ma[i][j - 1];  
        for (int k = bs[j]; k < be[j]; k++) {  
            cnt[a[k]]++;  
            if (cnt[a[k]] == maxa) ma[i][j] = min(ma[i][j], a[k]);  
            if (cnt[a[k]] > maxa) maxa = cnt[a[k]], ma[i][j] = a[k];  
        }  
    }  
}

auto query = [&](int l, int r) {  
    int res = 0;  
    if (bk[l] == bk[r - 1]) {  
        for (int i = l; i < r; i++) cnt[a[i]] = 0;  
        int maxa = 0;  
        for (int i = l; i < r; i++) {  
            cnt[a[i]]++;  
            if (maxa == cnt[a[i]]) res = min(res, a[i]);  
            if (maxa < cnt[a[i]]) maxa = cnt[a[i]], res = a[i];  
        }  
    } else {  
        int L = bk[l], R = bk[r - 1];  
        res = ma[L + 1][R - 1];  
        for (int i = l; i < be[L]; i++) cnt[a[i]] = pre[R - 1][a[i]] - pre[L][a[i]];  
        for (int i = bs[R]; i < r; i++) cnt[a[i]] = pre[R - 1][a[i]] - pre[L][a[i]];  
        int maxa = pre[R - 1][res] - pre[L][res];  
        for (int i = l; i < be[L]; i++) {  
            cnt[a[i]]++;  
            if (maxa == cnt[a[i]]) res = min(res, a[i]);  
            if (maxa < cnt[a[i]]) maxa = cnt[a[i]], res = a[i];  
        }  
        for (int i = bs[R]; i < r; i++) {  
            cnt[a[i]]++;  
            if (maxa == cnt[a[i]]) res = min(res, a[i]);  
            if (maxa < cnt[a[i]]) maxa = cnt[a[i]], res = a[i];  
        }  
    }  
    return res;  
};

树分块 / 王室联邦分块

王室联邦分块是最经典、最常用的一种树分块方法，其构建的分块具有如下性质：

  • 块大小有界：每个块的大小在 [B, 2B] 之间。保证了块的规模大致均匀。
  • 省会的性质：每个块均有一个块外的省会，省会节点比块中所有节点深度都小。
  • 块的连通性：每个块加上其省会是原树的一个连通块，但可能有多个块共享省会。

通过这种分块，可以利用省会建立虚树在线地解决问题，或利用树上莫队算法离线查询问题。

以下实现中，key 为每个块的省会，kid 为每个节点作为省会对应的任意块 id，非省会则为 0 ，bk 为每个节点所属块 id ，kfa 为省会间建立的虚树父亲关系。

特别地，空节点 0 也属于省会，对应遍历完整棵树后的剩余节点，其块大小严格小于 B 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
vector<int> stk, key(1), kid(n + 1), bk(n + 1);  
int N = 1, len = sqrt(__lg(30) * n);  
auto dfs = [&](auto &&self, int u) -> void {  
    int st = stk.size();  
    for (int v: adj[u]) {  
        if (fa[u] == v) continue;  
        self(self, v);  
        if (stk.size() >= st + len) {  
            key.push_back(u), kid[u] = N;  
            while (stk.size() != st) {  
                bk[stk.back()] = N, stk.pop_back();  
            }  
            N++;  
        }  
    }  
    stk.push_back(u);  
};  
dfs(dfs, 1);  
  
key.push_back(0), kid[0] = N;  
while (!stk.empty()) {  
    bk[stk.back()] = N;  
    stk.pop_back();  
}  
N++;  
  
vector<int> kfa(n + 1);  
vector<vector<int> > inkey(n + 1);  
for (int u = 1; u <= n; u++) {  
    if (!kid[u]) continue;  
    for (int x = u; x; x = fa[x]) {  
        inkey[x].push_back(u);  
        if (kid[fa[x]]) {  
            kfa[u] = fa[x];  
            break;  
        }  
    }  
}

树状数组

树状数组可以执行单点修改和前缀和查询，维护的信息运算要满足结合律，对于可差分信息可以方便地实现区间和。

普通树状数组

最基础的树状数组，可以进行单点修改和前缀和查询操作，复杂度均为 O(log n) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<typename T>
struct Fenwick {
    vector<T> a;

    explicit Fenwick(int n) : a(n) {}

    void add(int x, T v) {
        for (int i = x; i < a.size(); i += i & -i) a[i] += v;
    }

    T sum(int x) {
        auto ans = T();
        for (int i = x; i; i -= i & -i) ans += a[i];
        return ans;
    }
};

树状数组上二分

返回最后一个使前缀和小于指定值 k 的下标 x 的下一位，即权值树状数组第 k 小。

1
2
3
4
5
6
7
8
9
10
int kth(T k) {
    int x = 0;
    auto cur = T();
    for (int i = bit_floor(a.size()); i; i >>= 1) {
        if (x + i >= a.size()) continue;
        if (cur + a[x + i] >= k) continue;
        x += i, cur += a[x];
    }
    return x + 1;
}

树状数组 Θ(n) 建树

树状数组每一个节点的值是由所有与自己直接相连的儿子的值求和得到的，因此建树时可以每次确定完儿子的值后，用儿子的值更新其直接父亲。

树状数组的元素 a[i] 管辖的区间是 [i − lowbit(i) + 1, i] ，因此也可以预处理一个前缀和数组 sum 来建树。

1
2
3
4
5
6
7
8
9
10
11
12
13
explicit Fenwick(const vector<T> &v) : a(v.size()) {
    for (int i = 1; i < v.size(); ++i) {
        a[i] += v[i];
        int j = i + (i & -i);
        if (j < v.size()) a[j] += a[i];
    }
}

explicit Fenwick(const vector<T> &sum) : a(sum.size()) {
    for (int i = 1; i < sum.size(); ++i) {
        a[i] = sum[i] - sum[i - (i & -i)];
    }
}

区间加、区间和

使用两个树状数组维护差分信息，可实现区间加、区间和，左闭右闭实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Fenwick<int> d(n + 1), di(n + 1);

auto apply = [&](int l, int r, int v) {
    auto set = [&](int x, int v) {
        d.add(x, v);
        di.add(x, v * x);
    };
    set(l, v);
    set(r + 1, -v);
};

auto query = [&](int l, int r) {
    auto get = [&](int x) {
        return d.sum(x) * (x + 1) - di.sum(x);
    };
    return get(r) - get(l - 1);
};

线段树

线段树是一种维护区间信息的数据结构，只要求维护的信息可合并，因此具有极强的泛用性。

信息、标记的实现需要满足有效信息、标记与空信息、空标记合并后不改变（即空构造的信息和标记均为单位元），否则结果不可预估。

zkw 线段树

zkw 线段树是一种基于完全二叉树、采用自底向上非递归实现的高效线段树变种，以代码简洁、节省空间著称，特别适合单点修改和区间查询操作，时间复杂度均为 O(log n) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<typename Info>  
struct SegmentTree {  
    int n;  
    vector<Info> seg;  
  
    explicit SegmentTree(const vector<Info> &val) : seg(2 * val.size()) {  
        n = (int) val.size();  
        for (int i = 0; i < val.size(); ++i) seg[n + i] = val[i];  
        for (int i = n - 1; i; --i) seg[i] = Info::merge(seg[i << 1], seg[i << 1 | 1]);  
    }  
  
    void modify(int x, const Info &v) {  
        for (seg[x += n] = v; x >>= 1; ) seg[x] = Info::merge(seg[x << 1], seg[x << 1 | 1]);  
    }  
  
    Info query(int l, int r) {  
        Info resl{}, resr{};  
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {  
            if (l & 1) resl = Info::merge(resl, seg[l++]);  
            if (r & 1) resr = Info::merge(seg[--r], resr);  
        }  
        return Info::merge(resl, resr);  
    }  
};

懒标记线段树

模板类实现的懒标记线段树，实现了区间修改和区间查询功能，时间复杂度均为 O(log n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
template<typename Info, typename Tag>  
struct SegmentTree {  
    vector<Info> seg;  
    vector<Tag> tag;  
  
    explicit SegmentTree(const vector<Info> &val) : seg(val.size() * 4), tag(val.size() * 4) {  
        auto build = [&](auto &&self, int u, int l, int r) {  
            if (r - l == 1) {  
                seg[u] = val[l];  
                return;  
            }  
            int m = l + r >> 1;  
            self(self, u << 1, l, m);  
            self(self, u << 1 | 1, m, r);  
            seg[u] = Info::merge(seg[u << 1], seg[u << 1 | 1]);  
        };  
        build(build, 1, 0, val.size());  
    }  
  
    void push(int u, int l, int r) {  
        int m = l + r >> 1;  
        seg[u << 1].apply(tag[u], l, m);  
        tag[u << 1].apply(tag[u], l, m);  
        seg[u << 1 | 1].apply(tag[u], m, r);  
        tag[u << 1 | 1].apply(tag[u], m, r);  
        tag[u] = Tag();  
    }  
  
    void apply(int u, int l, int r, int ql, int qr, const Tag &t) {  
        if (l >= qr || r <= ql) return;  
        if (l >= ql && r <= qr) {  
            seg[u].apply(t, l, r);  
            tag[u].apply(t, l, r);  
            return;  
        }  
        push(u, l, r);  
        int m = l + r >> 1;  
        apply(u << 1, l, m, ql, qr, t);  
        apply(u << 1 | 1, m, r, ql, qr, t);  
        seg[u] = Info::merge(seg[u << 1], seg[u << 1 | 1]);  
    }  
  
    Info query(int u, int l, int r, int ql, int qr) {  
        if (l >= qr || r <= ql) return Info();  
        if (l >= ql && r <= qr) return seg[u];  
        push(u, l, r);  
        int m = l + r >> 1;  
        return Info::merge(query(u << 1, l, m, ql, qr),  
                           query(u << 1 | 1, m, r, ql, qr));  
    }  
};

区间加区间乘懒标记

区间乘区间加的懒标记实现，对 p 取模。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
i64 p = 1e9 + 7;

struct Tag {
    i64 mul = 1;
    i64 add = 0;

    void apply(const Tag &t, int l, int r) {
        mul = (mul * t.mul) % p;
        add = (add * t.mul) % p;
        add = (add + t.add) % p;
    }
};

struct Info {
    i64 val = 0;

    void apply(const Tag &t, int l, int r) {
        val = (val * t.mul + t.add * (r - l)) % p;
    }

    static Info merge(const Info &a, const Info &b) {
        return {(a.val + b.val) % p};
    }
};

动态开点线段树

结点只有在有需要的时候才被创建，一次操作最多也新增 log n 量级的结点，且没有浪费。

单次操作的时间复杂度是不变的，为 O(log n) 。由于每次操作都有可能创建并访问全新的一系列结点，因此 m 次单点操作后结点的数量规模是 O(mlog n)。

节点 0 作为空节点，使用前需调用 create 函数以生成根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
template<typename Info, typename Tag>  
struct SegmentTree {  
    vector<Info> seg;  
    vector<Tag> tag;  
    vector<int> lch, rch;  
  
    explicit SegmentTree() : seg(1), tag(1), lch(1), rch(1) {  
    }  
  
    int create() {  
        int x = seg.size();  
        seg.emplace_back();  
        tag.emplace_back();  
        lch.push_back(0);  
        rch.push_back(0);  
        return x;  
    }
  
    void push(int u, int l, int r) {  
        int m = l + r >> 1;  
        seg[lch[u]].apply(tag[u], l, m);  
        tag[lch[u]].apply(tag[u], l, m);  
        seg[rch[u]].apply(tag[u], m, r);  
        tag[rch[u]].apply(tag[u], m, r);  
        tag[u] = Tag();  
    }  
  
    void apply(int u, int l, int r, int ql, int qr, const Tag &t) {  
        if (l >= qr || r <= ql) return;  
        if (l >= ql && r <= qr) {  
            seg[u].apply(t, l, r);  
            tag[u].apply(t, l, r);  
            return;  
        }  
        push(u, l, r);  
        int m = l + r >> 1;  
        if (!lch[u]) lch[u] = create();  
        if (!rch[u]) rch[u] = create();  
        apply(lch[u], l, m, ql, qr, t);  
        apply(rch[u], m, r, ql, qr, t);  
        seg[u] = Info::merge(seg[lch[u]], seg[rch[u]]);  
    }  
  
    Info query(int u, int l, int r, int ql, int qr) {  
        if (!u || l >= qr || r <= ql) return Info();  
        if (l >= ql && r <= qr) return seg[u];  
        push(u, l, r);  
        int m = l + r >> 1;  
        return Info::merge(query(lch[u], l, m, ql, qr),  
                           query(rch[u], m, r, ql, qr));  
    }  
};

李超线段树

李超线段树在每个节点维护在区间中点处取值最优的线段，实现动态插入线段，单点查询最优线段。

插入操作通过递归比较中点值交换线段并下传，均摊时间复杂度 O(log2n) ，查询操作沿树路径收集候选线段并比较，时间复杂度 O(log n) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
struct Line {  
    f80 k, b;  
    int id;  
  
    f80 f(i64 x) const {  
        return k * x + b;  
    }  
  
    static bool better(const Line &a, const Line &b, i64 x) {  
        f80 ya = a.f(x), yb = b.f(x);  
        if (fabs(ya - yb) < eps) return a.id < b.id;  
        return ya > yb;  
    }  
};  
  
template<typename Line>  
struct LiChaoTree {  
    vector<Line> seg;  
    vector<int> lch, rch;  
  
    LiChaoTree() : seg(1), lch(1), rch(1) {  
    }  
  
    int create() {  
        int x = seg.size();  
        seg.emplace_back();  
        lch.push_back(0);  
        rch.push_back(0);  
        return x;  
    }  
  
    void update(int u, i64 l, i64 r, Line val) {  
        if (seg[u].id == 0) {  
            seg[u] = val;  
            return;  
        }  
        i64 m = l + r >> 1;  
        if (Line::better(val, seg[u], m)) swap(val, seg[u]);  
        if (r - l == 1) return;  
        if (Line::better(val, seg[u], l)) {  
            if (!lch[u]) lch[u] = create();  
            update(lch[u], l, m, val);  
        } else if (Line::better(val, seg[u], r)) {  
            if (!rch[u]) rch[u] = create();  
            update(rch[u], m, r, val);  
        }  
    }  
  
    void insert(int u, i64 l, i64 r, i64 ql, i64 qr, const Line &val) {  
        if (ql >= r || qr <= l) return;  
        if (ql <= l && r <= qr) {  
            update(u, l, r, val);  
            return;  
        }  
        i64 m = l + r >> 1;  
        if (ql < m) {  
            if (!lch[u]) lch[u] = create();  
            insert(lch[u], l, m, ql, qr, val);  
        }  
        if (qr > m) {  
            if (!rch[u]) rch[u] = create();  
            insert(rch[u], m, r, ql, qr, val);  
        }  
    }  
  
    Line query(int u, i64 l, i64 r, i64 x) {  
        if (!u) return Line{};  
        Line res = seg[u];  
        if (l == r) return res;  
        i64 m = l + r >> 1;  
        Line nres{};  
        if (x < m) nres = query(lch[u], l, m, x);  
        else nres = query(rch[u], m, r, x);  
        if (!res.id) return nres;  
        if (!nres.id) return res;  
        return Line::better(res, nres, x) ? res : nres;  
    }  
};

猫树

待更新

堆

堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。

配对堆

配对堆是一种基于多叉树结构的优先队列，通过动态合并兄弟节点实现高效的插入、合并和删除最小元素和减少一个元素的值等操作，尤其适合需要频繁合并的场景，其插入和合并的均摊时间复杂度为 O(1) ，删除操作为 O(log n) 。

本模板需要在外部维护根节点及弹出信息，涉及到对根节点修改的函数均返回新根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
template<typename T>  
struct PairingHeap {  
    vector<T> val;  
    vector<int> ch, si, fa;  
  
    explicit PairingHeap(): val(1), ch(1), si(1), fa(1) {  
    }  
  
    int create(T x) {  
        int u = val.size();  
        val.push_back(x);  
        ch.push_back(0);  
        si.push_back(0);  
        fa.push_back(0);  
        return u;  
    }  
  
    int meld(int x, int y) {  
        if (!x) return y;  
        if (!y) return x;  
        if (val[x] > val[y]) swap(x, y);  
        if (ch[x]) fa[ch[x]] = y;  
        si[y] = ch[x];  
        ch[x] = y, fa[y] = x;  
        return x;  
    }  
  
    int merge(int x) {  
        fa[x] = fa[si[x]] = 0;  
        if (!x || !si[x]) return x;  
        int y = si[x], z = si[y];  
        return meld(meld(x, y), merge(z));  
    }  
  
    int push(int rt, T x) {  
        return meld(rt, create(x));  
    }  
  
    T top(int rt) {  
        return val[rt];  
    }  
  
    int pop(int rt) {  
        return merge(ch[rt]);  
    }  
  
    int modify(int rt, int x, T v) {  
        val[x] = v;  
        if (x == rt) return rt;  
        if (ch[fa[x]] == x) ch[fa[x]] = si[x];  
        else si[fa[x]] = si[x];  
        if (si[x]) fa[si[x]] = fa[x];  
        si[x] = fa[x] = 0;  
        return meld(rt, x);  
    }  
};

二叉平衡树

二叉平衡树通过旋转或调整操作（如 AVL 树 的平衡因子、红黑树 的颜色规则）保持左右子树高度差在一定范围内，从而确保查找、插入、删除等操作的最坏时间复杂度为 O(log n)。

笛卡尔树

笛卡尔树是一种二叉树，每一个节点由一个键值二元组 (k, w) 构成。要求 k 满足二叉搜索树的性质，而 w 满足堆的性质。

如果笛卡尔树的 k, w 键值确定，且 k 互不相同， w 也互不相同，那么这棵笛卡尔树的结构是唯一的。

对于一个无重复元素的笛卡尔树有以下性质。

  • w 在树中满足堆的性质，而 k 满足二叉搜索树的性质。
  • 中序遍历笛卡尔树可以得到原序列。
  • 数列元素与节点构成一一映射关系。

竞赛中使用笛卡尔树时，常用数组下标作为二元组的键值 k ，如以下构建笛卡尔树实现。

1
2
3
4
5
6
7
8
9
int root = 0;
stack<int> stk;
vector<int> lch(n + 1), rch(n + 1);
for (int i = 1; i <= n; ++i) {
    while (!stk.empty() && a[stk.top()] > a[i]) stk.pop();
    if (stk.empty()) lch[i] = root, root = i;
    else lch[i] = rch[stk.top()], rch[stk.top()] = i;
    stk.emplace(i);
}

Treap 树

无旋 Treap 树

Splay 树

Splay 树是一种自调整二叉搜索树，通过将最近访问的节点移至根部（伸展操作）来优化后续访问效率，确保操作的均摊时间复杂度为 O(log n) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
template<typename T>  
struct Splay {  
    int rt = 0;  
    vector<T> val;  
    vector<array<int, 2> > ch;  
    vector<int> fa, sz, cnt;  
  
    Splay() : val(1), ch(1), fa(1), sz(1), cnt(1) {  
        rt = 0;  
    }  
  
    void create(int f, T v) {  
        val.push_back(v);  
        ch.emplace_back();  
        fa.push_back(f);  
        sz.push_back(1);  
        cnt.push_back(1);  
    }  
  
    int get(int x) const {  
        return x == ch[fa[x]][1];  
    }  
  
    void pull(int x) {  
        sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];  
    }  
  
    void rotate(int x) {  
        int y = fa[x], z = fa[y], dir = get(x);  
        if (z) ch[z][get(y)] = x;  
        if (ch[x][dir ^ 1]) fa[ch[x][dir ^ 1]] = y;  
        fa[y] = x, fa[x] = z;  
        ch[y][dir] = ch[x][dir ^ 1], ch[x][dir ^ 1] = y;  
        pull(y), pull(x);  
    }  
  
    void splay(int x) {  
        for (int f; (f = fa[x]); rotate(x)) {  
            if (fa[f]) rotate(get(x) == get(f) ? f : x);  
        }  
        rt = x;  
    }  
  
    void insert(T v) {  
        int tot = val.size();  
        if (!rt) {  
            create(rt, v), rt = tot;  
            return;  
        }  
        int x = rt, f = 0;  
        while (x) {  
            f = x;  
            if (val[x] == v) break;  
            int dir = v > val[x];  
            x = ch[x][dir];  
        }  
        if (!x && f) create(f, v), ch[f][val[f] < v] = tot, splay(tot);  
        if (x) cnt[x]++, pull(x), splay(x);  
    }  
  
    int find(T v) {  
        int x = rt, f = 0;  
        while (x) {  
            f = x;  
            if (val[x] == v) break;  
            int dir = v > val[x];  
            x = ch[x][dir];  
        }  
        if (!x && f) splay(f);  
        if (x) splay(x);  
        return x;  
    }  
  
    void remove(T v) {  
        int x = find(v);  
        if (!x) return;  
        if (cnt[x] > 1) {  
            --cnt[x];  
            pull(x);  
            return;  
        }  
        int l = ch[x][0], r = ch[x][1];  
        ch[x][0] = ch[x][1] = fa[x] = 0;  
        if (!l && !r) {  
            rt = 0;  
        } else if (!l) {  
            rt = r, fa[r] = 0;  
        } else if (!r) {  
            rt = l, fa[l] = 0;  
        } else {  
            int pre = l;  
            while (ch[pre][1]) pre = ch[pre][1];  
            splay(pre);  
            ch[pre][1] = r;  
            fa[r] = pre;  
            pull(pre);  
            rt = pre;  
        }  
    }  
  
    int rank(T v) {  
        int x = rt, res = 0;  
        while (x) {  
            if (v < val[x]) {  
                x = ch[x][0];  
            } else {  
                res += sz[ch[x][0]];  
                if (v == val[x]) break;  
                res += cnt[x];  
                x = ch[x][1];  
            }  
        }  
        if (x) splay(x);  
        return res + 1;  
    }  
  
    T kth(int k) {  
        int x = rt;  
        while (x) {  
            int lsz = sz[ch[x][0]];  
            if (k <= lsz) x = ch[x][0];  
            else if (k <= lsz + cnt[x]) break;  
            else k -= lsz + cnt[x], x = ch[x][1];  
        }  
        if (x) splay(x);  
        return val[x];  
    }  
  
    T prev(T v) {  
        int x = rt, res = 0;  
        while (x) {  
            if (val[x] < v) res = x, x = ch[x][1];  
            else x = ch[x][0];  
        }  
        if (res) splay(res);  
        return val[res];  
    }  
  
    T next(T v) {  
        int x = rt, res = 0;  
        while (x) {  
            if (val[x] > v) res = x, x = ch[x][0];  
            else x = ch[x][1];  
        }  
        if (res) splay(res);  
        return val[res];  
    }  
};

动态树

Link-Cut Tree 是一种用于高效维护动态森林（支持树的连接、分割）和路径查询的数据结构，其核心操作（连接、分割、路径查询等）的均摊时间复杂度为 O(log n)，广泛应用于动态图算法和网络流问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
template<typename T>  
struct LCT {  
    vector<T> val, sum;  
    vector<array<int, 2> > ch;  
    vector<int> fa, rev, sz;  
  
    LCT() : val(1), sum(1), ch(1), fa(1), rev(1), sz(1) {  
    }  
  
    int create(T v) {  
        int x = val.size();  
        val.push_back(v);  
        sum.push_back(v);  
        ch.emplace_back();  
        fa.push_back(0);  
        rev.push_back(0);  
        sz.push_back(1);  
        return x;  
    }  
  
    bool get(int x) const {  
        return x == ch[fa[x]][1];  
    }  
  
    bool root(int x) const {  
        return x != ch[fa[x]][0] && x != ch[fa[x]][1];  
    }  
  
    void push(int x) {  
        if (!x || !rev[x]) return;  
        if (ch[x][0]) rev[ch[x][0]] = !rev[ch[x][0]];  
        if (ch[x][1]) rev[ch[x][1]] = !rev[ch[x][1]];  
        swap(ch[x][0], ch[x][1]);  
        rev[x] = 0;  
    }  
  
    void update(int p) {  
        if (!root(p)) update(fa[p]);  
        push(p);  
    }  
  
    void pull(int x) {  
        sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;  
        sum[x] = val[x] + sum[ch[x][0]] + sum[ch[x][1]];  
    }  
  
    void rotate(int x) {  
        int y = fa[x], z = fa[y], dir = get(x);  
        if (!root(y)) ch[z][get(y)] = x;  
        if (ch[x][dir ^ 1]) fa[ch[x][dir ^ 1]] = y;  
        fa[y] = x, fa[x] = z;  
        ch[y][dir] = ch[x][dir ^ 1], ch[x][dir ^ 1] = y;  
        pull(y), pull(x);  
    }  
  
    void splay(int x) {  
        update(x);  
        for (int f; f = fa[x], !root(x); rotate(x)) {  
            if (!root(f)) rotate(get(x) == get(f) ? f : x);  
        }  
    }  
  
    void access(int x) {  
        for (int p = 0; x; p = x, x = fa[x]) {  
            splay(x), ch[x][1] = p, pull(x);  
        }  
    }  
  
    void makeroot(int x) {  
        access(x);  
        splay(x);  
        rev[x] = !rev[x];  
        push(x);  
    }  
  
    int find(int x) {  
        access(x);  
        splay(x);  
        while (ch[x][0]) x = ch[x][0], push(x);  
        splay(x);  
        return x;  
    }  
  
    void split(int x, int y) {  
        makeroot(x);  
        access(y);  
        splay(y);  
    }  
  
    bool link(int x, int y) {  
        makeroot(x);  
        if (find(y) == x) return false;  
        fa[x] = y;  
        return true;  
    }  
  
    bool cut(int x, int y) {  
        makeroot(x);  
        if (find(y) != x || fa[y] != x || ch[y][0]) return false;  
        fa[y] = ch[x][1] = 0;  
        pull(x);  
        return true;  
    }  
  
    void modify(int x, T v) {  
        splay(x);  
        val[x] = v;  
        pull(x);  
    }  
  
    T query(int x, int y) {  
        split(x, y);  
        return sum[y];  
    }  
};

Top Tree

待更新

可持久化数据结构

可持久化数据结构总是可以保留每一个历史版本，并且支持操作的不可变特性。

本模板的可持久化数据结构均带有成员函数 branch ，表示在版本 u 的基础上新建分支版本。

修改函数的 u 和 v 参数表示在版本 u 的基础上修改，并将修改后的结果保存至版本 v。

推荐使用方法为：调用 branch 创建新版本后，为 u 和 v 传入相同版本以支持多次修改。

可持久化线段树

实现了单点修改区间查询的可持久化线段树，修改和查询操作的时空复杂度均为 Θ(log n) ，调用 build 函数可以执行 O(n) 建树并返回根。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
template<typename Info>  
struct PersistentSegmentTree {  
    vector<Info> seg;  
    vector<int> lch, rch;  
  
    explicit PersistentSegmentTree() : seg(1), lch(1), rch(1) {  
    }  
  
    int build(const vector<Info> &val) {  
        auto build = [&](auto &&self, int u, int l, int r) {  
            if (r - l == 1) {  
                seg[u] = val[l];  
                return;  
            }  
            int m = l + r >> 1;  
            self(self, lch[u] = create(), l, m);  
            self(self, rch[u] = create(), m, r);  
            seg[u] = Info::merge(seg[lch[u]], seg[rch[u]]);  
        };  
        int rt = create();  
        build(build, rt, 1, val.size());  
        return rt;  
    }  
  
    int create() {  
        int x = seg.size();  
        seg.emplace_back();  
        lch.push_back(0);  
        rch.push_back(0);  
        return x;  
    }  
  
    int branch(int u) {  
        int v = create();  
        seg[v] = seg[u];  
        lch[v] = lch[u];  
        rch[v] = rch[u];  
        return v;  
    }  
  
    void modify(int u, int v, int l, int r, int x, Info k) {  
        if (r - l == 1) {  
            seg[v] = k;  
            return;  
        }  
        int m = l + r >> 1;  
        if (x < m) {  
            int lu = lch[u];  
            rch[v] = rch[u];  
            modify(lu, lch[v] = create(), l, m, x, k);  
        } else {  
            int ru = rch[u];  
            lch[v] = lch[u];  
            modify(ru, rch[v] = create(), m, r, x, k);  
        }  
        seg[v] = Info::merge(seg[lch[v]], seg[rch[v]]);  
    }  
  
    Info query(int u, int l, int r, int ql, int qr) {  
        if (!u || l >= qr || r <= ql) return Info();  
        if (l >= ql && r <= qr) return seg[u];  
        int m = l + r >> 1;  
        return Info::merge(query(lch[u], l, m, ql, qr),  
                           query(rch[u], m, r, ql, qr));  
    }  
};

可持久化权值线段树 / 主席树

主席树是一种线段树差分的思想，基于可持久化权值线段树实现的主席树可以实现查询区间第 k 小的功能，修改和查询操作的时空复杂度均为 Θ(log n) ，其中 n 是值域大小。

seg.kth(rt[l - 1], rt[r], 0, maxv + 1, k); 在主席树上二分以查询区间 [l, r] 的第 k 小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
template<typename T>  
struct PersistentSegmentTree {  
    vector<T> seg;  
    vector<int> lch, rch;  
  
    explicit PersistentSegmentTree() : seg(1), lch(1), rch(1) {  
    }  
  
    int create() {  
        int x = seg.size();  
        seg.emplace_back();  
        lch.push_back(0);  
        rch.push_back(0);  
        return x;  
    }  
  
    int branch(int u) {  
        int v = create();  
        seg[v] = seg[u];  
        lch[v] = lch[u];  
        rch[v] = rch[u];  
        return v;  
    }  
  
    void modify(int u, int v, int l, int r, int x, T k) {  
        if (r - l == 1) {  
            seg[v] = seg[u] + k;  
            return;  
        }  
        int m = l + r >> 1;  
        if (x < m) {  
            int lu = lch[u];  
            rch[v] = rch[u];  
            modify(lu, lch[v] = create(), l, m, x, k);  
        } else {  
            int ru = rch[u];  
            lch[v] = lch[u];  
            modify(ru, rch[v] = create(), m, r, x, k);  
        }  
        seg[v] = seg[lch[v]] + seg[rch[v]];  
    }  
  
    int kth(int u, int v, int l, int r, int k) {  
        int m = l + r >> 1;  
        if (r - l == 1) return l;  
        int x = seg[lch[v]] - seg[lch[u]];  
        if (k <= x) return kth(lch[u], lch[v], l, m, k);  
        return kth(rch[u], rch[v], m, r, k - x);  
    }  
};

标记永久化 / 区间修改

使用标记永久化的思想实现可区间修改的可持久化线段树及其树上二分查询第 k 小，修改和查询操作的时空复杂度均为 Θ(log n) ，其中 n 是值域大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
template<typename T>  
struct PersistentSegmentTree {  
    vector<T> seg, tag;  
    vector<int> lch, rch;  
  
    explicit PersistentSegmentTree() : seg(1), tag(1), lch(1), rch(1) {  
    }  
  
    int create() {  
        int x = seg.size();  
        seg.emplace_back();  
        tag.emplace_back();  
        lch.push_back(0);  
        rch.push_back(0);  
        return x;  
    }  
  
    int branch(int u) {  
        int v = create();  
        seg[v] = seg[u];  
        lch[v] = lch[u];  
        rch[v] = rch[u];  
        tag[v] = tag[u];  
        return v;  
    }  
  
    void apply(int u, int v, int l, int r, int ql, int qr, T k) {  
        if (ql >= r || qr <= l) return;  
        if (ql <= l && r <= qr) {  
            tag[v] = tag[u] + k;  
            seg[v] = seg[u] + k * (r - l);  
            return;  
        }  
        int m = l + r >> 1;  
        int lu = lch[u], ru = rch[u];  
        if (ql < m) apply(lu, lch[v] = create(), l, m, ql, qr, k);  
        else lch[v] = lu;  
        if (qr > m) apply(ru, rch[v] = create(), m, r, ql, qr, k);  
        else rch[v] = ru;  
        seg[v] = seg[lch[v]] + seg[rch[v]] + tag[v] * (r - l);  
    }  
  
    T query(int u, int v, int l, int r, int ql, int qr, T t) {  
        if (ql >= r || qr <= l) return T();  
        if (ql <= l && r <= qr) return seg[v] - seg[u] + t * (r - l);  
        int m = l + r >> 1;  
        return query(lch[u], lch[v], l, m, ql, qr, t + tag[v] - tag[u]) +  
               query(rch[u], rch[v], m, r, ql, qr, t + tag[v] - tag[u]);  
    }  
  
    int kth(int u, int v, int l, int r, int k, T t) {  
        if (r - l == 1) return l;  
        int m = l + r >> 1;  
        T x = seg[lch[v]] - seg[lch[u]] + (t + tag[v] - tag[u]) * (m - l);  
        if (k <= x) return kth(lch[u], lch[v], l, m, k, t + tag[v] - tag[u]);  
        return kth(rch[u], rch[v], m, r, k - x, t + tag[v] - tag[u]);  
    }  
};

可持久化数组

基于可持久化线段树的可持久化数组，支持在历史版本上修改，操作复杂度 Θ(log n) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
template<typename T>  
struct PersistentArray {  
    vector<T> seg;  
    vector<int> lch, rch;  
  
    explicit PersistentArray() : seg(1), lch(1), rch(1) {  
    }  
  
    int create() {  
        int x = seg.size();  
        seg.emplace_back();  
        lch.push_back(0);  
        rch.push_back(0);  
        return x;  
    }  
  
    int branch(int u) {  
        int v = create();  
        seg[v] = seg[u];  
        lch[v] = lch[u];  
        rch[v] = rch[u];  
        return v;  
    }  
  
    void modify(int u, int v, int l, int r, int x, T k) {  
        if (r - l == 1) {  
            seg[v] = k;  
            return;  
        }  
        int m = l + r >> 1;  
        if (x < m) {  
            int lu = lch[u];  
            rch[v] = rch[u];  
            modify(lu, lch[v] = create(), l, m, x, k);  
        } else {  
            int ru = rch[u];  
            lch[v] = lch[u];  
            modify(ru, rch[v] = create(), m, r, x, k);  
        }  
    }  
  
    T query(int u, int l, int r, int x) {  
        if (r - l == 1) return seg[u];  
        int m = l + r >> 1;  
        return x < m ? query(lch[u], l, m, x) : query(rch[u], m, r, x);  
    }  
};

可持久化并查集

基于可持久化数组的可持久化并查集，支持在历史版本上修改，操作复杂度 Θ(α(log n)) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct PDSU {  
    int n;  
    vector<int> rt;  
    PersistentArray<int> p;  
  
    explicit PDSU(int n): rt(1) {  
        this->n = n;  
        for (int i = 0; i < n; i++) {  
            p.modify(0, 0, 0, n, i, -1);  
        }  
    }  
  
    int branch(int u) {  
        int v = rt.size();  
        rt.push_back(p.branch(rt[u]));  
        return v;  
    }  
  
    int find(int u, int x) {  
        int f = p.query(rt[u], 0, n, x);  
        if (f < 0) return x;  
        return find(u, f);  
    }  
  
    bool same(int u, int x, int y) {  
        return find(u, x) == find(u, y);  
    }  
  
    bool merge(int u, int x, int y) {  
        x = find(u, x), y = find(u, y);  
        if (x == y) return false;  
        int sx = p.query(rt[u], 0, n, x);  
        int sy = p.query(rt[u], 0, n, y);  
        if (sx > sy) swap(x, y);  
        p.modify(rt[u], rt[u], 0, n, x, sx + sy);  
        p.modify(rt[u], rt[u], 0, n, y, x);  
        return true;  
    }  
};

可持久化 01 字典树

trie.query(rt[l - 1], rt[r], x); 差分两个版本的字典树并优先跳对侧边以查询区间 [l, r] 中的任意与 x 的异或最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
struct Persistent01Trie {  
    static constexpr int maxb = 24;  
    vector<array<int, 2> > ch;  
    vector<int> pre;  
  
    Persistent01Trie() : ch(1), pre(1) {  
    }  
  
    int create() {  
        int x = ch.size();  
        ch.emplace_back();  
        pre.push_back(0);  
        return x;  
    }  
  
    int branch(int u) {  
        int v = create();  
        ch[v] = ch[u];  
        pre[v] = pre[u];  
        return v;  
    }  
  
    void insert(int u, int v, int x) {  
        pre[v] = pre[u] + 1;  
        for (int i = maxb; i >= 0; i--) {  
            int b = x >> i & 1;  
            int cu = ch[u][b];  
            ch[v][b] = create();  
            ch[v][!b] = ch[u][!b];  
            pre[ch[v][b]] = pre[cu] + 1;  
            u = cu, v = ch[v][b];  
        }  
    }  
  
    int query(int u, int v, int x) const {  
        int res = 0;  
        for (int i = maxb; i >= 0; i--) {  
            int b = x >> i & 1;  
            if (pre[ch[v][b ^ 1]] - pre[ch[u][b ^ 1]]) {  
                u = ch[u][b ^ 1], v = ch[v][b ^ 1], res |= 1 << i;  
            } else {  
                u = ch[u][b], v = ch[v][b];  
            }  
        }  
        return res;  
    }  
};

可持久化无旋 Treap 树

待更新

数据结构嵌套

维护多维度信息，可以考虑数据结构嵌套。

通常在外层数据结构的每个节点维护一个内层数据结构，维护每层数据结构所占用的空间是维护所有外层数据结构所需空间与该数据结构所需空间的乘积，每次操作所需的时间是维护每层数据结构所需时间的乘积。

一层数据结构可以维护一维区间或权值信息，嵌套数据结构即可完成复杂的操作。

以下是常用的数据结构。

  • 数组，直接维护原始信息，O(1) 修改，O(n) 查询，O(n) 空间
  • 前缀和数组，存储可差分信息，O(n) 修改，O(1) 查询，O(n) 空间
  • 分块，用于平衡复杂度，存储各种信息，O(1) / $O(\sqrt{n})$ 修改，$O(\sqrt{n})$ / O(1) 查询，$O(\sqrt{n})$ 空间
  • 树状数组，维护可差分信息，O(log n) 修改，O(log n) 查询，O(n) 空间
  • 线段树，维护可合并信息，O(log n) 修改，O(log n) 查询，O(qlog n) 空间
  • 平衡树，维护偏序信息，O(log n) 修改，O(log n) 查询，O(qlog n) 空间

树状数组套树状数组

树状数组套树状数组，也被称作二维树状数组，用来维护二维数组上的单点修改和前缀信息问题。

其操作可以类比一维树状数组，修改和查询操作复杂度均为 O(log2n) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<typename T>
struct Fenwick {
    vector<vector<T>> a;

    explicit Fenwick(int n, int m) : a(n, vector<T>(m)) {}

    void add(int x, int y, T v) {
        for (int i = x; i < a.size(); i += i & -i) {
            for (int j = y; j < a[i].size(); j += j & -j) {
                a[i][j] += v;
            }
        }
    }

    T sum(int x, int y) {
        auto ans = T();
        for (int i = x; i; i -= i & -i) {
            for (int j = y; j; j -= j & -j) {
                ans += a[i][j];
            }
        }
        return ans;
    }
};

子矩阵加，子矩阵和

通过维护四个二维树状数组维护差分信息，可以实现子矩阵加、求子矩阵和，左闭右闭实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Fenwick<int> d(n + 1, m + 1), di(n + 1, m + 1), dj(n + 1, m + 1), dij(n + 1, m + 1);

auto apply = [&](int x1, int y1, int x2, int y2, int v) {
    auto set = [&](int x, int y, int v) {
        d.add(x, y, v);
        di.add(x, y, v * x);
        dj.add(x, y, v * y);
        dij.add(x, y, v * x * y);
    };
    set(x1, y1, v);
    set(x1, y2 + 1, -v);
    set(x2 + 1, y1, -v);
    set(x2 + 1, y2 + 1, v);
};

auto query = [&](int x1, int y1, int x2, int y2) {
    auto get = [&](int x, int y) {
        return d.sum(x, y) * (x + 1) * (y + 1)
               - di.sum(x, y) * (y + 1)
               - dj.sum(x, y) * (x + 1)
               + dij.sum(x, y);
    };
    return get(x2, y2)
           - get(x2, y1 - 1)
           - get(x1 - 1, y2)
           + get(x1 - 1, y1 - 1);
};

线段树套线段树

外层树维护 x 区间信息，内层树维护 x 区间对应 y 区间的线段树，实现单点修改，子矩阵查询。

线段树套线段树时，外层线段树难以实现区间修改，因此难以实现通用的子矩阵修改，需要易于实现的子矩阵修改请使用树状数组套线段树。

单次操作时间复杂度 O(log2n) ，空间复杂度 O(log2n) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
struct SegmentTree {  
    vector<int> seg, lch, rch;  
  
    explicit SegmentTree() : seg(1), lch(1), rch(1) {  
    }  
  
    int create() {  
        int y = seg.size();  
        seg.emplace_back();  
        lch.push_back(0);  
        rch.push_back(0);  
        return y;  
    }  
  
    void modify(int u, int l, int r, int x, int k) {  
        if (r - l == 1) {  
            seg[u] += k;  
            return;  
        }  
        int m = l + r >> 1;  
        if (x < m) {  
            if (!lch[u]) lch[u] = create();  
            modify(lch[u], l, m, x, k);  
        } else {  
            if (!rch[u]) rch[u] = create();  
            modify(rch[u], m, r, x, k);  
        }  
        seg[u] = seg[lch[u]] + seg[rch[u]];  
    }  
  
    int query(int u, int l, int r, int ql, int qr) {  
        if (!u || l >= qr || r <= ql) return 0;  
        if (l >= ql && r <= qr) return seg[u];  
        int m = l + r >> 1;  
        return query(lch[u], l, m, ql, qr) +  
               query(rch[u], m, r, ql, qr);  
    }  
};  
  
struct NestedSegmentTree {  
    vector<int> seg, lch, rch;  
    SegmentTree segy;  
  
    explicit NestedSegmentTree() : seg(1), lch(1), rch(1) {  
    }  
  
    int create() {  
        int y = segy.create();  
        int x = seg.size();  
        seg.push_back(y);  
        lch.push_back(0);  
        rch.push_back(0);  
        return x;  
    }  
  
    void modify(int u, int lx, int rx, int ly, int ry, int x, int y, int k) {  
        segy.modify(seg[u], ly, ry, y, k);  
        if (rx - lx == 1) return;  
        int mx = lx + rx >> 1;  
        if (x < mx) {  
            if (!lch[u]) lch[u] = create();  
            modify(lch[u], lx, mx, ly, ry, x, y, k);  
        } else {  
            if (!rch[u]) rch[u] = create();  
            modify(rch[u], mx, rx, ly, ry, x, y, k);  
        }  
    }  
  
    int query(int u, int lx, int rx, int ly, int ry, int qxl, int qxr, int qyl, int qyr) {  
        if (!u || lx >= qxr || rx <= qxl) return 0;  
        if (lx >= qxl && rx <= qxr) return segy.query(seg[u], ly, ry, qyl, qyr);  
        int mx = lx + rx >> 1;  
        return query(lch[u], lx, mx, ly, ry, qxl, qxr, qyl, qyr) +  
               query(rch[u], mx, rx, ly, ry, qxl, qxr, qyl, qyr);  
    }  
};

树状数组套权值线段树/动态主席树

外层树维护区间信息，内层树维护区间对应的权值线段树，实现单点修改，查询区间第 k 大。

单次操作时间复杂度 O(log2n) ，空间复杂度 O(log2n) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
struct PersistentSegmentTree {  
    vector<int> seg;  
    vector<int> lch, rch;  
  
    explicit PersistentSegmentTree() : seg(1), lch(1), rch(1) {  
    }  
  
    int create() {  
        int y = (int) seg.size();  
        seg.emplace_back();  
        lch.push_back(0);  
        rch.push_back(0);  
        return y;  
    }  
  
    void modify(int u, int l, int r, int y, int k) {  
        if (r - l == 1) {  
            seg[u] += k;  
            return;  
        }  
        int m = l + r >> 1;  
        if (y < m) {  
            if (!lch[u]) lch[u] = create();  
            modify(lch[u], l, m, y, k);  
        } else {  
            if (!rch[u]) rch[u] = create();  
            modify(rch[u], m, r, y, k);  
        }  
        seg[u] = seg[lch[u]] + seg[rch[u]];  
    }  
  
    int query(vector<int> &u, vector<int> &v, int l, int r, int k) {  
        if (r - l == 1) return l;  
        int x = 0;  
        for (auto i: u) x -= seg[lch[i]];  
        for (auto i: v) x += seg[lch[i]];  
        int m = l + r >> 1;  
        if (k <= x) {  
            for (auto &i: u) i = lch[i];  
            for (auto &i: v) i = lch[i];  
            return query(u, v, l, m, k);  
        } else {  
            for (auto &i: u) i = rch[i];  
            for (auto &i: v) i = rch[i];  
            return query(u, v, m, r, k - x);  
        }  
    }  
};  
  
struct FenwickNestedSegmentTree {  
    vector<int> a;  
    PersistentSegmentTree segy;  
  
    explicit FenwickNestedSegmentTree(int n) : a(n) {  
        for (int i = 1; i < n; i++) a[i] = segy.create();  
    }  
  
    void modify(int x, int l, int r, int y, int k) {  
        for (int i = x; i < a.size(); i += i & -i) {  
            segy.modify(a[i], l, r, y, k);  
        }  
    }  
  
    int kth(int l, int r, int lv, int rv, int v) {  
        vector<int> rtu, rtv;  
        for (int i = l; i; i -= i & -i) rtu.push_back(a[i]);  
        for (int i = r; i; i -= i & -i) rtv.push_back(a[i]);  
        return segy.query(rtu, rtv, lv, rv, v);  
    }  
};

K-D Tree

K-D Tree 是一种维护 k 维空间中点的数据结构，支持高效范围查询和最近邻搜索。

以下实现是一个动态插入、支持范围查询的 K-D Tree，使用二进制分组维护动态插入操作：插入时间均摊 O(log2n)，查询 $O(\sqrt{n})$，空间 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
struct KDTree {  
    struct Node {  
        int val, sum;  
        array<int, 2> p, l, r;  
    };  
  
    vector<Node> nd;  
    vector<int> lch, rch, rt, re;  
  
    KDTree() : nd(1), lch(1), rch(1), rt(1) {  
    }  
  
    int create() {  
        int x = lch.size();  
        lch.push_back(0);  
        rch.push_back(0);  
        nd.emplace_back();  
        return x;  
    }  
  
    void update(int x) {  
        nd[x].sum = nd[x].val;  
        nd[x].l = nd[x].r = nd[x].p;  
        for (int ch: {lch[x], rch[x]}) {  
            if (!ch) continue;  
            nd[x].sum += nd[ch].sum;  
            for (int d: {0, 1}) {  
                nd[x].l[d] = min(nd[x].l[d], nd[ch].l[d]);  
                nd[x].r[d] = max(nd[x].r[d], nd[ch].r[d]);  
            }  
        }  
    }  
  
    void recycle(int u) {  
        if (!u) return;  
        re.push_back(u);  
        if (lch[u]) recycle(lch[u]);  
        if (rch[u]) recycle(rch[u]);  
    }  
  
    int build(int l, int r, int d = 0) {  
        if (l >= r) return 0;  
        int m = l + r >> 1;  
        nth_element(re.begin() + l, re.begin() + m, re.begin() + r,  
                    [&](int x, int y) { return nd[x].p[d] < nd[y].p[d]; });  
        int x = re[m];  
        lch[x] = build(l, m, d ^ 1);  
        rch[x] = build(m + 1, r, d ^ 1);  
        update(x);  
        return x;  
    }  
  
    void insert(array<int, 2> p, int v) {  
        re.clear();  
        int x = create();  
        nd[x].p = p, nd[x].val = v;  
        re.push_back(x);  
        int i = 0;  
        while (i < rt.size() && rt[i]) recycle(rt[i]), rt[i] = 0, i++;  
        if (i == rt.size()) rt.push_back(0);  
        rt[i] = build(0, re.size());  
    }  
  
    int query(int u, array<int, 2> ql, array<int, 2> qr) {  
        if (!u) return 0;  
        bool f1 = false, f2 = true, f3 = true;  
        for (int k: {0, 1}) f1 |= nd[u].l[k] > qr[k] || nd[u].r[k] < ql[k];  
        if (f1) return 0;  
        for (int k: {0, 1}) f2 &= nd[u].l[k] >= ql[k] && nd[u].r[k] <= qr[k];  
        if (f2) return nd[u].sum;  
        for (int k: {0, 1}) f3 &= nd[u].p[k] >= ql[k] && nd[u].p[k] <= qr[k];  
        return (f3 ? nd[u].val : 0) + query(lch[u], ql, qr) + query(rch[u], ql, qr);  
    }  
};

邻域查询

小波矩阵

小波矩阵的核心思想是通过多层位分解将序列按二进制位分层处理，每层通过位向量记录元素的分组信息，实现了高效地对数组执行各种操作。

小波矩阵的操作时间常数很小，且空间复杂度为 $O(\frac{n\log{V}}{\omega})$ ，在常见值域或离散化后可视为线性空间复杂度 O(n) 。

操作 说明 时间复杂度
rank(l, r, v) 区间 [l, r) 中 v 出现次数 O(log V)
kth(l, r, k) 区间 [l, r) 中第 k 小元素 O(log V)
rangefreq(l, r, a, b) 区间 [l, r) 中值域 [a, b) 内元素数量 O(log V)
rangemin(l, r, a, b) 区间 [l, r) 中值域 [a, b) 内最小值 O(log V) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
struct BitRank {  
    vector<u64> B;  
    vector<int> cnt;  
  
    explicit BitRank(int n) : B(((n + 1) >> 6) + 1), cnt(B.size()) {  
    }  
  
    void set(int i, u64 val) { B[i >> 6] |= val << (i & 63); }  
  
    void build() {  
        for (int i = 1; i < B.size(); i++) {  
            cnt[i] = cnt[i - 1] + __builtin_popcountll(B[i - 1]);  
        }  
    }  
  
    int rank1(int i) { return cnt[i >> 6] + __builtin_popcountll(B[i >> 6] & (1ull << (i & 63)) - 1); }  
  
    int rank0(int i) { return i - rank1(i); }  
};  
  
struct WaveletMatrix {  
    int ht;  
    vector<int> pos;  
    vector<BitRank> bk;  
  
    explicit WaveletMatrix(vector<int> vec) {  
        int sig = *max_element(vec.begin(), vec.end());  
        ht = sig == 0 ? 1 : 64 - __builtin_clzll(sig);  
        pos.resize(ht), bk.resize(ht, BitRank(vec.size()));  
        for (int i = 0; i < ht; i++) {  
            for (int j = 0; j < vec.size(); j++) {  
                bk[i].set(j, vec[j] >> (ht - i - 1) & 1);  
            }  
            bk[i].build();  
            auto it = stable_partition(vec.begin(), vec.end(), [&](int c) {  
                return ~c >> (ht - i - 1) & 1;  
            });  
            pos[i] = it - vec.begin();  
        }  
    }  
  
    int rank(int i, int v) {  
        int p = 0;  
        for (int j = 0; j < ht; j++) {  
            if (v >> (ht - j - 1) & 1) {  
                p = pos[j] + bk[j].rank1(p);  
                i = pos[j] + bk[j].rank1(i);  
            } else {  
                p = bk[j].rank0(p);  
                i = bk[j].rank0(i);  
            }  
        }  
        return i - p;  
    }  
  
    int rank(int l, int r, int v) {  
        return rank(r, v) - rank(l, v);  
    }  
  
    int kth(int l, int r, int k) {  
        int res = 0;  
        for (int i = 0; i < ht; i++) {  
            int j = bk[i].rank0(r) - bk[i].rank0(l);  
            if (j > k) {  
                l = bk[i].rank0(l);  
                r = bk[i].rank0(r);  
            } else {  
                l = pos[i] + bk[i].rank1(l);  
                r = pos[i] + bk[i].rank1(r);  
                k -= j;  
                res |= 1 << (ht - i - 1);  
            }  
        }  
        return res;  
    }  
  
    int rangefreq(int i, int j, int a, int b, int l, int r, int x) {  
        if (i == j || r <= a || b <= l) return 0;  
        int m = (l + r) >> 1;  
        if (a <= l && r <= b) return j - i;  
        int left = rangefreq(bk[x].rank0(i), bk[x].rank0(j), a, b, l, m, x + 1);  
        int right = rangefreq(pos[x] + bk[x].rank1(i), pos[x] + bk[x].rank1(j), a, b, m, r, x + 1);  
        return left + right;  
    }  
  
    int rangefreq(int l, int r, int a, int b) {  
        return rangefreq(l, r, a, b, 0, 1 << ht, 0);  
    }  
  
    int rangemin(int i, int j, int a, int b, int l, int r, int x, int v) {  
        if (i == j || r <= a || b <= l) return -1;  
        if (r - l == 1) return v;  
        int m = (l + r) >> 1;  
        int res = rangemin(bk[x].rank0(i), bk[x].rank0(j), a, b, l, m, x + 1, v);  
        if (res >= 0) return res;  
        return rangemin(pos[x] + bk[x].rank1(i), pos[x] + bk[x].rank1(j), a, b, m, r, x + 1, v + (1 << (ht - x - 1)));  
    }  
  
    int rangemin(int l, int r, int a, int b) {  
        return rangemin(l, r, a, b, 0, 1 << ht, 0, 0);  
    }  
};