第八章 线段树的进阶用法

• 可持久化线段树
  • 例1：P3834 【模板】可持久化线段树 2
  • 例2：P4587 [FJOI2016]神秘数
• 树状数组套权值线段树
  • 例3：P3380 【模板】二逼平衡树（树套树）
  • 例4：P3810 【模板】三维偏序（陌上花开）

我们知道，对于一棵线段树而言，如果它的总长度不变，那么它的形态是不会改变的。也就是说，在值域不变情况下，权值树的形态是不会改变的。这样一来，就可以对权值树进行合并的操作。对于权值树 $A, B$，若 $A, B$ 形态相同，则可以合并这两棵权值树，合并的方式就是对应节点相加。

显然，合并后的树依然是一棵权值线段树。可以将权值线段树的合并类比为加法。类似的，也可以类比得到权值线段树的减法，即对应点数相减。

可持久化线段树

例1：P3834 【模板】可持久化线段树 2

例2：P4587 [FJOI2016]神秘数

考虑对于一个一定确定的可重集合，如何确定其答案。

假设该可重集合的元素从小到大分别为 $a_1, a_2, \cdots, a_{\lvert s \rvert}$，并将元素按顺序加入一个集合 $S$。记录一个变量 $ans$ 代表目前不能被 $S$ 中若干元素求和表示的最小数，当 $S$ 为空时，$ans = 1$。此时，如果向 $S$ 中加入一个元素 $a_i$，如果 $a_i \in [1, ans]$，那么 $ans$ 会变为 $ans + a_i$，否则 $ans$ 不会有变化。

如果 $a_i \gt ans$，则显然数 $ans$ 依然无法被表示；否则，对于 $[1, a_i - 1]$ 的元素按照原样表示，对于 $[a_i, ans + a_i - 1]$（其中 $ans$ 为修改之前的 $ans$）的数，则可以拆分为 $a_i + x$，其中 $x \in [1, ans - 1]$，可以被之前的元素求和表示。

由于每次加入数据时，加入的数必然大于上一次的答案，因此如果可以加入新树，加入完成之后的答案至少大于原答案的两倍。这也就意味着，对于任意一个元素 $a_i$，如果最终可以被加入集合，则之多需要 $\mathcal O(\log a_i)$ 次就会被加入，故单次查询操作的次数为 $\mathcal O(\log(\max \{ a_i \} ))$。

    for (int i = 1; i <= m; i++) {
        std::cin >> l >> r;
        ans = 1;
        lst = 0;
        while (true) {
            res = SGT.Query(SGT.root[l - 1], SGT.root[r], lst + 1, ans);
            lst = ans;
            if (res) ans = ans + res;
            else break;
        }
        std::cout << ans << '\n';
    }

树状数组套权值线段树

例3：P3380 【模板】二逼平衡树（树套树）

如果本题去掉修改操作，则显然可以使用可持久化权值线段树进行维护。又由于可持久化权值线段树可以类比为权值树的前缀和，可以考虑采用类似于维护动态前缀和的方式来维护本题。而对动态前缀和的维护，最简单的方法即为树状数组（或线段树）。

在这里，可以考虑采用嵌套的形式，将权值树作为整体，用树状数组或是线段树对其进行维护。由于权值树同时满足可合并性、可减性和交换律，因此这样的维护是可行的。

以树状数组为例，对序列的每一个位置开一个权值树，然后用树状数组进行维护。每次操作先跑一遍树状数组处理出这次操作涉及到那几棵树，然后直接进行权值树的查询即可。

typedef std::vector<int> svi;

struct BinaryIndexedTree {
    struct SegmentTree {
        struct Node {
            int l, r;
            int lson;
            int rson;
            int val;
        } node[maxN * logN * logN + 10];

        int ncnt;
        int root[maxN + 10];

        void PushUp(int u) {
            node[u].val = node[node[u].lson].val + node[node[u].rson].val;
            return;
        }

        void Build(int &u) {
            u = ++ncnt;
            return;
        }

        void Clone(int &u, int v) {
            u = ++ncnt;
            node[u] = node[v];
            return;
        }

