经验总结

  1. 首页 > 生活 > >

基础&进阶 线段树学习笔记（一） | P3372 【模板】线段树 1 题解

生活百科

什么是线段树线段树是一棵二叉树，每个结点存储需维护的信息，一般用于处理区间最值、区间和等问题 。
线段树的用处对编号连续的一些点进行修改或者统计操作，修改和统计的复杂度都是 O(log n) 。
基础线段树（+ 懒标记）为什么不写没有懒标记的版本？因为我太菜的不会写 因为有懒标记的版本更实用啦 。

  • P3372 【模板】线段树 1
【基础&进阶 线段树学习笔记（一） | 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;}

经验总结扩展阅读


上一篇：有趣实验 .NET下数据库的负载均衡

下一篇：oppoa83屏幕多大