C++高级数据结构之线段树

C++高级数据结构之线段树攻略

什么是线段树

线段树是一种数据结构，它可以支持区间查询和单点修改，是处理静态区间问题的常用手段。它利用了 二分思想，将区间离散化成一些个体，然后考虑对个体进行处理，再结合区间合并的特性，更新区间信息。线段树主要由四个操作构成：建树、单点修改、区间查询和区间修改。

线段树的数据表示

在实现线段树时，我们需要考虑数据结构的几个要素：存储方式、数据的存储结构、具体实现方式等。在最常见的线段树实现中，通常将读入的区间离散化后，使用数组保存区间信息。线段树的构造是在递归过程中完成的。每次将当前区间分成两部分，构造左右子树，最后将区间的统计信息合并到父节点，然后返回。

下面是一个典型线段树节点的结构：

struct Node{
    int l; // 区间左端点
    int r; // 区间右端点
    int sum; // 区间和
}node[maxn<<2]; // 线段树数组，开4倍空间

其中 l 和 r 分别记录节点的左右端点，sum 表示区间和。

线段树的操作

建树

下面是线段树的建树过程，基本思想是对于当前区间，取区间中间位置为节点，然后将当前区间分成左右两部分分别构造其左右子树。

void build(int p, int l, int r){
    node[p].l = l;
    node[p].r = r;
    if(l == r){
        scanf("%d", &node[p].sum);
        return;
    }
    int mid = (l + r) >> 1; 
    build(p<<1, l, mid); // 左子树
    build(p<<1|1, mid+1, r); // 右子树
    node[p].sum = node[p<<1].sum + node[p<<1|1].sum; // 合并信息
}

单点修改

单点修改操作即为更改线段树某个节点的区间信息。单点修改只会影响一个节点，因此是一种很轻量的操作。具体操作就是从根节点开始，依次进入左右子树，直至遇到叶节点，然后进行更新。

void update(int p, int x, int k){
    if(node[p].l == x && node[p].r == x){
        node[p].sum += k;
        return;
    }
    int mid = (node[p].l + node[p].r) >> 1;
    if(x <= mid) update(p<<1, x, k); // 左子树
    else update(p<<1|1, x, k); // 右子树
    node[p].sum = node[p<<1].sum + node[p<<1|1].sum; // 合并信息
}

区间查询

区间查询即为查询线段树某个区间的信息。具体操作同样是从根节点开始，依次进入左右子树，直至遇到区间完全包含目标区间或者与目标区间相离的区间，然后将得到的信息合并。

int query(int p, int l, int r){
    if(node[p].l == l && node[p].r == r)
        return node[p].sum;
    int mid = (node[p].l + node[p].r) >> 1;
    if(r <= mid) return query(p<<1, l, r); // 左子树
    else if(l > mid) return query(p<<1|1, l, r); // 右子树
    else return query(p<<1, l, mid) + query(p<<1|1, mid+1, r); // 遇到分歧，分别查询左右子树
}

区间修改

区间修改将修改线段树某个区间内的节点信息。具体操作同样是从根节点开始，递归执行左右子树的修改，最后将修改后的子树信息合并。

void modify(int p, int l, int r, int k){
    if(node[p].l >= l && node[p].r <= r){
        node[p].sum += k;
        return;
    }
    int mid = (node[p].l + node[p].r) >> 1;
    if(l <= mid) modify(p<<1, l, r, k); // 左子树
    if(r > mid) modify(p<<1|1, l, r, k); // 右子树
    node[p].sum = node[p<<1].sum + node[p<<1|1].sum; // 合并信息
}

示例

示例一

题目描述：https://www.acwing.com/problem/content/description/802/
题目解答：https://www.acwing.com/solution/content/50632/

该题要求维护区间元素的和，并对某个区间元素加上一个值。下面是该题的代码实现，其中 n 表示待维护区间长度。

void build(int p, int l, int r){
    node[p].l = l;
    node[p].r = r;
    if(l == r){
        scanf("%lld", &node[p].sum);
        return;
    }
    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid+1, r);
    node[p].sum = node[p<<1].sum + node[p<<1|1].sum;
}

void modify(int p, int x, int k){
    if(node[p].l == x && node[p].r == x){
        node[p].sum += k;
        return;
    }
    int mid = (node[p].l + node[p].r) >> 1;
    if(x <= mid) modify(p<<1, x, k);
    else modify(p<<1|1, x, k);
    node[p].sum = node[p<<1].sum + node[p<<1|1].sum;
}

ll query(int p, int l, int r){
    if(node[p].l == l && node[p].r == r)
        return node[p].sum;
    int mid = (node[p].l + node[p].r) >> 1;
    if(r <= mid) return query(p<<1, l, r);
    else if(l > mid) return query(p<<1|1, l, r);
    else return query(p<<1, l, mid) + query(p<<1|1, mid+1, r);
}

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    for(int i = 0; i < m; ++i){
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if(opt == 1) modify(1, x, y);
        else printf("%lld\n", query(1, x, y));
    }
    return 0;
}

示例二

题目描述：https://www.acwing.com/problem/content/1073/
题目解答：https://www.acwing.com/solution/content/39389/

该题要求维护区间最大值，并对某个元素进行单点修改。代码实现如下，其中 n 表示待维护区间长度。

void build(int p, int l, int r){
    node[p].l = l;
    node[p].r = r;
    if(l == r){
        scanf("%d", &node[p].sum);
        return;
    }
    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid+1, r);
    node[p].sum = max(node[p<<1].sum, node[p<<1|1].sum);
}

void update(int p, int x, int k){
    if(node[p].l == x && node[p].r == x){
        node[p].sum = k;
        return;
    }
    int mid = (node[p].l + node[p].r) >> 1;
    if(x <= mid) update(p<<1, x, k);
    else update(p<<1|1, x, k);
    node[p].sum = max(node[p<<1].sum, node[p<<1|1].sum);
}

int query(int p, int l, int r){
    if(node[p].l == l && node[p].r == r)
        return node[p].sum;
    int mid = (node[p].l + node[p].r) >> 1;
    if(r <= mid) return query(p<<1, l, r);
    else if(l > mid) return query(p<<1|1, l, r);
    else return max(query(p<<1, l, mid), query(p<<1|1, mid+1, r));
}

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    for(int i = 0; i < m; ++i){
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if(opt == 1) update(1, x, y);
        else printf("%d\n", query(1, x, y));
    }
    return 0;
}

总结

线段树是一种非常常用的数据结构，可以高效地解决静态区间查询问题。它具有以下特点：

• 可以支持区间查询、单点修改、区间修改等操作；
• 基于二分思想，将区间离散化，实现节点合并；
• 可以高效地支持大规模数据处理，常被用于OI竞赛和工程实现。

同时线段树也存在一些注意事项，下面进行总结：

• 在某些情况下，线段树需要懒标记来实现区间修改，以避免重复修改的问题；
• 线段树的空间复杂度为 $O(n\log n)$，对于卡空间的情况需要注意；
• 在线段树实现过程中，要注意数组越界的问题，保证程序的稳定运行。