        void Modify(int &u, int l, int r, int pos, int val) {
            if (u == 0) Build(u);
            if (l == r) {
                node[u].val += val;
                return;
            }
            int mid = (l + r) / 2;
            if (pos <= mid) Modify(node[u].lson, l, mid, pos, val);
            else Modify(node[u].rson, mid + 1, r, pos, val);
            PushUp(u);
            return;
        }

        int QueryRank(svi u, svi v, int l, int r, int k) {
            if (l == r) return 0;
            int mid = (l + r) / 2;
            int cnt = 0;
            if (k <= mid) {
                if (u.size()) for (int i = 0; i < u.size(); i++) u[i] = node[u[i]].lson;
                if (v.size()) for (int i = 0; i < v.size(); i++) v[i] = node[v[i]].lson;
                return QueryRank(u, v, l, mid, k);
            } else {
                if (u.size()) for (int i = 0; i < u.size(); i++) cnt -= node[node[u[i]].lson].val;
                if (v.size()) for (int i = 0; i < v.size(); i++) cnt += node[node[v[i]].lson].val;
                if (u.size()) for (int i = 0; i < u.size(); i++) u[i] = node[u[i]].rson;
                if (v.size()) for (int i = 0; i < v.size(); i++) v[i] = node[v[i]].rson;
                return cnt + QueryRank(u, v, mid + 1, r, k);
            }
        }

        int QueryKth(svi u, svi v, int l, int r, int k) {
            if (l == r) return l;
            int mid = (l + r) / 2;
            int cnt = 0;
            for (int i = 0; i < u.size(); i++) cnt -= node[node[u[i]].lson].val;
            for (int i = 0; i < v.size(); i++) cnt += node[node[v[i]].lson].val;
            if (k <= cnt) {
                for (int i = 0; i < u.size(); i++) u[i] = node[u[i]].lson;
                for (int i = 0; i < v.size(); i++) v[i] = node[v[i]].lson;
                return QueryKth(u, v, l, mid, k);
            } else {
                for (int i = 0; i < u.size(); i++) u[i] = node[u[i]].rson;
                for (int i = 0; i < v.size(); i++) v[i] = node[v[i]].rson;
                return QueryKth(u, v, mid + 1, r, k - cnt);
            }
        }
    } SGT;

    int LowBit(int val) {
        return val & -val;
    }

    void Add(int pos, int val) {
        for (int i = pos; i <= n; i += LowBit(i)) {
            SGT.Modify(SGT.root[i], 1, range.size() - 2, a[pos], val);
        }
        return;
    }

    int AskRank(int l, int r, int k) {
        svi u;
        svi v;
        l -= 1;
        while (l) {
            u.push_back(SGT.root[l]);
            l -= LowBit(l);
        }
        while (r) {
            v.push_back(SGT.root[r]);
            r -= LowBit(r);
        }
        return SGT.QueryRank(u, v, 1, tot, k) + 1;
    }

    int AskKth(int l, int r, int k) {
        svi u;
        svi v;
        l -= 1;
        while (l) {
            u.push_back(SGT.root[l]);
            l -= LowBit(l);
        }
        while (r) {
            v.push_back(SGT.root[r]);
            r -= LowBit(r);
        }
        return SGT.QueryKth(u, v, 1, tot, k);
    }

    int AskPre(int l, int r, int k) {
        int rank = AskRank(l, r, k);
        if (rank == 1) return 0;
        return AskKth(l, r, rank - 1);
    }

    int AskSuf(int l, int r, int k) {
        if (k >= range.size() - 1) return tot + 1;
        int rank = AskRank(l, r, k + 1);
        if (rank > r - l + 1) return tot + 1
        return AskKth(l, r, rank);
    }
} BIT;

例4：P3810 【模板】三维偏序（陌上花开）

首先介绍离线算法和在线算法的相关概念。离线算法，即在使用核心算法处理数据前，便已经获得所有的输入数据。本题在开始算法之前已经直接得到了所有元素的所有属性，故可以采用离线算法。离散化就是一种典型的离线算法，因为需要获得所有的数据后才可以将这些数据排序。

