什么是线段树线段树是一棵二叉树,每个结点存储需维护的信息,一般用于处理区间最值、区间和等问题 。
线段树的用处对编号连续的一些点进行修改或者统计操作,修改和统计的复杂度都是 O(log n) 。
基础线段树(+ 懒标记)为什么不写没有懒标记的版本?因为我太菜的不会写 因为有懒标记的版本更实用啦 。
- P3372 【模板】线段树 1
1. 建树
void build(int rt, int L, int R) { l[rt] = L, r[rt] = R; if (L == R) {sum[rt] = a[L];return ; } int mid = L + R >> 1; build(rt << 1, L, mid), build(rt << 1 | 1, mid + 1, R); update(rt);}
作为一棵最最普通的线段树 , 它有一个性质,对于每个结点 x,它的左儿子的编号是 x * 2 (即代码中的 x << 1
),右儿子的编号是 x * 2 + 1 (即代码中的 x << 1 | 1
) 。代码中的 l 和 r 数组用于记录编号为 rt 的点所管辖的区间的左右端点 。update
是什么?它是用子节点的数据更新自身的数据 , 以保证正确性 。- update 的具体实现
void update(int rt) { sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}
它在后续的操作中也会用到 。2. 修改
void change(int rt, int L, int R, int x) { if (L <= l[rt] && r[rt] <= R) {sum[rt] += (r[rt] - l[rt] + 1) * x;lazy[rt] += x;return ; } pushdown(rt); if (L <= r[rt << 1]) change(rt << 1, L, R, x); if (l[rt << 1 | 1] <= R) change(rt << 1 | 1, L, R, x); update(rt);}
其中传入的参数 L 和 R 表示需修改的区间的左右端点 , x 表示这个区间上要加的数 。if (L <= l[rt] && r[rt] <= R)
意为当该点管辖的区间被需修改的区间全覆盖时 , 直接修改这个点上记录的区间和,并打上懒标记,不继续下传,以保证效率 。(懒标记就是一种记录修改操作的 tag,用于节省时间 。)pushdown
操作意为该点管辖的区间不完全覆盖于需修改的区间时,下传懒标记 。(为什么现在才下传?因为懒标记就是这么用的 因为后面的更改会用到该点的子节点的数据 , 如果懒标记不下传,后面的修改操作就会出现问题 。)下面的两个 if
是什么?if (L <= r[rt << 1])
表示左儿子的区间中有部分(或全部)包含于询问区间,需统计 。(如果还是没看出来就翻回去看看定义和性质吖)那么是不是就知道 if (l[rt << 1 | 1] <= R)
是什么了?对,它表示的是右儿子的区间中有部分(或全部)包含于询问区间,需统计 。传的参数为什么是这样不用我说了吧?- pushdown 的具体实现
void pushdown(int rt) { if (!lazy[rt]) return ; sum[rt << 1] += (r[rt << 1] - l[rt << 1] + 1) * lazy[rt]; sum[rt << 1 | 1] += (r[rt << 1 | 1] - l[rt << 1 | 1] + 1) * lazy[rt]; lazy[rt << 1] += lazy[rt]; lazy[rt << 1 | 1] += lazy[rt]; lazy[rt] = 0; update(rt);}
在下传懒标记时给子节点的区间和加上 懒标记的值 × 子节点的区间大小 。(给该子节点的管辖区间的所有数都加上懒标记的值,那么该区间的区间和就会加上 懒标记的值 × 区间长度 。)同时,给子节点的懒标记都加上自己的懒标记的值 。(没错我还是给你吊在那里,不给你传到底)记得清空自己的懒标记值并更新自己的区间和 。3. 查询
ll query(int rt, int L, int R) { if (L <= l[rt] && r[rt] <= R) return sum[rt]; pushdown(rt); ll res = 0; if (L <= r[rt << 1]) res += query(rt << 1, L, R); if (l[rt << 1 | 1] <= R) res += query(rt << 1 | 1, L, R); return res;}
查询其实和修改很像 。(不妨肉眼观查一下)在该结点所管辖的区间完全被覆盖时,直接返回区间和 。若未被完全覆盖,则下传懒标记,分左右儿子考虑,统计总答案并返回值 。是不是 so easy?于是你愉快地切了这题 。
完整代码,点击查看【基础&进阶 线段树学习笔记(一) | P3372 【模板】线段树 1 题解】
#include <bits/stdc++.h>using namespace std;#define ll long long#define pii pair<int, int>inline ll read() { ll s = 0, w = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') w = -1; c = getchar();} while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar(); return s * w;}const int N = 100010;int n, m, a[N];struct SegmentTree { ll sum[N << 2], lazy[N << 2]; int l[N << 2], r[N << 2]; void update(int rt) {sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; } void pushdown(int rt) {if (!lazy[rt]) return ;sum[rt << 1] += (r[rt << 1] - l[rt << 1] + 1) * lazy[rt], lazy[rt << 1] += lazy[rt];sum[rt << 1 | 1] += (r[rt << 1 | 1] - l[rt << 1 | 1] + 1) * lazy[rt], lazy[rt << 1 | 1] += lazy[rt];lazy[rt] = 0;update(rt); } void build(int rt, int L, int R) {l[rt] = L, r[rt] = R;if (L == R) {sum[rt] = a[L];return ;}int mid = L + R >> 1;build(rt << 1, L, mid), build(rt << 1 | 1, mid + 1, R);update(rt); } void change(int rt, int L, int R, int x) {if (L <= l[rt] && r[rt] <= R) {sum[rt] += (r[rt] - l[rt] + 1) * x;lazy[rt] += x;return ;}pushdown(rt);if (L <= r[rt << 1]) change(rt << 1, L, R, x);if (l[rt << 1 | 1] <= R) change(rt << 1 | 1, L, R, x);update(rt); } ll query(int rt, int L, int R) {if (L <= l[rt] && r[rt] <= R) return sum[rt];pushdown(rt);ll res = 0;if (L <= r[rt << 1]) res += query(rt << 1, L, R);if (l[rt << 1 | 1] <= R) res += query(rt << 1 | 1, L, R);return res; }} tree;int main() { n = read(), m = read(); for (int i = 1; i <= n; i++) a[i] = read(); tree.build(1, 1, n); while (m--) {int op = read();if (op == 1) {int l = read(), r = read(), x = read();tree.change(1, l, r, x);}if (op == 2) {int l = read(), r = read();printf("%lld\n", tree.query(1, l, r));} } return 0;}
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- HTML&CSS-盒模型运用居中方式合集
- JS 模块化-05 ES Module & 4 大规范总结
- 两道超有意思的 CSS 面试题,试试你的基础
- 研发效能之技术治理&技术治理架构师
- 一百一十九 salesforce零基础学习In-App Guidance实现引导页操作功能
- flutter系列之:深入理解布局的基础constraints
- 为什么阿里Java开发手册不推荐使用Timestamp
- 古代的"一两白银"相当于现在的多少钱?
- are't的完全形式是什么
- 临沂市2022年中考数学考点 临沂市中考数学考点