线段树动态开点详解

线段树是一种用于处理区间问题的数据结构，其应用非常广泛。但在实际应用过程中，线段树的空间复杂度往往是固定的，而事实上，我们并不总是需要处理整个区间，这样就导致了空间浪费。动态开点线段树就是为了解决这个问题而诞生的。本文将从多个方面对线段树动态开点做详细的阐述。

一、读入数据

为了实现动态开点，首先需要我们先读入数据。一个线段树最大的叶子结点编号为n，如果我们已知了需要处理区间的右端点r，那么这棵线段树空间就可以直接开到2n。但是如果我们不知道r的值，线段树的空间就不能提前开到2n，否则就会造成空间浪费。正确的做法是使用动态开点技术，根据需要动态的开启和关闭每一个节点，这样就可以避免空间浪费了。

下面是读入数据的代码示例：

struct SegmentTree {
    int l, r, sum; // sum 表示该区间内元素的和
    int lt, rt; //左右儿子的编号
    #define lson tr[u].lt
    #define rson tr[u].rt
} tr[MAXN*40]; //开到足够大的数量

int n, m, idx; //idx 表示当前空闲结点编号
int root[MAXN]; // root[i] 表示以第 i 个数为右端点建立的线段树的根节点

void build(int u, int l, int r) {
    if(l == r) return; //到达叶节点，返回
    int mid = (l + r) >> 1;
    lson = ++idx; // 左儿子编号为 idx + 1，并将 idx 加 1
    rson = ++idx; // 右儿子编号为 idx + 2，并将 idx 再次加 1
    build(lson, l, mid);
    build(rson, mid + 1, r);
}

int modify(int u, int l, int r, int x, int k) {
    int p = ++idx; // 开启新的结点 p
    tr[p] = tr[u]; // 复制原节点的内容
    if(l == r) {
        tr[p].sum += k; // 到达叶子结点，直接修改数据
        return p;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) tr[p].lt = modify(lson, l, mid, x, k);
    else tr[p].rt = modify(rson, mid + 1, r, x, k);
    tr[p].sum = tr[tr[p].lt].sum + tr[tr[p].rt].sum;
    return p;
}

二、动态开点线段树区间修改

在线段树上做区间修改的时候，我们需要先找到要修改的区间的左右端点，然后不断递归地向下处理，直到到达叶子节点，最后再递归回来更新每个节点的信息。由于我们使用了动态开点技术，所以在遍历的时候，我们不能像普通线段树一样通过左右儿子的编号访问它们，而是需要使用动态开点得到它们的实际编号。

下面是区间修改的代码示例：

void modify(int p, int u, int l, int r, int ql, int qr, int k) {
    if(ql <= l && qr >= r) { // 区间在当前区间内
        tr[p].sum += k * (r - l + 1);
        tr[p].tag += k; // 标记 one
        return;
    }
    int mid = (l + r) >> 1;
    if(ql <= mid) {
        if(!tr[u].lt) tr[u].lt = ++idx; // 左儿子第一次被访问时才开点
        modify(p << 1, tr[u].lt, l, mid, ql, qr, k);
    }
    if(qr > mid) {
        if(!tr[u].rt) tr[u].rt = ++idx; // 右儿子第一次被访问时才开点
        modify(p << 1 | 1, tr[u].rt, mid + 1, r, ql, qr, k);
    }
    tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum + tr[u].tag * (r - l + 1); //更新信息
}

三、动态线段树选取相关特殊操作

动态开点线段树有一些特殊操作和普通线段树不同，它们可以提高我们求解某些问题的效率。下面介绍一些比较常见的操作：

1. 求区间某个位置的值

在普通线段树中，我们可以很轻松地求区间 [l, r] 中的最大值或最小值，但是如果要求区间内任意一个位置 i 的值时，就需要使用另外一种方法了。我们可以用一个数组 id 保存每个节点对应的区间范围，然后根据查询的位置不断递归向下至叶子结点。如图3-1所示。

下面是查询区间某个位置的代码示例：

