线段树讲解

news/2024/11/8 9:32:27/

0、引入

假设给定一个长度为 1001 的数组,即下标 0 到 1000。

现在需要完成 3 个功能:

add(1, 200, 6); //给下标 1 到 200 的每个数都加 6;
update(7, 375, 4); //下标 7 到 375 的数全部修改为 4
query(3, 999); //下标 3 到 999 所有数的累加和

如果暴力解,则上述的每个功能的时间复杂度都为 O(N)O(N)O(N);而如果是使用线段树,则可以做到时间复杂度 O(logN)O(logN)O(logN)

1、简介

为了简单起见,涉及到线段树的数组下标从 1 开始。

线段树是一种支持范围整体修改范围整体查询的数据结构。

首先,希望将一个数组分成树状
请添加图片描述
怎么做到呢?申请一个数组,只要满足下标 iii 的父节点是 i/2i/2i/2 ,左孩子为 i∗2i * 2i2,右孩子为 i∗2+1i * 2 + 1i2+1 就能转换为一个树状。

请添加图片描述
那么 申请的数组到底要准备多长呢? 如果原数组长度为 NNN,则准备 4N4N4N 长度是够用的,包括一些用不上的位置。

这个结论怎么来的呢?

首先,当数组长度为 2x2^x2x 次方时最省空间,因为没有废的空间。例长度为 4 时,申请 7 长度的的数组(0位置不用,下标1到7)即可, 就算包含弃而不用的 0 位置,也只需要 8 长度的空间。

当数组长度为 2x+12^x+12x+1 时,最费空间,但是也不会超过 4N4N4N 长度。

2、懒更新:add

例如要给 3 ~ 874 下标范围的每个值都 +5,懒更新就是当树状数组中的某个范围包含在 3 ~ 874 时,就不再往下下发任务,而是就地处理。即只要树状中包含的数组范围没有完全包含在3 ~ 874中,就下发任务。
请添加图片描述
可以认为当一个任务到来时,卡着左边界和右边界各下放一次,中间该懒的就懒了(不往下发),时间复杂度 O(logn)O(logn)O(logn) 级别,非常快。


具体来说,就是一开始准备一个累加和数组(即4N4N4N长度)和一个懒更新数组,初始时:
请添加图片描述
如果来了一个任务 add(1,4,3),即1~4下标范围的每个数都+3,对应到树状中,树根的范围已经完全包含在这个任务要求的范围中了,于是不再下发任务,而是就地处理。于是,懒更新数组更新为:
请添加图片描述
如果接着又来了一个任务 add(1,2,4)。首先,先看是否有懒信息,当前的情况是有,于是将该信息下发一层(下发到1-2 和 3-4),然后清空本层的懒信息:
在这里插入图片描述
然后执行任务 add(1,2,4),这个任务只需要分给 1-2,于是1-2 这个格子就得到了每个数+4的任务,先检查之前1-2 是否有懒信息,发现有,于是将当前的懒信息往下下发一层(1-1 和 2-2),将自己清空,发现任务1-2 包含了当前的1-2,于是拦住这个任务,1-2 的懒信息更新为4:
在这里插入图片描述
在这里插入图片描述
也就是如果当前层有懒信息,需要先将任务往下发一层然后再执行新任务

3、懒更新:update

change 数组和 lazy 数组、sum 数组一样,都是原数组长度的 4 倍,只是用于记录原数组的不同信息。

为什么需要一个布尔类型的数组 update 呢?

例如原数组下标为1 ~ 500:

  • sum[1] = 100 万 表示1 ~ 500 的累加和为 100万,而 sum[1] = 0 表示累加和为0,没有歧义;
  • add[1] = 7 表示 1 ~ 500 每个数加7,而 add[1] = 0 无论是每个数都加0 还是 表示没有懒信息 都是可以的;
  • change[1] = 7 表示1 ~ 500 的每个数都修改为7;但是 change[1] = 0 就有歧义,不知道是1 ~ 500 每个数都变成 0 还是 1 ~ 500 的每个数没有update信息,造成了歧义。

所以再增加一个布尔类型的 update 数组,如果 update[1] = 1, change[1] = 0 就表示 1 ~ 500 的每个数变成0;而update = 0, change[1] = 0 表示没有关于 update 的懒信息,原数组该什么样就什么样。

4、懒更新:query

当需要查询区间的累加和时,要先将区间的其他任务(更新、累加)进行下发,然后执行查询任务。

