树形结构

C++ 算法 数据结构
数据结构与算法
发布日期:   2023-08-09
更新日期:   2023-09-11
文章字数:   3.5k
阅读时长:   15 分
阅读次数:  

树形结构

字典树

字典树虽然是树形结构，但因为其主要用于前缀匹配和前缀查询，故将字典树归类到《字符串》专题，这里不再赘述。可以前往《字符串》专题查看字典树相关内容。

线段树

线段树1

线段树（Segment Tree），也叫区间树，用于进行区间查询，单点查询，区间修改和单点修改。与差分数组不同的是，差分数组只能支持离线的区间修改，即差分数组只能修改完后再查询，查询是一次性的。而线段树却可以做到在线的区间、单点修改与查询，并且都可以在O（logn）的时间复杂度之内完成，是一个非常优秀的数据结构。

线段树属于二叉搜索树，假设有一个数组S = {$v_1$，$v_2$，$v_3$，……，$v_n$}，对于线段树来讲，其根节点维护的是区间[1，n]的元素和；而对其左儿子来讲，其维护的是区间[1，$\frac{n+1}{2}$]的元素和；而对其右儿子来讲，其维护的是区间[$\frac{n+1}{2}+1$，n]的元素和，并以此类推。更普遍地讲，对于线段树的一个节点，若其维护的是区间[l，r]的元素和，则其左儿子维护了区间[l，$\frac{l+r}{2}$]的元素和，右儿子维护了区间[$\frac{l+r}{2}+1$，r]的元素和。

因为线段树属于二叉树的这个特性，我们考虑到一种树结构叫做完全二叉树，在完全二叉树中，我们对顶点进行顺序编号，使得完全二叉树的父子节点的编号具有一定的规律。同理，线段树虽说并不是一棵完全二叉树，但是我们可以利用完全二叉树对结点的编号思想对线段树进行编号，这样我们就可以利用数组来模拟树结构了。我们规定，对于线段树，若将其中任意一个顶点标记为 t，则其父节点的编号为$\frac{t}{2}$，其左儿子编号为 2t，右儿子编号为 2t + 1。

线段树的区间修改的时间复杂度是O（logn），假设我们现在要对某个区间的所有元素加上v，我们只需要从根节点开始，往下遍历，找到包含该区间或者和该区间相关的顶点，进行值的修改即可。为了减少操作次数，假设我们现在有一个[1，5]的区间，现在要对区间[1，3]的全部元素加v，我们遍历到根节点的左儿子[1，3]，对其维护的区间和加上 区间长度*v（即3v），接下来便直接返回即可，就没必要更新其子节点的元素值了，可以在一定程度上减少操作次数。但是，这又会引来一个问题，就是假设下一次的区间修改需要用到[1，3]的子节点元素值，可其子节点的元素值在上一次区间修改中并没有更新，这又该怎么办？

这个时候，延迟标记（lazy标记）就派上用场了，它代表着我们对这个区间进行修改的数值，同时，打上了 lazy 标记的节点也意味着其子节点在某次区间更新中并没有被更新元素值。这样，当我们需要用到被打上 lazy 标记的节点的子节点时，我们肯定会遍历到这个带有 lazy 标记的节点本身。这样一来，当我们碰上了 lazy 标记的时候，我们在向下遍历子节点时，便可以将 lazy 标记下传，修改对应子节点的元素值。

而对于区间最值，我们可以模仿区间求和的方式，进行递归查询即可。

接下来便是线段树1的模板：