int query(int p, int u, int l, int r, int x) {
    if(l == r) return tr[p].sum; // 已经到达叶节点
    int mid = (l + r) >> 1;
    if(x <= mid) {
        if(!tr[u].lt) tr[u].lt = ++idx; // 左儿子第一次被访问时才开点
        return query(p << 1, tr[u].lt, l, mid, x) + tr[p].tag * (x - l + 1);
    }
    else {
        if(!tr[u].rt) tr[u].rt = ++idx; // 右儿子第一次被访问时才开点
        return query(p << 1 | 1, tr[u].rt, mid + 1, r, x) + tr[p].tag * (r - x + 1);
    }
}

2. 求区间 [r-i+1, r] 任意数的和

在维护一段数列区间的前缀和时，我们可以直接使用线段树来维护前缀和。但是，在动态开点线段树中，如果要求区间 [r-i+1, r] 中任意数的和时，我们可以使用数据结构“主席树”来维护。

下面是求区间 [r-i+1, r] 任意数的和的代码示例：

void modify(int p, int u, int l, int r, int x, int k) {
    tr[p].sum += k;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) { // 修改左儿子的值
        if(!tr[u].lt) tr[u].lt = ++idx; // 左儿子第一次被访问时才开点
        modify(p << 1, tr[u].lt, l, mid, x, k);
    }
    else { // 修改右儿子的值
        if(!tr[u].rt) tr[u].rt = ++idx; // 右儿子第一次被访问时才开点
        modify(p << 1 | 1, tr[u].rt, mid + 1, r, x, k);
    }
}

int query(int p, int ul, int ur, int l, int r, int k) {
    if(l == r) return l;
    int cnt = tr[tr[p << 1 | 1].lt].sum - tr[tr[p << 1].lt].sum; // 右儿子区间内的数量
    int mid = (l + r) >> 1;
    if(cnt >= k) return query(p << 1 | 1, tr[ul].rt, tr[ur].rt, mid + 1, r, k);
    else return query(p << 1, tr[ul].lt, tr[ur].lt, l, mid, k - cnt);
    // 在左儿子中查找
}

3. 求区间第 k 大/小的数

求解区间第 k 大/小的数，可以用上面的“主席树”来解决。我们可以对每个节点开一个小根堆，记录着区间内所有数字，然后就用主席树的方法求解区间第 k 大/小的数。

下面是查询区间第 k 大/小的代码示例：

void pushup(int u) {
    tr[u].sum = tr[tr[u].lt].sum + tr[tr[u].rt].sum;
}
void modify(int p, int u, int l, int r, int x, int k) {
    tr[p].st.push(k); //将当前数加入小根堆中
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) {
        if(!tr[u].lt) tr[u].lt = ++idx; // 左儿子第一次被访问时才开点
        modify(p << 1, tr[u].lt, l, mid, x, k);
    }
    else {
        if(!tr[u].rt) tr[u].rt = ++idx; // 右儿子第一次被访问时才开点
        modify(p << 1 | 1, tr[u].rt, mid + 1, r, x, k);
    }
    pushup(u);
}

int query(int p, int ul, int ur, int l, int r, int k) {
    if(l == r) return l;
    int cnt = 0;
    //找出区间 [ul, ur] 中包含的数的个数
    for(int i = 0; i < tr[tr[p << 1].rt].st.size(); i++)
        if(tr[tr[p << 1].rt].st.top() <= r && tr[tr[p << 1].rt].st.top() >= l) cnt++;
    int mid = (l + r) >> 1;
    if(cnt >= k) return query(p << 1, tr[ul].lt, tr[ur].lt, l, mid, k);
    else return query(p << 1 | 1, tr[ul].rt, tr[ur].rt, mid + 1, r, k - cnt);
}

总结

动态开点线段树是一种非常实用的数据结构，其空间利用率非常高，能够满足很多实际问题的需求。在实现过程中，需要认真分析问题，考虑到各种特殊情况，才能写出优秀的代码，提高算法效率。