与离线算法对应的是在线算法，即在算法开始前不知道所有的输入数据，需要动态处理。在算法竞赛中，有部分题目的输入数据与上一次询问的结果有关，此类题目会要求选手必须使用在线算法完成问题，要求会比离线问题更高。

考虑将问题简化为两个属性（设为 $A, B$）的时候该如何解决。一种简单的方式是，使用离线算法，先按照 $A$ 属性进行排序并按顺序遍历，再用权值线段树对前 $i$ 个元素中的 $B$ 属性进行维护。当插入一个元素时，只要在权值线段树中查找 $B$ 属性小于等于该元素的元素个数，并统计总数即可。当属性个数达到三个时，依然先按照某一元素进行排序，从而将需要考虑的属性减少至两个。

使用树状数组套线段树解决这个问题。在对 $A$ 属性进行排序后，依次遍历所有元素，用外层树状数组维护 $B$ 属性，用内层的线段树维护 $C$ 属性。例如对于一个 $B$ 属性为 $b$，$C$ 属性为 $c$ 的元素，在 $b$ 在树状数组上对应的所有权值树的 $c$ 位置插入一个元素即可。

当遍历到某一元素时，先查询目前已遍历到元素中 $B, C$ 两个属性逗比当前元素属性小的元素个数。若当前元素 $B$ 属性为 $b$，$C$ 属性为 $c$，则等价于查询第 $1$ 到 $b$ 棵树中值域在 $[1, c]$ 值域内到数并统计答案。在完成查询后，将元素插入到树套树中，并按顺序遍历下一元素。

struct Element {
    int a, b, c;
    int id;

    bool operator<(const Element &other) const {
        if (a != other.a) return a < other.a;
        if (b != other.b) return b < other.b;
        return c < other.c;
    }
} e[maxN + 10];

struct BinaryIndexedTree {
    struct SegmentTree {
        struct Node {
            int lson;
            int rson;
            int value;
        } node[maxK * logK * logN + 10];

        int ncnt;
        int root[maxK + 10];

        void PushUp(int u) {
            node[u].value = node[node[u].lson].value + node[node[u].rson].value;
            return;
        }

        void Build(int &u) {
            u = ++ncnt;
            return;
        }

        void Modify(int &u, int l, int r, int weight, int value) {
            if (!u) Build(u);
            if (l == r) {
                node[u].value += value;
                return;
            }
            int mid = (l + r) / 2;
            if (weight <= mid) Modify(node[u].lson, l, mid, weight, value);
            else Modify(node[u].rson, mid + 1, r, weight, value);
            PushUp(u);
            return;
        }

        int Query(int u, int l, int r, int weight) {
            if (l == r) return node[u].value;
            int mid = (l + r) / 2;
            if (weight <= mid) return Query(node[u].lson, l, mid, weight);
            else return node[node[u].lson].value + Query(node[u].rson, mid + 1, r, weight);
        }
    } SGT;

    int lowbit(int x) {
        return x & -x;
    }

    void Add(int pos, int weight, int value) {
        for (int i = pos; i <= k; i += lowbit(i)) {
            SGT.Modify(SGT.root[i], 1, k, weight, value);
        }
        return;
    }

    int Ask(int pos, int weight) {
        int ret = 0;
        for (int i = pos; i > 0; i -= lowbit(i)) {
            ret += SGT.Query(SGT.root[i], 1, k, weight);
        }
        return ret;
    }
} BIT;

    std::sort(e + 1, e + n + 1);
    int i = 1;
    int j;
    while (i <= n) {
        j = i;
        while (e[i].a == e[j].a) BIT.Add(e[j].b, e[j].c, 1), j++;
        j = i;
        while (e[i].a == e[j].a) f[e[j].id] = BIT.Ask(e[j].b, e[j].c), j++;
        i = j;
    }
    for (int i = 1; i <= n; i++) d[f[i]]++;
    for (int i = 1; i <= n; i++) std::cout << d[i] << '\n';