const int maxn = 5e5 + 5;
struct node {    //线段树节点
    long long l, r;    //左边界，右边界
    long long lazy, sum;    //延迟标记，该节点维护的区间的总和
    long long maxNum, minNum;   //区间最大值，最小值
};
node tree[maxn * 4];    //线段树，开4倍的节点空间
int a[maxn];    //原始数组
int n, m, oper, x, y, k;
void up(int id) {   //回溯更新数据
    tree[id].sum = tree[id * 2].sum + tree[id * 2 + 1].sum; //求当前节点所维护的区间总和
    tree[id].maxNum = max(tree[id * 2].maxNum, tree[id * 2 + 1].maxNum);    //更新区间最大值
    tree[id].minNum = min(tree[id * 2].minNum, tree[id * 2 + 1].minNum);    //更新区间最小值
}
void build(int id, int l, int r) {    //建树
    tree[id].l = l, tree[id].r = r;    //当前顶点维护的区间左右边界
    tree[id].lazy = 0;    //lazy标记默认为0
    if (l == r) {    //当这个顶点维护的是单个点的元素值时，更新区间和以及最值
        tree[id].sum = tree[id].minNum = tree[id].maxNum = a[l];
        return;
    }
    int mid = l + (r - l) / 2;    //二分区间
    build(id * 2, l, mid);    //递归建左区间
    build(id * 2 + 1, mid + 1, r);    //递归建右区间
    up(id); //回溯更新数据
}
void down(int id) {    //下传lazy标记
    //lazy标记下传到左儿子
    tree[id * 2].lazy += tree[id].lazy;    
    tree[id * 2].minNum += tree[id].lazy, tree[id * 2].maxNum += tree[id].lazy; //更新左儿子最值
    tree[id * 2].sum += (tree[id * 2].r - tree[id * 2].l + 1) * tree[id].lazy;    //更新左儿子的元素值

    //lazy标记下传到右儿子
    tree[id * 2 + 1].lazy += tree[id].lazy;    
    tree[id * 2 + 1].minNum += tree[id].lazy, tree[id * 2 + 1].maxNum += tree[id].lazy; //更新右儿子最值
    tree[id * 2 + 1].sum += (tree[id * 2 + 1].r - tree[id * 2 + 1].l + 1) * tree[id].lazy;    //更新右儿子的元素值

    tree[id].lazy = 0;    //当前节点的lazy标记已下传，重置为0
}
void update(int id, int l, int r, int v) {    //将区间 [l，r] 所有元素加上v
    if (tree[id].l > r || tree[id].r < l) return;    //顶点维护的区间与 [l，r] 相离，不需要操作
    if (tree[id].l >= l && tree[id].r <= r) {    //顶点维护的区间包含在在 [l，r] 之中
        tree[id].lazy += v;    //添加lazy标记
        tree[id].minNum += v, tree[id].maxNum += v;   //更新最值
        tree[id].sum += (tree[id].r - tree[id].l + 1) * v;        //更新元素值
        return;    //减少操作次数，打上lazy标记之后不需要对子节点进行修改
    }
    if (tree[id].lazy > 0) down(id);    //如果当前节点带上lazy标记，则下传其lazy标记
    update(id * 2, l, r, v);    //递归修改左儿子
    update(id * 2 + 1, l, r, v);    //递归修改右儿子
    up(id); //回溯更新数据
}
long long query_sum(int id, int l, int r) {    //查询 [l，r] 的区间和
    if (tree[id].l > r || tree[id].r < l) return 0;    //顶点维护的区间与 [l，r] 相离，不需要操作
    if (tree[id].l >= l && tree[id].r <= r) return tree[id].sum;    //顶点维护的区间包含在 [l，r] 之中，将其维护的区间和算入总和中
    if (tree[id].lazy > 0) down(id);    //碰上lazy标记，下传lazy标记
    return query_sum(id * 2, l, r) + query_sum(id * 2 + 1, l, r);    //递归查询左儿子和右儿子
}
long long query_max(int id, int l, int r) { //查询 [l，r] 的区间最大值
    if (tree[id].l > r || tree[id].r < l) return 0; //顶点维护的区间与 [l，r]相离，返回0或者-INF（根据题意来）
    if (tree[id].l >= l && tree[id].r <= r) return tree[id].maxNum; //顶点维护的区间包含在 [l，r]之中，返回区间最大值
    if (tree[id].lazy > 0) down(id);    //碰上lazy标记，下传lazy标记
    return max(query_max(id * 2, l, r), query_max(id * 2 + 1, l, r));   //递归取左儿子和右儿子最值的较大值
}  
long long query_min(int id, int l, int r) { //查询 {l，r] 的区间最小值
    if (tree[id].l > r || tree[id].r < l) return 0x3f3f3f3f3f3f3f3f; //顶点维护的区间与 [l，r]相离，返回INF（根据题意来）
    if (tree[id].l >= l && tree[id].r <= r) return tree[id].minNum; //顶点维护的区间包含在 [l，r]之中，返回区间最小值
    if (tree[id].lazy > 0) down(id);    //碰上lazy标记，下传lazy标记
    return min(query_min(id * 2, l, r), query_min(id * 2 + 1, l, r));   //递归取左儿子和右儿子最值的较小值
}

