Java数据结构之线段树中的懒操作详解
一、问题提出
对于线段树,若要求对区间中的所有点都进行更新,可以引入懒操作。
懒操作包括区间更新和区间查询操作。
二、区间更新
对 [l,r] 区间进行更新,例如将 [l,r] 区间所有元素都更新为 v,步骤如下。
1.若当前节点区间被查询区间[l,r]覆盖,则仅对该节点进行更新并做懒标记,表示该节点已被更新,对该节点的子节点暂不更新。
2.判断是在左子树中查询还是在右子树中查询。在查询过程中,若当前节点带有懒标记,则将懒标记传给子节点(将当前节点的懒标记清除,将子节点更新并做懒标记),继续查找。
3.在返回时更新最值。
三、区间查询
带有懒标记的区间查询和普通的区间查询有所不同,在查询过程中若遇到节点有懒标记,则下传懒标记,继续查询。
四、实战
1.问题描述
2.输入
10
5 3 7 2 12 1 6 4 8 15
3 7 25
1 10
3.代码
package com.platform.modules.alg.alglib.p85; public class P85 { public String output = ""; private final int maxn = 100005; private final int inf = 0x3f3f3f3f; private int n; private int a[] = new int[maxn]; private node tree[] = new node[maxn * 4]; // 树结点存储数组 public P85() { for (int i = 0; i < tree.length; i++) { tree[i] = new node(); } } void lazy(int k, int v) { tree[k].mx = v; // 更新最值 tree[k].lz = v; // 做懒标记 } // 向下传递懒标记 void pushdown(int k) { lazy(2 * k, tree[k].lz); // 传递给左孩子 lazy(2 * k + 1, tree[k].lz); // 传递给右孩子 tree[k].lz = -1; // 清除自己的懒标记 } // 创建线段树,k表示存储下标,区间[l,r] void build(int k, int l, int r) { tree[k].l = l; tree[k].r = r; tree[k].lz = -1; // 初始化懒操作 if (l == r) { tree[k].mx = a[l]; return; } int mid, lc, rc; mid = (l + r) / 2; // 划分点 lc = k * 2; // 左孩子存储下标 rc = k * 2 + 1; // 右孩子存储下标 build(lc, l, mid); build(rc, mid + 1, r); tree[k].mx = Math.max(tree[lc].mx, tree[rc].mx); // 结点的最大值等于左右孩子最值的最大值 } // 将区间 [l,r] 修改更新为 v void update(int k, int l, int r, int v) { // 找到该区间 if (tree[k].l >= l && tree[k].r <= r) { lazy(k, v); // 更新并做懒标记 return; } if (tree[k].lz != -1) pushdown(k); // 懒标记下移 int mid, lc, rc; mid = (tree[k].l + tree[k].r) / 2; // 划分点 lc = k * 2; // 左孩子存储下标 rc = k * 2 + 1; // 右孩子存储下标 if (l <= mid) update(lc, l, r, v); // 到左子树更新 if (r > mid) update(rc, l, r, v);// 到右子树更新 tree[k].mx = Math.max(tree[lc].mx, tree[rc].mx); // 返回时修改更新最值 } // 求区间 [l,r] 的最值 int query(int k, int l, int r) { int Max = -inf; if (tree[k].l >= l && tree[k].r <= r) // 找到该区间 return tree[k].mx; if (tree[k].lz != -1) pushdown(k); // 懒标记下移 int mid, lc, rc; mid = (tree[k].l + tree[k].r) / 2; // 划分点 lc = k * 2; // 左孩子存储下标 rc = k * 2 + 1; // 右孩子存储下标 if (l <= mid) Max = Math.max(Max, query(lc, l, r)); // 到左子树查询 if (r > mid) Max = Math.max(Max, query(rc, l, r)); // 到右子树查询 return Max; } public String cal(String input) { int l, r; int i, v; String[] line = input.split("\n"); n = Integer.parseInt(line[0]); // 第 1 行:10 String[] nums = line[1].split(" "); // 第 2 行:5 3 7 2 12 1 6 4 8 15 for (i = 1; i <= n; i++) a[i] = Integer.parseInt(nums[i - 1]); build(1, 1, n); // 创建线段树 // 输入查询最值的区间 [l,r] 1 10 String[] range = line[2].split(" "); l = Integer.parseInt(range[0]); r = Integer.parseInt(range[1]); // 求区间[l..r]的最值 output += query(1, l, r) + "\n"; // 输入更新的区间值 l r v 第 3 行: 3 7 25 String[] change = line[3].split(" "); l = Integer.parseInt(change[0]); r = Integer.parseInt(change[1]); v = Integer.parseInt(change[2]); // 将区间 [l,r] 修改更新为 v update(1, l, r, v); // 求区间[l..r]的最值 第 4 行:1 10 range = line[4].split(" "); l = Integer.parseInt(range[0]); r = Integer.parseInt(range[1]); // 求区间 [l..r] 的最值 output += query(1, l, r) + "\n"; return output; } } // 结点 class node { int l; // l 表示区间左右端点 int r; // r 表示区间左右端点 int mx; // mx表示区间[l,r]的最值 int lz; // lz 懒标记 }
4.测试
以上就是Java数据结构之线段树中的懒操作详解的详细内容,更多关于Java线段树 懒操作的资料请关注猪先飞其它相关文章!
原文出处:https://blog.csdn.net/chengqiuming/article/details/127150347
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
- 这篇文章主要介绍了Java线程池中的各个参数如何合理设置操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-06-19
- 在Java中,我们可以利用多线程来最大化地压榨CPU多核计算的能力,下面这篇文章主要给大家介绍了关于java中多线程与线程池基本使用的相关资料,需要的朋友可以参考下...2021-09-13