当前位置：首页 > news >正文

洛谷P3373线段树详解【模板】

news 2025/4/26 21:27:01

洛谷P3373题目概述

洛谷P3373是一道关于线段树的模板题，题目名称为“【模板】线段树 2”。题目的主要要求是对一个长度为 n 的数列进行如下操作：

将某区间每个数乘上一个数。
将某区间每个数加上一个数。
求出某区间所有数的和。

线段树简介

线段树是一种二叉树数据结构，常用于高效处理区间查询和更新操作。它可以将一个区间划分为多个子区间，每个节点代表一个区间，通过维护这些节点的信息，可以在 $O(\log n)$ 的时间复杂度内完成区间查询和更新操作。

代码详细讲解

1. 头文件和宏定义

#include <iostream>
#include <cmath>
using namespace std;
#define MAXN 400002
#define lson (root*2)
#define rson (root*2+1)

#include <iostream> 和 #include <cmath> 分别引入输入输出流和数学库。
using namespace std; 表示使用标准命名空间。
MAXN 定义了线段树数组的最大长度，通常为 $4 n$ ，因为线段树的节点数最多为 $4 n$ 。
lson 和 rson 分别表示当前节点的左子节点和右子节点的编号。

2. 全局变量

int MOD;
long long sgmt[MAXN], lazy_mul[MAXN], lazy_add[MAXN];

MOD 是取模的基数，用于防止结果溢出。
sgmt[MAXN] 是线段树数组，用于存储每个节点所代表区间的和。
lazy_mul[MAXN] 和 lazy_add[MAXN] 是懒标记数组，分别用于标记乘法和加法操作。

3. `push_up` 函数

void push_up(int root) {sgmt[root] = sgmt[lson] + sgmt[rson];sgmt[root] %= MOD;
}

该函数用于将左右子节点的信息更新到父节点。具体来说，将左子节点和右子节点所代表区间的和相加，并取模后赋值给父节点。

4. `push_down` 函数

void push_down(int root, int len) {if (lazy_mul[root] == 1 && lazy_add[root] == 0) return;lazy_mul[lson] *= lazy_mul[root], lazy_mul[lson] %= MOD;lazy_mul[rson] *= lazy_mul[root], lazy_mul[rson] %= MOD;lazy_add[lson] *= lazy_mul[root], lazy_add[lson] %= MOD;lazy_add[rson] *= lazy_mul[root], lazy_add[rson] %= MOD;lazy_add[lson] += lazy_add[root], lazy_add[lson] %= MOD;lazy_add[rson] += lazy_add[root], lazy_add[rson] %= MOD;sgmt[lson] *= lazy_mul[root], sgmt[lson] %= MOD;sgmt[lson] += (len/2)*lazy_add[root], sgmt[lson] %= MOD;sgmt[rson] *= lazy_mul[root], sgmt[rson] %= MOD;sgmt[rson] += (len/2)*lazy_add[root], sgmt[rson] %= MOD;lazy_mul[root] = 1, lazy_add[root] = 0;
}

该函数用于将当前节点的懒标记下推到左右子节点。
首先判断当前节点是否有懒标记，如果 lazy_mul[root] 为 1 且 lazy_add[root] 为 0，则说明没有懒标记，直接返回。
然后将当前节点的乘法懒标记和加法懒标记下推到左右子节点，并更新左右子节点的线段树数组和懒标记数组。
最后将当前节点的懒标记重置为初始值。

5. `update` 函数

void update(int a, int b, long long c, long long d, int l, int r, int root) {if (a <= l && r <= b) {sgmt[root] *= c, sgmt[root] %= MOD;sgmt[root] += (r-l+1)*d, sgmt[root] %= MOD;lazy_mul[root] *= c, lazy_mul[root] %= MOD;lazy_add[root] *= c, lazy_add[root] %= MOD;lazy_add[root] += d, lazy_add[root] %= MOD;return;}push_down(root,r-l+1);int mid = (l+r)/2;if (a <= mid) update(a,b,c,d,l,mid,lson);if (b > mid) update(a,b,c,d,mid+1,r,rson);push_up(root);
}

该函数用于更新区间 [a, b] 内的所有数，将每个数先乘上 c，再加上 d。
如果当前节点所代表的区间完全包含在 [a, b] 内，则直接更新当前节点的线段树数组和懒标记数组。
否则，先将当前节点的懒标记下推，然后递归更新左右子节点，最后更新当前节点的线段树数组。

6. `query` 函数

long long query(int a, int b, int l, int r, int root) {if (a <= l && r <= b) return sgmt[root];push_down(root,r-l+1);long long ans = 0;int mid = (l+r)/2;if (a <= mid) ans += query(a,b,l,mid,lson), ans %= MOD;if (b > mid) ans += query(a,b,mid+1,r,rson), ans %= MOD;return ans;
}

该函数用于查询区间 [a, b] 内所有数的和。
如果当前节点所代表的区间完全包含在 [a, b] 内，则直接返回当前节点的线段树数组的值。
否则，先将当前节点的懒标记下推，然后递归查询左右子节点，并将结果相加。