线段树2

该线段树需要满足下列三种操作：

  • 将某区间的每一个数乘上x

  • 将某区间的每一个数加上x

  • 求出某区间每一个数的和，并取模于mod

该线段树新增了乘法操作，一般的 lazy 标记已经不能满足要求了，所以我们需要新增一个 lazy 标记来对乘法进行判断。在这里，我们利用 lazy_add 来判断加法，利用 lazy_mul 来判断乘法。

考虑到这个线段树需要维护加法和乘法，所以我们还需要额外考虑在down函数中下传 lazy 标记时 lazy_add 和 lazy_mul 的下传顺序。回忆线段树1的下传操作：

void down(int id) {    //下传lazy标记
    tree[id * 2].lazy += tree[id].lazy;    //lazy标记下传到左儿子
    tree[id * 2].sum += (tree[id * 2].r - tree[id * 2].l + 1) * tree[id].lazy;    //更新左儿子的元素值
    tree[id * 2 + 1].lazy += tree[id].lazy;    //lazy标记下传到右儿子
    tree[id * 2 + 1].sum += (tree[id * 2 + 1].r - tree[id * 2 + 1].l + 1) * tree[id].lazy;    //更新右儿子的元素值
    tree[id].lazy = 0;    //当前节点的lazy标记已下传，重置为0
}

可以看出，儿子节点的 lazy 标记继承了父节点的 lazy 标记。对于乘法标记的继承，因为乘法优先级高，故儿子节点的乘法标记直接继承父亲的乘法标记，即：儿子节点新乘法标记 = 儿子节点旧乘法标记 x 父亲节点乘法标记（必要时可以加入取模运算）。而对于加法标记，其处理需要多注意一步，我们假设该节点的父亲节点的乘法标记不为默认值，即父亲节点乘法标记不为1，代表父亲在这之前做过一次乘法修改，更进一步说，儿子节点需要先修改乘法值，代表着这个乘法标记会影响到儿子节点的加法标记的修改（或者这么理解：打一个简单的比方，假设儿子节点维护的区间和为sum，儿子节点的加法标记 n 意为 $sum+n$，而父亲节点的乘法标记m意为 $(sum+n)m$，而父亲节点的加法标记 x 意为$(sum+n)m+x$，故对于儿子节点的区间和，实则为$sum\cdot m+nm+x$，故对于儿子节点而言，乘法标记应为m，加法标记应为 $nm+x$），故得到：儿子节点新加法标记 = 儿子节点旧加法标记 x 父亲节点乘法标记 + 父亲节点加法标记（必要时可以加入取模运算）。

搞清楚这个问题之后，剩下的该线段树的代码就很简单了，基本上和线段树1没有什么太大差别。

上代码：

洛谷P3373

