【题目来源】
洛谷：P3372 【模板】线段树 1 - 洛谷
【题目描述】
如题，已知一个数列，你需要进行下面两种操作：
- 将某区间每一个数加上 k。
- 求出某区间每一个数的和。
【输入】
第一行包含两个整数 n,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。
接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下：
1 x y k：将区间 [x,y] 内每个数加上 k。2 x y：输出区间 [x,y] 内每个数的和。
【输出】
输出包含若干行整数，即为所有操作 2 的结果。
【输入样例】
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
【输出样例】
11
8
20
【算法标签】
《洛谷 P3372 线段树1》 #线段树#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 定义int为long long类型
#define lc p << 1 // 左子节点索引
#define rc p << 1 | 1 // 右子节点索引
#define N 100005 // 数组最大长度int n, m, w[N]; // n:元素个数，m:操作次数，w:原始数组// 线段树节点结构体
struct Node
{int l, r; // 节点代表的区间[l,r]int sum; // 区间和int add; // 懒惰标记
} tr[N * 4]; // 线段树数组/*** 构建线段树* @param p 当前节点索引* @param l 区间左端点* @param r 区间右端点*/
void build(int p, int l, int r)
{tr[p] = {l, r, w[l], 0}; // 初始化节点if (l == r) // 叶子节点直接返回return;int m = l + r >> 1; // 计算中点build(lc, l, m); // 递归构建左子树build(rc, m + 1, r); // 递归构建右子树tr[p].sum = tr[lc].sum + tr[rc].sum; // 更新区间和
}/*** 下推懒惰标记* @param p 当前节点索引*/
void pushdown(int p)
{if (tr[p].add) // 如果有懒惰标记{// 更新左右子节点的区间和tr[lc].sum += tr[p].add * (tr[lc].r - tr[lc].l + 1);tr[rc].sum += tr[p].add * (tr[rc].r - tr[rc].l + 1);// 更新左右子节点的懒惰标记tr[lc].add += tr[p].add;tr[rc].add += tr[p].add;tr[p].add = 0; // 清除当前节点的懒惰标记}
}/*** 区间查询* @param p 当前节点索引* @param x 查询区间左端点* @param y 查询区间右端点* @return 区间和*/
int query(int p, int x, int y)
{if (x <= tr[p].l && tr[p].r <= y) // 完全包含区间return tr[p].sum;int m = tr[p].l + tr[p].r >> 1; // 计算中点pushdown(p); // 下推懒惰标记int sum = 0;if (x <= m)sum += query(lc, x, y); // 查询左子树if (y > m)sum += query(rc, x, y); // 查询右子树return sum;
}/*** 区间更新* @param p 当前节点索引* @param x 更新区间左端点* @param y 更新区间右端点* @param k 增量值*/
void update(int p, int x, int y, int k)
{if (x <= tr[p].l && tr[p].r <= y) // 完全包含区间{tr[p].sum += (tr[p].r - tr[p].l + 1) * k; // 更新区间和tr[p].add += k; // 更新懒惰标记return;}int m = tr[p].l + tr[p].r >> 1; // 计算中点pushdown(p); // 下推懒惰标记if (x <= m)update(lc, x, y, k); // 更新左子树if (y > m)update(rc, x, y, k); // 更新右子树tr[p].sum = tr[lc].sum + tr[rc].sum; // 更新当前节点的区间和
}signed main()
{cin >> n >> m;for (int i = 1; i <= n; i++)cin >> w[i]; // 输入原始数组build(1, 1, n); // 构建线段树while (m--){int op;cin >> op;if (op == 1) // 区间更新操作{int x, y, k;cin >> x >> y >> k;update(1, x, y, k);}else // 区间查询操作{int x, y;cin >> x >> y;cout << query(1, x, y) << endl;}}return 0;
}
【运行结果】
5 5
1 5 4 2 3
2 2 4
11
1 2 3 2
2 3 4
8
1 1 5 1
2 1 4
20