7. `build` 函数

void build(int l, int r, int root) {if (l == r) return;int mid = (l+r)/2;build(l,mid,lson);build(mid+1,r,rson);push_up(root);return;
}

该函数用于构建线段树。
如果当前节点所代表的区间只有一个元素，则直接返回。
否则，递归构建左右子节点，然后更新当前节点的线段树数组。

8. `main` 函数

int main() {for (int i = 1; i < MAXN; i++)lazy_mul[i] = 1;int n, m; cin >> n >> m >> MOD;int npot = 1 << (int)ceil(log2(n));for (int i = 0; i < n; i++)cin >> sgmt[npot+i];n = npot;int l = 1, r = n, root = 1;build(l,r,root);while (m--) {int op, a, b, c; cin >> op >> a >> b;if (op == 1) {cin >> c; update(a,b,c,0,l,r,root);} else if (op == 2) {cin >> c; update(a,b,1,c,l,r,root);} elsecout << query(a,b,l,r,root)%MOD << endl;}return 0;
}

首先将所有乘法懒标记初始化为 1。
然后读取数列的长度 n、操作的次数 m 和取模的基数 MOD。
接着将数列存储在线段树数组中，并将 n 扩展为 2 的幂次方。
调用 build 函数构建线段树。
最后循环处理 m 次操作，根据操作类型调用 update 或 query 函数。

复杂度分析

时间复杂度：每次更新和查询操作的时间复杂度均为 $O(\log n)$ ，因此总的时间复杂度为 $\log n)$ 。
空间复杂度：线段树数组和懒标记数组的空间复杂度均为 $O (4 n)$ ，因此总的空间复杂度为 $O (n)$ 。

完整代码：

// P3373 【模板】线段树 2
#include <iostream>
#include <cmath>
using namespace std;
#define MAXN 400002
#define lson (root*2)
#define rson (root*2+1)int MOD;
long long sgmt[MAXN], lazy_mul[MAXN], lazy_add[MAXN];void push_up(int root) {sgmt[root] = sgmt[lson] + sgmt[rson];sgmt[root] %= MOD;
}void push_down(int root, int len) {if (lazy_mul[root] == 1 && lazy_add == 0) return;lazy_mul[lson] *= lazy_mul[root], lazy_mul[lson] %= MOD;lazy_mul[rson] *= lazy_mul[root], lazy_mul[rson] %= MOD;lazy_add[lson] *= lazy_mul[root], lazy_add[lson] %= MOD;lazy_add[rson] *= lazy_mul[root], lazy_add[rson] %= MOD;lazy_add[lson] += lazy_add[root], lazy_add[lson] %= MOD;lazy_add[rson] += lazy_add[root], lazy_add[rson] %= MOD;sgmt[lson] *= lazy_mul[root], sgmt[lson] %= MOD;sgmt[lson] += (len/2)*lazy_add[root], sgmt[lson] %= MOD;sgmt[rson] *= lazy_mul[root], sgmt[rson] %= MOD;sgmt[rson] += (len/2)*lazy_add[root], sgmt[rson] %= MOD;lazy_mul[root] = 1, lazy_add[root] = 0;
}void update(int a, int b, long long c, long long d, int l, int r, int root) {if (a <= l && r <= b) {sgmt[root] *= c, sgmt[root] %= MOD;sgmt[root] += (r-l+1)*d, sgmt[root] %= MOD;lazy_mul[root] *= c, lazy_mul[root] %= MOD;lazy_add[root] *= c, lazy_add[root] %= MOD;lazy_add[root] += d, lazy_add[root] %= MOD;return;}push_down(root,r-l+1);int mid = (l+r)/2;if (a <= mid) update(a,b,c,d,l,mid,lson);if (b > mid) update(a,b,c,d,mid+1,r,rson);push_up(root);
}long long query(int a, int b, int l, int r, int root) {if (a <= l && r <= b) return sgmt[root];push_down(root,r-l+1);long long ans = 0;int mid = (l+r)/2;if (a <= mid) ans += query(a,b,l,mid,lson), ans %= MOD;if (b > mid) ans += query(a,b,mid+1,r,rson), ans %= MOD;return ans;
}void build(int l, int r, int root) {if (l == r) return;int mid = (l+r)/2;build(l,mid,lson);build(mid+1,r,rson);push_up(root);return;
}int main() {for (int i = 1; i < MAXN; i++)lazy_mul[i] = 1;int n, m; cin >> n >> m >> MOD;int npot = 1 << (int)ceil(log2(n));for (int i = 0; i < n; i++)cin >> sgmt[npot+i];n = npot;int l = 1, r = n, root = 1;build(l,r,root);while (m--) {int op, a, b, c; cin >> op >> a >> b;if (op == 1) {cin >> c; update(a,b,c,0,l,r,root);} else if (op == 2) {cin >> c; update(a,b,1,c,l,r,root);} elsecout << query(a,b,l,r,root)%MOD << endl;}return 0;
}