- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
「观前提醒」 。
「文章仅供学习和参考,如有问题请在评论区提出」 。
线段树(Segment Tree) 是算法竞赛中常用的用来维护区间信息的数据结构.
线段树可以在 \(O(logN)\) 的时间复杂度内实现 单点修改、区间修改、区间查询 等操作。能够用来维护很多类型的信息,包括但不仅限于 求区间和、求区间最值、求区间最大子段和、求区间最大公约数 等.
这里先给出线段树的结构图, 。
从结构图我们可以看到,线段树是一颗 平衡二叉树 ,而且每个节点都对应了一个区间值.
然后我们发现,对于编号为 \(p\) 的节点,它的左右儿子节点编号分别为 \(2p\) 和 \(2p + 1\) 。同理,我们也能够推出编号为 \(p\) 的节点的父节点编号为 $\left \lfloor \frac{p}{2} \right \rfloor $ .
现在我们把图稍微改变一下, 。
我们发现,对于任意一对左右节点的区间范围,是通过其父节点的区间区间折半推导出来的.
若 \(tr_{p}\) 所维护的区间是 \([l, r]\) ,然后取 $mid = \left \lfloor \frac{l + r}{2} \right \rfloor $ ,那么 \(tr_{p}\) 的左儿子节点 \(tr_{2p}\) 表示区间就是 \([l, mid]\) ,右儿子节点 \(tr_{2p + 1}\) 表示的区间是 \([mid + 1, r]\) .
这里我们注意到,对于编号为 \(p\) 的节点,它的左右节点所表示的区间长度不一定会相等。但是这样并不会影响线段树的整体结构,因为每个节点都会不断往下细分,直到区间长度为 \(1\) .
所以这里只需要满足,一对左右儿子节点所表示的区间的加和就是其父亲节点所表示的区间就行,即 \(tr_{p} = tr_{2p} + tr_{2p + 1}\) (这里指的是区间相加).
根据上面所理解的线段树的存储逻辑,我们需要一层一层地向下折半拆分,直到区间长度为 \(1\) 时再对其进行赋值。那么我们就可以考虑用 递归 来实现这个过程.
而且又因为每个节点维护的是某一段的区间值,对于所要维护的区间值(区间和、区间最值等)不同,建树的逻辑也会有些许的不同,但是总体思路是相同的。那么我们这里就以 求区间加和 问题来举例.
我们每次分别进行递归遍历自己的左右节点,直到区间长度为 \(1\) 时,对自身进行赋值。然后每个节点再根据已经更新好后的左右节点值,对自身进行赋值.
这里我们可以专门写一个 pushup() 函数来进行父节点的更新,因为越往后看就会发现更新父节点是个重复操作,没有必要重复写.
这样的话,我们就需要分层遍历每个节点,所以建树的时间复杂度就是 \(O(N)\) .
代码 (以求区间和为例) 。
const int N = 1e5 + 10; // 根据序列数据范围而定
// 对于存储每个节点需要 2n 的空间,但每次会 ×2 来获取子节点,所以一般还要再多开 2n 的空间来防止越界
struct Node { // 每个节点所存储的信息
int l, r; // 当前节点维护的区间 [l, r]
int sum; // 当前节点所维护的区间值
} tr[N * 4]; // tr[] 存储线段树数据
int a[N]; // a[] 存储原数组数据
// 计算 u 节点区间值并更新
void pushup(int u) {
// 根据已经更新好的左右节点值来更新自身
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
// 建树函数
// u 是节点编号,[l, r] 是此时编号为 p 的节点所要代表的区间
void build(int u, int l, int r) {
if (l == r) tr[u] = {l, r, a[l]}; // 此时区间长度为 1,进行赋值
else {
tr[u] = {l, r}; // 更新当前节点区间
int mid = l + r >> 1; // 位运算,相当于 (l + r) / 2
// 分别向下递归左右节点
build(u << 1, l, mid); // u << 1,位运算,相当于 u * 2
build(u << 1 | 1, mid + 1, r); // u << 1 | 1, 位运算,相当于 u * 2 + 1
// 计算当前节点区间值并更新
pushup(u);
}
}
// 建树
int n; // 序列长度
build(1, 1, n);
若我们想要查询区间 \([l, r]\) 内每个数的加和,我们只需要从根节点开始,用每个节点所维护的区间 \([a, b]\) 和要查询的区间 \([l, r]\) 进行对比。那么就会有三种情况:(我们取 $mid = \left \lfloor \frac{a + b}{2} \right \rfloor $ ) 。
如果 \(l \le a \le b \le r\) ,直接返回当前节点值.
如果 \(l \le mid\) , 还需继续往下访问左节点.
如果 \(mid + 1\le r\) ,还需继续往下访问右节.
然后就是递归处理这三种情况,最终返回所要查询的区间值.
因为一个区间 \([l, r]\) ,最多可以将其拆成 \(logN\) 个极大的区间,所以每次查询的时间复杂度为 \(O(logN)\) .
代码实现 (以求区间和为例) 。
struct Node {
int l, r; // 区间 [l, r]
int sum; // 区间值
} tr[N * 4];
// 查询操作, u 是节点编号, [l, r] 是要查询的区间
void query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) // 当前节点区间被 [l, r] 完全包含
return tr[u].sum; // 返回当前节点值
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
if (l <= mid) sum += query(u << 1, l, r); // 遍历左节点
if (r >= mid + 1) sum += query(u << 1 | 1, l, r); // 遍历右节点
return sum; // 返回加和的值
}
对于线段的单点修改逻辑很简单,就是不断地向下拆分区间,直到区间长度为 \(1\) 的叶子节点。然后对其进行修改,同时在修改完回溯的时候,再用 pushup() 更新父节点的值.
这里的向下遍历的思路和区间查询差不多,就是判断要修改的位置是在左节点还是右节点.
这样的话,我们最多就会遍历 \(logN\) 层,所以单点修改的时间复杂度为 \(O(logN)\) .
代码实现 (以求区间和为例) 。
struct Node {
int l, r; // 区间 [l, r]
int sum; // 区间加和值
} tr[N * 4];
// 更新节点 u 的值
void pushup(int u) {
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
// 修改操作, u 是节点编号, x 是要修改的位置, v 是要修改成的值
void modify(int u, int x, int v) {
if (tr[u].l == x && tr[u].r == x) // 查询到节点
tr[u].sum = v; // 修改节点值
else {
int mid = tr[u].l + tr[u].r >> 1;
// 遍历左右节点
if (x <= mid) modify(u << 1, x, v);
if (x >= mid + 1) modify(u << 1 | 1, x, v);
pushup(u); // 修改后, 在回溯时对节点值进行更新
}
}
对于区间修改,我们不可能遍历每个节点,然后更新 \([l, r]\) 区间里的每个节点值,因为这样的时间复杂度是 \(O(N)\) 的。而这种时间复杂度对于线段树来说是不可取的.
那么我们应该怎么进行修改呢?接下来我们就需要用到 懒惰标记 .
懒惰标记 ,就是对节点信息的延迟更新,即用多少,就更新多少的方式,以此来降低修改操作所耗费的时间。每次执行修改操作的时候,我们通过打标记的方式表明该节点对应的区间在某一次操作中被修改,但是不更新该节点的子节点信息。然后在下一次访问该节点时才会下放标记并且更新子节点.
同区间查询相同,对于一个要修改的区间 \([l, r]\) ,最多可以将其拆成 \(logN\) 个极大的区间,所以每次区间修改的时间复杂度就被降为了 \(O(logN)\) .
这里我们也可以写一个 pushdown() 函数来进行子节点数值的更新和标记下放.
因为一旦访问到被打上标记的节点,就需要执行 pushdown() 操作,从而使访问能够继续向下传递。所以在执行 区间查询 和 区间修改 的时候,都需要在访问左右节点前进行 pushdown() 操作来更新左右节点的信息.
代码实现 (维护区间和,修改操作是增加 \(d\) ) 。
struct Node {
int l, r; // 区间 [l, r]
int sum; // 区间值
int add; // 懒惰标记, 表示要增加的值
} tr[N * 4];
// 更新节点 u 的值
void pushup(int u) {
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
// 更新节点 u 左右节点的值并下放标记
void pushdown(int u) {
Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if (root.add) { // 当前节点有标记才执行
// 更新左右节点的值
// 因为维护的是区间和, 区间内每个节点加上 root.add, 区间值就相当于加了 区间长度 * root.add
left.sum += (left.r - left.l + 1) * root.add;
rignt.sum = (right.r - right.l + 1) * root.add;
// 给左右节点下方标记
left.add += root.add;
right.add += root.add;
// 清空当前节点标记
root.add = 0;
}
}
// 修改操作, u 是节点编号, [l, r] 是要修改的区间, d 是要增加的值
void modify(int u, int l, int r, int d) {
if (tr[u].l >= l && tr[u].r <= r) { // 区间被完全包含, 更新当前节点并打上标记
tr[u].sum += (tr[u].r - tr[u].l + 1) * d; // 更新节点值
tr[u].add += d; // 打标记
} else {
pushdown(u); // 先更新左右节点值后再进行访问
int mid = tr[u].l + tr[u].r >> 1;
// 访问左右节点
if (l <= mid) modify(u << 1, l, r, d);
if (r >= mid + 1) modiy(u << 1 | 1, l, r, d);
pushup(u); // 有节点被修改, 需要回溯时进行更新
}
}
// 查询操作, u 是节点编号, [l, r] 是要查找的区间
void query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) // 区间被完全包含, 直接返回当前值
return tr[u].sum;
pushdown(u); // 先更新左右节点值后再进行访问
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
// 访问左右节点, 求加和值
if (l <= mid) sum += query(u << 1, l, r);
if (r >= mid + 1) sum += query(u << 1 | 1, l, r);
return sum; // 返回加和值
}
题目描述 。
1 x y k :将区间 \([x, y]\) 内每个数加上 \(k\) .
2 x y :输出区间 \([x, y]\) 内每个数的和.
代码 。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
struct Node {
int l, r;
LL sum;
LL add;
} tr[N * 4];
int a[N];
void pushup(int u) {
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u) {
Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
if (root.add) {
left.add += root.add, right.add += root.add;
left.sum += (LL)(left.r - left.l + 1) * root.add;
right.sum += (LL)(right.r - right.l + 1) * root.add;
root.add = 0;
}
}
void build(int u, int l, int r) {
if (l == r) tr[u] = {l, r, a[l]};
else {
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int d) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].sum += (LL)(tr[u].r - tr[u].l + 1) * d;
tr[u].add += d;
} else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, d);
if (r > mid) modify(u << 1 | 1, l, r, d);
pushup(u);
}
}
LL query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r)
return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL sum = 0;
if (l <= mid) sum += query(u << 1, l, r);
if (r > mid) sum += query(u << 1 | 1, l, r);
return sum;
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(1, 1, n);
while (m--) {
int op, x, y, k;
scanf("%d", &op);
if (op == 1) {
scanf("%d%d%d", &x, &y, &k);
modify(1, x, y, k);
} else {
scanf("%d%d", &x, &y);
printf("%lld\n", query(1, x, y));
}
}
return 0;
}
题目描述 。
1 x y k :将区间 \([x, y]\) 内每个数乘上 \(k\) .
2 x y k :将区间 \([x, y]\) 内每个数加上 \(k\) .
3 x y :输出区间 \([x, y]\) 内每个数的和对 \(m\) 取模所得的结果.
代码 。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
struct Node {
int l, r;
LL sum;
LL mul;
LL add;
} tr[N * 4];
int a[N];
int n, q, p;
void pushup(int u) {
tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % p;
}
void pushdown(int u) {
Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
left.sum = (left.sum * root.mul + (left.r - left.l + 1) * root.add) % p;
right.sum = (right.sum * root.mul + (right.r - right.l + 1) * root.add) % p;
left.mul = (left.mul * root.mul) % p;
right.mul = (right.mul * root.mul) % p;
left.add = (left.add * root.mul + root.add) % p;
right.add = (right.add * root.mul + root.add) % p;
root.mul = 1, root.add = 0;
}
void build(int u, int l, int r) {
tr[u].l = l, tr[u].r = r, tr[u].mul = 1, tr[u].add = 0;
if (l == r) tr[u].sum = a[l];
else {
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int d) {
if (tr[u].l >= l && tr[u].r <= r) {
if (d >= 0) { // 加法操作
tr[u].sum = (tr[u].sum + (LL)(tr[u].r - tr[u].l + 1) * d) % p;
tr[u].add = (tr[u].add + d) % p;
} else { // 乘法操作
d = -d;
tr[u].sum = (tr[u].sum * d) % p;
tr[u].mul = (tr[u].mul * d) % p;
tr[u].add = (tr[u].add * d) % p;
}
} else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, d);
if (r > mid) modify(u << 1 | 1, l, r, d);
pushup(u);
}
}
LL query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r)
return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL sum = 0;
if (l <= mid) sum = (sum + query(u << 1, l, r)) % p;
if (r > mid) sum = (sum + query(u << 1 | 1, l, r)) % p;
return sum;
}
int main() {
int n, m;
cin >> n >> m >> p;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(1, 1, n);
while (m--) {
int op, x, y, k;
scanf("%d", &op);
if (op == 1) {
scanf("%d%d%d", &x, &y, &k);
modify(1, x, y, -k);
} else if (op == 2) {
scanf("%d%d%d", &x, &y, &k);
modify(1, x, y, k);
} else {
scanf("%d%d", &x, &y);
printf("%lld\n", query(1, x, y));
}
}
return 0;
}
这里只是讲了线段树的基本用法,例题也都是模板题。其实对于各种线段树的题目来说,最难的就是如何去维护懒惰标记。因为平时遇到的线段树题目都会有着相应的变形,所以都会比较难。而且因为代码量很大,很容易出错,在重新检查、找bug的时候也比较麻烦.
所以还是得多做题,多熟悉,才能更熟练地使用.
线段树 - OI Wiki: https://oi-wiki.org/ds/seg/ 。
算法学习笔记(14): 线段树 - 知乎: https://zhuanlan.zhihu.com/p/106118909 。
最后此篇关于线段树的文章就讲到这里了,如果你想了解更多关于线段树的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
有没有办法将多个线段视为 1 条线? IE:我将鼠标悬停在其中一个上,两者都会突出显示,并且切换图例中的可见性将隐藏这两个部分。 http://jsfiddle.net/rayholland/HSvB
有没有办法将多条线段视为一条线? IE:我将鼠标悬停在一个上,两个都突出显示,切换图例中的可见性将隐藏两个部分。 http://jsfiddle.net/rayholland/HSvBj/2/ ser
我正在尝试解决有关使用箭头键绘制线条的练习。当按下任一箭头键时,该线从中心开始向东、西、北或南绘制。该代码仅在东或西方向有效,而在北或南方向无效,这是我的问题!! 有人可以给我关于这件事的想法吗?谢谢
给定每条线的起点和终点的 XYZ 坐标,如何确定两条 3D 线段是否相交?如果它们确实相交,在什么 XYZ 位置? 我只能找到 2D 的答案:How do you detect where two l
给定每条线的起点和终点的 XYZ 坐标,如何确定两条 3D 线段是否相交?如果它们确实相交,在什么 XYZ 位置? 我只能找到 2D 的答案:How do you detect where two l
我正在使用适用于 ios 的 google map sdk 来提供当前用户位置和结束位置之间的方向。到目前为止,我已经使用下面的代码在当前用户位置和结束位置之间绘制了一条 GMSPolyline,并且
我是 Qt 的新手,我想使用 Qt 使用 CGAL 制作交互式几何程序。我希望用户使用鼠标输入点、线段,然后按下按钮让 CGAL 算法处理输入。 我的环境是 CGAL 4.5、Qt 5.6 和 QtC
我有两条线段:X1,Y1,Z1 - X2,Y2,Z2 和 X3,Y3,Z3 - X4,Y4,Z4 我试图找到两个线段之间的最短距离。 几个小时以来,我一直在寻找解决方案,但所有这些解决方案似乎都适用于
我正在尝试在 WPF 中创建铁路轨道和带有边界和标签的街道等效果。如何向线段添加边框和沿线段的标签?我试过 Border 类,但它创建了一个矩形边框。 对于标签,我尝试了 Text on a path
我正在做一个小项目来显示基于路线段重叠的路线效率低下。 例如,我在这里放了一个 JSFIDDLE,显示 D 和 E 之间有一条粉红色和蓝色的线重叠。我如何确定这段路在它们的路线上有重叠? 路线将由用户
我想绘制三组数据。具体来说,我想显示单个数据点,包括三组的均值。这是我到目前为止所拥有的: library(ggplot2) df <- data.frame(group=rep(c("A", "B"
我想绘制三组数据。具体来说,我想显示单个数据点,包括三组的均值。这是我到目前为止所拥有的: library(ggplot2) df <- data.frame(group=rep(c("A", "B"
<line> 元素可以用来画线段 SVG 线段 <line> <line> 元素可以用来画线段 线段的起始坐标可以用 x1 和 y1 来定义 线段的终点坐标可
我正在我的游戏中编写 C++ 碰撞检测程序,并试图提出一种算法:我有一个由两个中心点(C1、C2)、长度和半径定义的胶囊。然后我有一条用两点(R1,R2)定义的射线。我已经知道它们相交了。我只需要找到
我正在创建一个包含多变量数据的 PCA 双图。 有没有办法在 ggbiplot 中指定线段的颜色/透明度/位置?此命令的所有参数均未提供此选项。 我知道 ggbiplot 是基于 ggplot - 它
最近学了下 python opencv,分享下使用 opencv 在图片上绘制常用图形的方法。 案例中实现了在图片中添加线段、圆形、矩形、椭圆形以及添加文字的方法,使用 opencv2 实现的
我在应用 rgl 3d 绘图包时遇到了一些问题。 我正在尝试绘制一些线段。我的数据被安排在一个名为“标记”的数据框中,它有六列,一列代表起始 x、y 和 z 值,一列代表结束 x、y 和 z 值。 s
我必须使用 matplotlib 库绘制多条“曲线”,每条曲线由水平线段(甚至点)组成。 我通过 NaNs 分隔片段达到了这个目标。这是我的示例(工作)代码: from pylab import ar
我是一名优秀的程序员,十分优秀!