数据结构

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

并查集

含有路径压缩和按集合大小合并优化的并查集实现，可以查询集合元素数量，每个操作的均摊复杂度为 $O(\alpha(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);  
    }  
  
    bool merge(int x, int y) {  
        x = find(x), y = find(y);  
        if (x == y) return false;  
        if (p[x] > p[y]) swap(x, y);  
        p[x] += p[y], p[y] = x;  
        return true;  
    }  
};

珂朵莉树

珂朵莉树是一种基于区间合并的数据结构，通过将序列划分为多个值相同的连续区间来高效处理区间赋值和查询操作，其时间复杂度在平均情况下为均摊 $O(m\log{n})$ ，但最坏情况下可能退化为 $O(mn)$ ，其中 $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 表是基于倍增思想，用于解决可重复贡献问题的数据结构，可以做到 $\Theta(n\log n)$ 预处理，$\Theta(1)$ 回答每个询问。

本实现为左闭右闭实现，提供了向 ST 表末尾新增元素的方法，复杂度 $\Theta(\log n)$ 。注意本实现使用了 c++20 的 bit 库，但 bit_width(x) 可以被等价替代为 (int) log2(x) + 1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<typename T>
struct SparseTable {
    vector<vector<T>> st = {{}};

    void append(T t) {
        u64 p = st[0].size(), d = bit_width(p + 1);
        if (d > st.size()) st.emplace_back(p);
        st[0].emplace_back(t);
        for (int i = 1; i < d; ++i) {
            st[i].emplace_back(max(st[i - 1][p], st[i - 1][p - (1 << (i - 1))]));
        }
    }

    T query(u64 l, u64 r) {
        u64 d = bit_width(r - l + 1);
        return max(st[d - 1][r], st[d - 1][l + (1 << (d - 1)) - 1]);
    }
};

分块

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

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

普通分块

单点修改前缀和查询，对权值分块时称为值域分块，$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];
    }
};

块状数组

以简单通用的方式实现块状数组，可以方便地修改分块逻辑。

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(1e9), 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;  
};

树状数组

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

普通树状数组

最基础的树状数组，可以进行单点修改和前缀和查询操作，复杂度均为 $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));  
    }  
};

动态开点线段树

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

单次操作的时间复杂度是不变的，为 $O(\log{n})$ 。由于每次操作都有可能创建并访问全新的一系列结点，因此 $m$ 次单点操作后结点的数量规模是 $O(m\log{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));  
    }  
};

区间加区间乘

区间乘区间加的懒标记实现，对 $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};
    }
};

堆

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

配对堆

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

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];  
    }  
};

可持久化数据结构

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

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

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

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

可持久化线段树

实现了单点修改区间查询的可持久化线段树，修改和查询操作的时空复杂度均为 $\Theta(\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$ 小的功能，修改和查询操作的时空复杂度均为 $\Theta(\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);  
    }  
};

可持久化数组

基于可持久化线段树的可持久化数组，支持在历史版本上修改，操作复杂度 $\Theta(\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);  
    }  
};

可持久化并查集

基于可持久化数组的可持久化并查集，支持在历史版本上修改，操作复杂度 $\Theta(\alpha(\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;  
    }  
};

数据结构嵌套

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

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

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

以下是常用的数据结构。

  • 数组，直接维护原始信息，$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(q\log{n})$ 空间
  • 平衡树，维护偏序信息，$O(\log{n})$ 修改，$O(\log{n})$ 查询，$O(q\log{n})$ 空间

树状数组套树状数组

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

其操作可以类比一维树状数组，修改和查询操作复杂度均为 $O(log^{2}{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 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(\log^2{n})$ ，空间复杂度 $O(\log^2{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
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(\log^2{n})$ ，空间复杂度 $O(\log^2{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
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);  
    }  
};