#include<iostream>
using namespace std;
const int maxn = 1e5 + 5;
struct node {
    long long l, r;    //左边界，右边界
    long long lazy_add, lazy_mul, sum;    //加法、乘法延迟标记，区间和
};
node tree[maxn * 4];
int n, mod, q, num[maxn], oper, x, y, k;    //n个数，模数，操作次数，原始数组，操作命令
void build(int id, int l, int r) {    //建树
    tree[id].l = l, tree[id].r = r;
    tree[id].lazy_add = 0, tree[id].lazy_mul = 1;
    if (l == r) {
        tree[id].sum = num[l]%mod;    //注意取模运算
        return;
    }
    int mid = l + (r - l) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    tree[id].sum = (tree[id * 2].sum + tree[id * 2 + 1].sum) % mod;
}
void down(int id) {    //标记下传
    //标记下传到左儿子
    tree[id * 2].lazy_add = (tree[id * 2].lazy_add * tree[id].lazy_mul + tree[id].lazy_add) % mod;
    tree[id * 2].lazy_mul = (tree[id * 2].lazy_mul * tree[id].lazy_mul) % mod;
    tree[id * 2].sum = (tree[id * 2].sum * tree[id].lazy_mul + tree[id].lazy_add * (tree[id * 2].r - tree[id * 2].l + 1)) % mod;

    //标记下传到右儿子
    tree[id * 2+1].lazy_add = (tree[id * 2+1].lazy_add * tree[id].lazy_mul + tree[id].lazy_add) % mod;
    tree[id * 2+1].lazy_mul = (tree[id * 2+1].lazy_mul * tree[id].lazy_mul) % mod;
    tree[id * 2 + 1].sum = (tree[id * 2 + 1].sum * tree[id].lazy_mul + tree[id].lazy_add * (tree[id * 2 + 1].r - tree[id * 2 + 1].l + 1)) % mod;

    //父亲节点标记下传完成，恢复到默认值
    tree[id].lazy_add = 0, tree[id].lazy_mul = 1;
}
void update_add(int id, int l, int r, int v) {    //区间加法
    if (tree[id].l > r || tree[id].r < l) return;
    if (tree[id].l >= l && tree[id].r <= r) {
        tree[id].lazy_add = (tree[id].lazy_add + v) % mod;
        tree[id].sum = (tree[id].sum + (tree[id].r - tree[id].l + 1) * v) % mod;
        return;
    }
    down(id);
    update_add(id * 2, l, r, v);
    update_add(id * 2 + 1, l, r, v);
    tree[id].sum = (tree[id * 2].sum+tree[id*2+1].sum) % mod;
}
void update_mul(int id, int l, int r, int v) {    //区间乘法
    if (tree[id].l > r || tree[id].r < l) return;
    if (tree[id].l >= l && tree[id].r <= r) {
        tree[id].lazy_add = (tree[id].lazy_add * v) % mod;    //区间乘法的lazy标记修改需要额外再修改一次加法标记
        tree[id].lazy_mul = (tree[id].lazy_mul * v) % mod;
        tree[id].sum = (tree[id].sum * v) % mod;
        return;
    }
    down(id);
    update_mul(id * 2, l, r, v);
    update_mul(id * 2 + 1, l, r, v);
    tree[id].sum = (tree[id * 2].sum + tree[id * 2 + 1].sum) % mod;
}
long long query(int id, int l, int r) {    //区间查询
    if (tree[id].l > r || tree[id].r < l) return 0;
    if (tree[id].l >= l && tree[id].r <= r) return tree[id].sum;
    down(id);
    return (query(id * 2, l, r) + query(id * 2 + 1, l, r)) % mod;
}
int main() {
    cin >> n >> q >> mod;
    for (int i = 1; i <= n; ++i) cin >> num[i];
    build(1, 1, n);
    for (int i = 1; i <= q; ++i) {
        cin >> oper;
        if (oper == 1) {
            cin >> x >> y >> k;
            update_mul(1, x, y, k);
        }
        else if (oper == 2) {
            cin >> x >> y >> k;
            update_add(1, x, y, k);
        }
        else if (oper == 3) {
            cin >> x >> y;
            cout << query(1, x, y) % mod<< '\n';    //不要忘记再取模一次
        }
    }
    return 0;
}
文章作者: 热心市民灰灰
文章链接: http://example.com/2023/08/09/shu-xing-jie-gou/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 热心市民灰灰 !
C++ 算法 数据结构
  目录