技术标签: 算法 线段树 二叉树 经典数据结构与算法整理 数据结构 # 线段树(模板)
线段树是一种非常强大的数据结构,它允许我们在对数时间内对数组的区间执行查询和更新操作。在这个教程中,我们将通过一个具体的例子——使用线段树来解决洛谷P3372 【模板】线段树 1“区间求和”和“区间更新”的问题来学习线段树的基础模板的应用。
我并不打算动动手指就能把线段树的工作原理描述得非常细致易懂。
如果读者完全不明白线段树,建议在拥有二叉树
的前置知识下,对着这里的代码敲一遍,相信你会豁然开朗,自己敲一遍比看别人说一千次还要有效。
线段树是一个二叉树,每个节点代表一个区间的聚合信息(例如区间和、最大值或最小值)。对于长度为n
的数组,线段树大约需要4 * n
的空间来存储(至于为什么是4 * n的空间,请看oi-wiki,这里不多赘述)。
构建线段树涉及将数组分解为多个区间,并将这些区间作为树的叶子节点。内部节点存储子区间的聚合值。构建树的过程是递归的,时间复杂度为O(n)
。
inline void buildTree(int l, int r, int node_idx = 1) {
tree[node_idx].l = l;
tree[node_idx].r = r;
if (l == r) {
tree[node_idx].sum = nums[l];
return;
}
int double_idx = (node_idx << 1);
int left_chil_idx = double_idx + 1;
int right_chil_idx = double_idx + 2;
int mid = l + ((r - l) >> 1);
buildTree(l, mid, left_chil_idx);
buildTree(mid + 1, r, right_chil_idx);
tree[node_idx].sum = tree[left_chil_idx].sum + tree[right_chil_idx].sum;
}
在这个函数中,我们从根节点开始,递归地将数组分成两部分,直到每个区间只包含一个元素。我们将数组的元素存储在树的叶子节点,然后计算内部节点的值,它是其左右子节点值的和。
down
函数,将之前保存在lazy
数组中没有真正进行更新操作的数字,真正执行一次更新操作。
在区间查询和区间更新操作中,如果访问到了某一个节点,并且还要继续深入访问其子节点,就应该将之前保存下来的懒惰更新的值进行真正的更新。
inline void down(int node_idx) {
if (lazy[node_idx] == 0) return;
int tree_left = tree[node_idx].l;
int tree_right = tree[node_idx].r;
int mid = tree_left + ((tree_right - tree_left) >> 1);
int double_idx = (node_idx << 1);
int left_chil_idx = double_idx + 1;
int right_chil_idx = double_idx + 2;
tree[left_chil_idx].sum += lazy[node_idx] * (mid - tree_left + 1);
tree[right_chil_idx].sum += lazy[node_idx] * (tree_right - mid);
lazy[left_chil_idx] += lazy[node_idx];
lazy[right_chil_idx] += lazy[node_idx];
lazy[node_idx] = 0;
}
区间查询是线段树的核心功能之一。我们可以使用线段树在O(log n)
时间内查询任意区间的聚合信息。
inline int queryRange(int query_left, int query_right, int node_idx = 1) {
int tree_left = tree[node_idx].l, tree_right = tree[node_idx].r;
// 完全不与查询目标的区间重合
if (tree_left > query_right || tree_right < query_left) return 0;
// 完全与查询目标的区间重合
if (tree_left >= query_left && tree_right <= query_right) {
return tree[node_idx].sum;
}
down(node_idx);
// 部分重合的情况下,我们要把查询目标的区间一分为二,分别查询左右两半。
int double_idx = (node_idx << 1);
int left_chil_idx = double_idx + 1;
int right_chil_idx = double_idx + 2;
int mid = tree_left + ((tree_right - tree_left) >> 1);
// 这里的mid有三种情况:
// 1.mid可能刚好位于[query_left, query_right]之间,刚好可以将其分为两半。
// 2.mid可能比原来的查询目标的右端点要大。
// 3.mid + 1可能比原来的查询目标的左端点要小。
// 因此直接写query(query_left, mid, left_chil_idx);的话
// 有多算一部分区间的风险。
int left_query = queryRange(query_left, min(query_right, mid), left_chil_idx);
int right_query = queryRange(max(query_left, mid + 1), query_right, right_chil_idx);
return left_query + right_query;
}
在查询函数中,我们首先检查当前区间是否与查询区间重叠。如果没有重叠,返回0。如果当前区间完全包含于查询区间中,返回当前节点的值。如果当前区间与查询区间部分重叠,则递归查询左右子树。
注意:
min(mid, r)
和max(mid + 1, l), r)
以防止错误修改原来的目标区间。线段树也支持区间更新,我们可以在O(log n)
时间内更新区间内所有元素的值。
inline void addRange(int query_left, int query_right, int val, int node_idx = 1) {
int tree_left = tree[node_idx].l, tree_right = tree[node_idx].r;
// 完全不与查询目标的区间重合
if (tree_left > query_right || tree_right < query_left) return;
// 完全与查询目标的区间重合
if (tree_left >= query_left && tree_right <= query_right) {
tree[node_idx].sum += val * (tree_right - tree_left + 1);
lazy[node_idx] += val; // 懒惰更新,只更新当前节点,打上懒惰更新中待更新的值,以后访问到再来更新。
return;
}
// 将以前懒惰更新中记录的值应用到子节点中。
down(node_idx);
int double_idx = (node_idx << 1);
int left_chil_idx = double_idx + 1;
int right_chil_idx = double_idx + 2;
int mid = tree_left + ((tree_right - tree_left) >> 1);
// 这里的min和max的使用的原因请看上面的queryRange函数。
addRange(query_left, min(query_right, mid), val, left_chil_idx);
addRange(max(query_left, mid + 1), query_right, val, right_chil_idx);
tree[node_idx].sum = tree[left_chil_idx].sum + tree[right_chil_idx].sum;
}
更新和查询的时候,我们会把区间分为两半,这意味着我们需要把查询目标区间分裂成两个子区间
那么现在可以想象,我们当前节点代表[tree_left, tree_right]
这一区间,而我们的查询目标区间是[query_left, query_right]
取mid
为中点,该节点的左右子节点分别代表这两个子区间:[tree_left, mid]
,[mid + 1, tree_right]
,我们要在这两个子节点中进行子查询
由于左右子节点分别代表:[tree_left, mid]
和[mid + 1, tree_right]
,它们可能会各占[query_left, query_right]
一部分,因此它们都有各自的子目标区间。
我们要将query_left
, query_right
两者与mid
进行比较,让左右子节点的查询获取正确的子目标区间的左右端点。
对于mid
和[query_left, query_right]
,有以下三种情况:
tree_left | … | query_left | … | mid | … | query_right | … | tree_right |
---|
说明:
...
表示区间中的其余部分,长度至少为1,下面的表格同理。[query_left, mid]
,[mid + 1, query_right]
刚好可以将查询目标分为两半而不出错误。tree_left | … | query_left | … | query_right | … | mid | … | tree_right |
---|
说明:
[query_left, mid]
,[mid + 1, query_right]
将会脱离原本的查询目标,导致查询结果偏大。tree_left | … | mid + 1 | … | query_left | … | query_right | … | tree_right |
---|
说明:
以上三种情况的表格展示了mid
在不同位置对查询区间的影响。因此代码实现的时候不能直接把mid
当成查询目标的区间的左右端点。
以下是如何使用线段树进行区间查询和更新的完整代码示例:
#include <iostream>
#include <vector>
using namespace std;
#define int long long
int n, m;
struct Node {
int l = 0, r = 0, sum = 0;
};
class SegmentTree {
public:
vector<Node> tree;
vector<int> lazy;
vector<int> nums;
inline void buildTree(int l, int r, int node_idx = 1) {
tree[node_idx].l = l;
tree[node_idx].r = r;
if (l == r) {
tree[node_idx].sum = nums[l];
return;
}
int double_idx = (node_idx << 1);
int left_chil_idx = double_idx + 1;
int right_chil_idx = double_idx + 2;
int mid = l + ((r - l) >> 1);
buildTree(l, mid, left_chil_idx);
buildTree(mid + 1, r, right_chil_idx);
tree[node_idx].sum = tree[left_chil_idx].sum + tree[right_chil_idx].sum;
}
inline void down(int node_idx) {
if (lazy[node_idx] == 0) return;
int tree_left = tree[node_idx].l;
int tree_right = tree[node_idx].r;
int mid = tree_left + ((tree_right - tree_left) >> 1);
int double_idx = (node_idx << 1);
int left_chil_idx = double_idx + 1;
int right_chil_idx = double_idx + 2;
tree[left_chil_idx].sum += lazy[node_idx] * (mid - tree_left + 1);
tree[right_chil_idx].sum += lazy[node_idx] * (tree_right - mid);
lazy[left_chil_idx] += lazy[node_idx];
lazy[right_chil_idx] += lazy[node_idx];
lazy[node_idx] = 0;
}
inline int queryRange(int query_left, int query_right, int node_idx = 1) {
int tree_left = tree[node_idx].l, tree_right = tree[node_idx].r;
// 完全不与查询目标的区间重合
if (tree_left > query_right || tree_right < query_left) return 0;
// 完全与查询目标的区间重合
if (tree_left >= query_left && tree_right <= query_right) {
return tree[node_idx].sum;
}
down(node_idx);
// 部分重合的情况下,我们要把查询目标的区间一分为二,分别查询左右两半。
int double_idx = (node_idx << 1);
int left_chil_idx = double_idx + 1;
int right_chil_idx = double_idx + 2;
int mid = tree_left + ((tree_right - tree_left) >> 1);
// 这里的mid有三种情况:
// 1.mid可能刚好位于[query_left, query_right]之间,刚好可以将其分为两半。
// 2.mid可能比原来的查询目标的右端点要大。
// 3.mid + 1可能比原来的查询目标的左端点要小。
// 因此直接写query(query_left, mid, left_chil_idx);的话
// 有多算一部分区间的风险。
int left_query = queryRange(query_left, min(query_right, mid), left_chil_idx);
int right_query = queryRange(max(query_left, mid + 1), query_right, right_chil_idx);
return left_query + right_query;
}
inline void addRange(int query_left, int query_right, int val, int node_idx = 1) {
int tree_left = tree[node_idx].l, tree_right = tree[node_idx].r;
// 完全不与查询目标的区间重合
if (tree_left > query_right || tree_right < query_left) return;
// 完全与查询目标的区间重合
if (tree_left >= query_left && tree_right <= query_right) {
tree[node_idx].sum += val * (tree_right - tree_left + 1);
lazy[node_idx] += val; // 懒惰更新,只更新当前节点,打上懒惰更新中待更新的值,以后访问到再来更新。
return;
}
// 将以前懒惰更新中记录的值应用到子节点中。
down(node_idx);
int double_idx = (node_idx << 1);
int left_chil_idx = double_idx + 1;
int right_chil_idx = double_idx + 2;
int mid = tree_left + ((tree_right - tree_left) >> 1);
// 这里的min和max的使用的原因请看上面的queryRange函数。
addRange(query_left, min(query_right, mid), val, left_chil_idx);
addRange(max(query_left, mid + 1), query_right, val, right_chil_idx);
tree[node_idx].sum = tree[left_chil_idx].sum + tree[right_chil_idx].sum;
// cout << "ADD RANGE HERE" <<endl;
}
explicit SegmentTree(const vector<int> &ns) : nums(ns) {
this->tree.resize(4 * n);
this->lazy.resize(4 * n);
buildTree(1, n);
}
};
inline int rd() {
int c = getchar(), f = 1, res = 0;
while (c > '9' || c < '0') {
if (c == '-') f = -1;
c = getchar();
}
while (c <= '9' && c >= '0') {
res = (res << 3) + (res << 1) + c - '0';
c = getchar();
}
return res * f;
}
signed main() {
n = rd(), m = rd();
vector<int> nums(n + 1);
for (int i = 1; i <= n; ++i) {
nums[i] = rd();
}
SegmentTree sgt(nums);
int type, x, y, k;
while (m--) {
type = rd();
x = rd(), y = rd();
if (type == 1) {
k = rd();
sgt.addRange(x, y, k);
} else {
printf("%lld\n", sgt.queryRange(x, y));
}
}
return 0;
}
在主函数中,我们首先读取数组长度和操作数,然后使用输入数组构建线段树。接下来,根据操作类型进行查询或更新。
线段树是解决区间查询和更新问题的非常有效的数据结构。理解它的关键点在于理解懒惰更新
这一个点,总的来说,这里的线段树其实就是一个完全二叉树,借助懒惰更新
实现了更低的复杂度,如果不熟悉线段树就对着代码重新敲一遍,原理很好理解。
文章浏览阅读3.8k次。1、将下载好的萤石js插件,添加到SoringBoot项目中。位置可参考下图所示。(容易出错的地方,在将js插件在html页面引入时,发生路径错误的问题)所以如果对页面中引入js的路径不清楚,可参考下图所示存放路径。2、将ezuikit.js引入到demo-live.html中。(可直接将如下代码复制到你创建的html页面中)<!DOCTYPE html><html lan..._ezuikit 测试的url
文章浏览阅读322次。第二步,在弹出的对话框选择,设备驱动—>PLC—>莫迪康—>ModbusRTU—>COM,根据配置软件选择的协议选期期,这里以此为例,然后点击“下一步”。第四步,把使用虚拟串口打勾(GPRS设备),根据需要选择要生成虚拟口,这里以选择KVCOM1为例,然后点击“下一步”设备ID即Modbus地址(1-255) 使用DTU时,为下485接口上的设备地址。第六步,Modbus的从机地址,与配置软件相同,这里以1为例,点击“下一步“第五步,Modbus的从机地址,与配置软件相同,这里以1为例,点击“下一步“_组态王ua
文章浏览阅读9.4k次,点赞22次,收藏19次。安装npm相当于安装node.js,Node.js已自带npm,安装Node.js时会一起安装,npm的作用就是对Node.js依赖的包进行管理,也可以理解为用来安装/卸载Node.js需要装的东西_npm安装配置
文章浏览阅读748次,点赞21次,收藏26次。大家好,小编来为大家解答以下问题,python基础训练100题,python入门100例题,现在让我们一起来看看吧!宝子们还在新手村练级的时候,不单要吸入基础知识,夯实自己的理论基础,还要去实际操作练练手啊!由于文章篇幅限制,不可能将100道题全部呈现在此除了这些,下面还有我整理好的基础入门学习资料,视频和讲解文案都很齐全,用来入门绝对靠谱,需要的自提。保证100%免费这不,贴心的我爆肝给大家整理了这份今天给大家分享100道Python练习题。大家一定要给我三连啊~
文章浏览阅读1k次。 为了在 Linux ( Ubuntu) 上安装sublime,一般大家都会选择常见的教程或是 sublime 官网教程,然而在国内这种方法可能失效。为此,需要用安装包安装。以下就是使用官网安装包安装的教程。打开 sublime 官网后,点击右上角 download, 或是直接访问点击打开链接,即可看到各个平台上的安装包。选择 Linux 64 位版并下载。下载后,打开终端,进入安装..._ubuntu 安装sumlime text打不开
文章浏览阅读563次,点赞13次,收藏6次。CrossOver24是一款类虚拟机软件,专为macOS和Linux用户设计。它的核心技术是Wine,这是一种在Linux和macOS等非Windows操作系统上运行Windows应用程序的开源软件。通过CrossOver24,用户可以在不购买Windows授权或使用传统虚拟机的情况下,直接在Mac或Linux系统上运行Windows软件和游戏。该软件还提供了丰富的功能,如自动配置、无缝集成和实时传输等,以实现高效的跨平台操作体验。
文章浏览阅读1.7k次。一个用聊天的方式让ChatGPT帮我写的线程安全的环形List_为什么gpt一写list就卡
文章浏览阅读336次。我们在前面的文章里曾写过Web应用中乱码产生的原因和处理方式,旧文回顾:深度揭秘乱码问题背后的原因及解决方式其中我们提到可以通过Filter的方式来设置请求和响应的encoding,来解..._filterconfig selectencoding
文章浏览阅读651次。转自:http://www.jb51.net/article/36480.htmencodeURI和decodeURI是成对来使用的,因为浏览器的地址栏有中文字符的话,可以会出现不可预期的错误,所以可以encodeURI把非英文字符转化为英文编码,decodeURI可以用来把字符还原回来_js encodeur decodeurl
文章浏览阅读1.9w次,点赞6次,收藏3次。前言在日常的Android开发当中,我们肯定要打包apk。但是今天我打包的时候遇到一个很奇怪的问题Android The destination folder does not exist or is not writeable,大意是目标文件夹不存在或不可写。出现问题的原因以及解决办法上面有说报错的中文大意是:目标文件夹不存在或不可写。其实问题就在我们的打包界面当中图中标红的Desti..._the destination folder does not exist or is not writeable
文章浏览阅读94次。一、配置代码编辑区的样式 <1>打开Eclipse,Help —> Install NewSoftware,界面如下: <2>点击add...,按下图所示操作: name:随意填写,Location:http://eclipse-color-th..._ecplise高大上设置
文章浏览阅读2.8k次。一,下载mysql:http://dev.mysql.com/downloads/mysql/; 打开页面之后,在Select Platform:下选择linux Generic,如果没有出现Linux的选项,请换一个浏览器试试。我用的谷歌版本不可以,换一个别的浏览器就行了,如果还是不行,需要换一个翻墙的浏览器。 二,下载完后解压缩并放到安装文件夹下: 1、MySQL-client-5.6.2_linux mysql 安装 mysql-5.6.24-1.linux_glibc2.5.x86_64.rpm-bundle