5、解决的问题

线段树是用于解决区间增加、区间更新和区间查询的问题。

6、线段树代码实现

public class SegmentTree {public static class SegmentTree {private int MAXN;private int[] arr; //缓存数组,原序列的信息从0开始,但在arr里是从1开始的,0位置不用private int[] sum; //模拟线段树维护区间和,原数组arr长度扩4倍private int[] lazy; //为累加和懒惰标记,原数组arr长度扩4倍private int[] change; //范围上所有的值被更新成的值private boolean[] update; //update信息的慵懒标记,是否有修改信息public SegmentTree(int[] origin) {MAXN = origin.length + 1;arr = new int[MAXN]; // arr[0]不用,从1开始使用for (int i = 1; i < MAXN; i++) {arr[i] = origin[i - 1];}sum = new int[MAXN << 2]; // 用来支持脑补概念中,某一个范围的累加和信息lazy = new int[MAXN << 2]; // 用来支持脑补概念中,某一个范围沒有往下傳遞的纍加任務change = new int[MAXN << 2]; // 用来支持脑补概念中,某一个范围有没有更新操作的任务update = new boolean[MAXN << 2]; // 用来支持脑补概念中,某一个范围更新任务,更新成了什么}private void pushUp(int rt) { //树状中根的累加和 = 左孩子的累加和 + 右孩子的累加和sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; //sum[i] = sum[2*i] + sum[2*i+1]}// 之前的,所有懒增加,和懒更新,从父范围,发给左右两个子范围// 分发策略是什么// rt表示父节点的下标,ln表示左子树元素结点个数,rn表示右子树结点个数private void pushDown(int rt, int ln, int rn) {//先检查“更新”信息,再检查“累加”信息//之所以这样,是因为在update()函数操作的时候会将lazy信息清空//如果既有update信息又有lazy信息,则说明最近一次更新到目前为止又攒了几个累加信息//所以在分发任务的时候要先检查“更新”,再检查“累加”,因为两者同时存在时,更新是早的,累加是后攒起来的if (update[rt]) { //如果父节点有“更新”信息,则下发一级//左右孩子都有更新信息update[rt << 1] = true;update[rt << 1 | 1] = true;//左右孩子都改成父节点的change信息change[rt << 1] = change[rt];change[rt << 1 | 1] = change[rt];//左右孩子的累加和(lazy)信息都清空,被update信息覆盖掉lazy[rt << 1] = 0;lazy[rt << 1 | 1] = 0;//左右孩子的累加和重新计算sum[rt << 1] = change[rt] * ln;sum[rt << 1 | 1] = change[rt] * rn;//父节点的“更新”信息清空update[rt] = false;}if (lazy[rt] != 0) { //有懒信息,向下分发一级:更新左右孩子的累加和信息和和懒信息lazy[rt << 1] += lazy[rt]; //左孩子的懒信息加上父节点的懒信息sum[rt << 1] += lazy[rt] * ln; //左孩子的累加和更新加上左边节点个数 * 懒信息lazy[rt << 1 | 1] += lazy[rt]; //右孩子的懒信息加上父节点的懒信息sum[rt << 1 | 1] += lazy[rt] * rn; //右孩子的累加和更新lazy[rt] = 0; //孩子承接了懒任务,所以父节点的懒信息清零}}// 该函数就是将原数组建立成一个树状结构,最大范围一定在 1 这个下标上// 在初始化阶段,先把sum数组,填好// 在arr[l~r]范围上,去build,1~N,// rt : 这个范围在sum中的下标public void build(int l, int r, int rt) { //l~r这个范围在sum数组中对应的下标为rtif (l == r) { //叶节点,只有一个数,将原数组中的l范围的值填到sum[rt]即可sum[rt] = arr[l];return;}int mid = (l + r) >> 1; //求出中点build(l, mid, rt << 1); //左孩子build(mid + 1, r, rt << 1 | 1); //右孩子pushUp(rt); //计算出左孩子和右孩子后,将左右孩子相加得到根节点的值}//任务:将L到R范围上的数都修改为C//目前到了rt这个下标的节点,它代表的是l到r区间public void update(int L, int R, int C, int l, int r, int rt) {//任务把此时的范围全部包括了if (L <= l && r <= R) {update[rt] = true; //设置“更新”操作的懒信息change[rt] = C; //“更新”操作的懒信息sum[rt] = C * (r - l + 1); //直接设置累加和lazy[rt] = 0; //因为已经进行了“更新”操作,所以之前累加和的懒信息全部清空return;}// 当前任务躲不掉,无法懒更新,要往下发int mid = (l + r) >> 1;pushDown(rt, mid - l + 1, r - mid); //检查是否有老任务要先下发if (L <= mid) {update(L, R, C, l, mid, rt << 1);}if (R > mid) {update(L, R, C, mid + 1, r, rt << 1 | 1);}pushUp(rt);}// L到R范围上的每个数都加C (即任务),是固定的// 当前来到的格子是rt,表示的范围是l到rpublic void add(int L, int R, int C, int l, int r, int rt) {// 任务如果把此时的范围全包了!//如任务为[3,874]范围的每个数都加5,而当前来到的是树状的3位置的[251,500]区间//因为[251,500] 包含在[3,874],则懒更新,即直接在这里处理任务,而不是下发任务if (L <= l && r <= R) {sum[rt] += C * (r - l + 1); //l到r范围共r-l+1个数,则累加和变大 C*(r-l+1)lazy[rt] += C; //懒更新信息return;}// 任务没有把你全包!// l  r  mid = (l+r)/2int mid = (l + r) >> 1;//先处理老任务pushDown(rt, mid - l + 1, r - mid); //如果有懒信息先下发一级再处理当前的任务//然后处理新任务if (L <= mid) { //任务需要发给左边add(L, R, C, l, mid, rt << 1);}if (R > mid) { //任务需要发给右边add(L, R, C, mid + 1, r, rt << 1 | 1);}pushUp(rt); //调整自己的累加和}// 任务:查询L到R范围上的累加和// 目前到了下标为rt的节点,代表的区间是l到rpublic long query(int L, int R, int l, int r, int rt) {if (L <= l && r <= R) {return sum[rt];}int mid = (l + r) >> 1;//将之前缓存的任务先下发在处理查询pushDown(rt, mid - l + 1, r - mid);long ans = 0;if (L <= mid) { //任务需要分给左边,左边的查询结果ans += query(L, R, l, mid, rt << 1);}if (R > mid) { //任务需要分给右边,右边的查询结果ans += query(L, R, mid + 1, r, rt << 1 | 1);}return ans;}}//纯暴力public static class Right {public int[] arr;public Right(int[] origin) {arr = new int[origin.length + 1];for (int i = 0; i < origin.length; i++) {arr[i + 1] = origin[i];}}public void update(int L, int R, int C) {for (int i = L; i <= R; i++) {arr[i] = C;}}public void add(int L, int R, int C) {for (int i = L; i <= R; i++) {arr[i] += C;}}public long query(int L, int R) {long ans = 0;for (int i = L; i <= R; i++) {ans += arr[i];}return ans;}}public static int[] genarateRandomArray(int len, int max) {int size = (int) (Math.random() * len) + 1;int[] origin = new int[size];for (int i = 0; i < size; i++) {origin[i] = (int) (Math.random() * max) - (int) (Math.random() * max);}return origin;}public static boolean test() {int len = 100;int max = 1000;int testTimes = 5000;int addOrUpdateTimes = 1000;int queryTimes = 500;for (int i = 0; i < testTimes; i++) {int[] origin = genarateRandomArray(len, max);SegmentTree seg = new SegmentTree(origin);int S = 1;int N = origin.length;int root = 1;seg.build(S, N, root);Right rig = new Right(origin);for (int j = 0; j < addOrUpdateTimes; j++) {int num1 = (int) (Math.random() * N) + 1;int num2 = (int) (Math.random() * N) + 1;int L = Math.min(num1, num2);int R = Math.max(num1, num2);int C = (int) (Math.random() * max) - (int) (Math.random() * max);if (Math.random() < 0.5) { //0.5的概率执行addseg.add(L, R, C, S, N, root);rig.add(L, R, C);} else { //0.5的概率执行updateseg.update(L, R, C, S, N, root);rig.update(L, R, C);}}for (int k = 0; k < queryTimes; k++) {int num1 = (int) (Math.random() * N) + 1;int num2 = (int) (Math.random() * N) + 1;int L = Math.min(num1, num2);int R = Math.max(num1, num2);long ans1 = seg.query(L, R, S, N, root);long ans2 = rig.query(L, R);if (ans1 != ans2) {return false;}}}return true;}public static void main(String[] args) {int[] origin = { 2, 1, 1, 2, 3, 4, 5 };SegmentTree seg = new SegmentTree(origin);int S = 1; // 整个区间的开始位置,规定从1开始,不从0开始 -> 固定int N = origin.length; // 整个区间的结束位置,规定能到N,不是N-1 -> 固定int root = 1; // 整棵树的头节点位置,规定是1,不是0 -> 固定int L = 2; // 操作区间的开始位置 -> 可变int R = 5; // 操作区间的结束位置 -> 可变int C = 4; // 要加的数字或者要更新的数字 -> 可变// 区间生成,必须在[S,N]整个范围上buildseg.build(S, N, root);// 区间修改,可以改变L、R和C的值,其他值不可改变seg.add(L, R, C, S, N, root);// 区间更新,可以改变L、R和C的值,其他值不可改变seg.update(L, R, C, S, N, root);// 区间查询,可以改变L和R的值,其他值不可改变long sum = seg.query(L, R, S, N, root);System.out.println(sum);System.out.println("对数器测试开始...");System.out.println("测试结果 : " + (test() ? "通过" : "未通过"));}
}

http://www.ppmy.cn/news/9947.html

相关文章

Python数据分析——pandas

1.pandas简介 pandas 是 Python 的核心数据分析支持库&#xff0c;提供了快速、灵活、明确的数据结构&#xff0c;旨在简单、直观地处理关系型、标记型数据。pandas 的目标是成为 Python 数据分析实践与实战的必备高级工具&#xff0c;其长远目标是成为最强大、最灵活、可以支持…

【小知识点】Python 随机生成一个汉字,提供了多种办法,目的竞然是用于创建头像

文章目录需求来源随机汉字随机生成常用汉字需求来源 在编写爬虫训练场 项目时&#xff0c;碰到一个随机头像的需求&#xff0c;这里用汉字去随机生成。 模拟的效果如下所示&#xff0c;输入一组汉字&#xff0c;然后返回一张图片。 接口地址如下所示&#xff1a; https://ui…

Struts2获取表单数据

Struts2获取表单数据Struts2获取表单数据1、原始Servlet方法2、属性封装3、表达式封装4、模型驱动封装Struts2获取表单数据 在Struts2中获取表单数据或提交路径的参数值的方式有4种。如下&#xff1a; 原始Servlet方法属性封装表达式封装模型驱动封装 1、原始Servlet方法 该…

FME对调查云平台完成变更调查照片的批量迁移

目录 前言 二、实际步骤 1.准备基础数据 2.模拟登录 3.获取图斑标识码 4.获取图形信息 5.通过空间位置关系过滤不合格照片 5.通过深度学习模型过滤照片特征错误图斑 6.照片迁移 总结 前言 又到了一年一度国土变更调查的苦日子&#xff0c;因为项目规则原因&#xff0c;…

【web安全】——web渗透的前缀知识

作者名&#xff1a;Demo不是emo 主页面链接&#xff1a;主页传送门 创作初心&#xff1a;舞台再大&#xff0c;你不上台&#xff0c;永远是观众&#xff0c;没人会关心你努不努力&#xff0c;摔的痛不痛&#xff0c;他们只会看你最后站在什么位置&#xff0c;然后羡慕或鄙夷座…

OPC Expert v8.1.2211 Crack

像专业人士一样解决您的 OPC 和 DCOM 连接问题 [无需经验] 快速修复 OPC 和 DCOM 错误 使用 OPC Expert&#xff0c;您无需任何经验即可解决和修复 OPC 连接问题。OPC Expert 为您完成繁重的工作&#xff0c;以快速自动诊断 OPC 和 DCOM 问题……Ω578867473而且还不止于此。OP…

阳康后的第一篇博客,先来几道恶心二进制编程题

目录 一、统计二进制中1的个数 二、打印整数二进制的奇数位和偶数位 三、两个整数二进制位不同个数 一、统计二进制中1的个数 这是一道牛客网OJ题&#xff0c;感兴趣的话可以先做一遍再看解析哦 -> 牛客网的OJ链接 注意&#xff1a;上面的牛客网是接口型&#xff0c;不需…

JDBC连接数据库

JDBC&#xff08;Java DataBase Connectivity&#xff09;&#xff0c;简单来讲JDBC是利用Java语言或程序连接并且访问数据库的一门技术&#xff0c;是Java语言中用来规范客户端程序如何访问数据库的应用程序接口&#xff0c;提供了查询和更新数据库操作方法&#xff0c;通常是…