线段树模板
文章目录
- 线段树
- 练习题目
- 线段树概念
- 区间维护
- 辅助函数
- 创建线段树 :build
- 修改线段树 :modify
- 查询线段树:query
- 全部代码
线段树
练习题目
洛谷题单
【模板】线段树 1
【模板】线段树 2
开关
扶苏的问题
线段树概念
线段树是一种高级数据结构,与树状数组一样,被用来处理区间查询,修改问题,并且线段树的最大优点是对动态数据的处理十分高效。
来看看线段树能处理的问题:
- 求区间的修改。给你一个区间,让你查询区间的左节点 , 右节点和增加量。如果用普通的数组,加上m次询问,则时间复杂度将会达到接近
O(mn)阶,是非常低效的。 - 区间和问题,查询,修改区间的元素,求和等等。使用普通数组对指定的区间求和,加之m次询问,则时间复杂度也会达到
O(mn),也可以使用前缀和求区间和,但是前缀和虽然高效,但是远没有线段树灵活,线段树能够处理的问题是非常多的。 - 线段树对于以上两种问题求解都具有
O(mlogn)的时间复杂度,是非常高效的。
线段树是具有以下形态的二叉树,其中树上的每个节点都是一个线段区间 。
看图可以发现线段树的几个特征:
这颗二叉树是采用分治法来划分区间,并且构建子树的,左右子树各一半。
这颗二叉树的每个节点都是一个线段区间,非叶子节点的线段区间是一段不相等的区间,叶子节点的线段区间的只包含一个元素。

区间维护
求区间维护是线段树最常用的使用方法之一,一共有五类函数:
- 辅助函数(前置准备,上移与下移): update ,pushdown
- 创建线段树 :build
- 修改线段树 :modify
- 查询线段树 :query
- 更新线段树 :update
辅助函数
inline void update(int root)
{node[root].sum = node[root * 2].sum + node[root * 2 + 1].sum;//将左子树和右子树的值合并
}inline void pushdown(int root)
{int lazy = node[root].lazy;node[root * 2].lazy += lazy;node[root * 2].sum += (node[root * 2].r - node[root * 2].l + 1) * lazy;//下发懒惰标记node[root * 2 + 1].lazy += lazy;node[root * 2 + 1].sum += (node[root * 2 + 1].r - node[root * 2 + 1].l + 1) * lazy;//下发懒惰标记node[root].lazy = 0;//清空懒惰标记
}
创建线段树 :build
void build_tree(int root, int l, int r)
{node[root].l = l;//封装左区间node[root].r = r;//封装右区间if (l == r){node[root].sum = a[l];//大小与需要相同,就赋值return;}int mid = (l + r) >> 1;build_tree(root * 2, l, mid);//递归左子树build_tree(root * 2 + 1, mid + 1, r);//递归右子树update(root);//合并左右子树
}
修改线段树 :modify
void modify(int root, int l, int r, int k)
{if (node[root].l == l && node[root].r == r){node[root].sum += (r - l + 1) * k;//值加上区间内增加的值node[root].lazy += k;//懒惰标记return;}pushdown(root);//下发懒惰标记,因为接下来要访问左右子树int mid = (node[root].l + node[root].r) >> 1;//取中间节点if (r <= mid){modify(root * 2, l, r, k);//全在左边的情况,递归左子树}else if (l > mid)全在右边的情况,递归右子树{modify(root * 2 + 1, l, r, k);}else//负责左右都递归{modify(root * 2, l, mid, k);modify(root * 2 + 1, mid + 1, r, k);}update(root);//因为修改了左右子树,所以要合并左右子树return;
}
查询线段树:query
long long query(int root, int l, int r)
{if (node[root].l == l && node[root].r == r){return node[root].sum;//如果区间正好吻合,则返回原值}pushdown(root);//下发懒惰标记,因为接下来要访问左右子树int mid = (node[root].l + node[root].r) >> 1;if (r <= mid)//同modify中的递归{return query(root * 2, l, r);}else if (l > mid){return query(root * 2 + 1, l, r);}return query(root * 2, l, mid) + query(root * 2 + 1, mid + 1, r);//这里要返回和
}
全部代码
#include <bits/stdc++.h>
using namespace std;struct tree
{int l, r;long long sum, lazy;
} node[300010];int n, m;
int a[100010];inline void update(int root)
{node[root].sum = node[root * 2].sum + node[root * 2 + 1].sum;//将左子树和右子树的值合并
}inline void pushdown(int root)
{int lazy = node[root].lazy;node[root * 2].lazy += lazy;node[root * 2].sum += (node[root * 2].r - node[root * 2].l + 1) * lazy;//下发懒惰标记node[root * 2 + 1].lazy += lazy;node[root * 2 + 1].sum += (node[root * 2 + 1].r - node[root * 2 + 1].l + 1) * lazy;//下发懒惰标记node[root].lazy = 0;//清空懒惰标记
}
void build_tree(int root, int l, int r)
{node[root].l = l;//封装左区间node[root].r = r;//封装右区间if (l == r){node[root].sum = a[l];//大小与需要相同,就赋值return;}int mid = (l + r) >> 1;build_tree(root * 2, l, mid);//递归左子树build_tree(root * 2 + 1, mid + 1, r);//递归右子树update(root);//合并左右子树
}void modify(int root, int l, int r, int k)
{if (node[root].l == l && node[root].r == r){node[root].sum += (r - l + 1) * k;//值加上区间内增加的值node[root].lazy += k;//懒惰标记return;}pushdown(root);//下发懒惰标记,因为接下来要访问左右子树int mid = (node[root].l + node[root].r) >> 1;//取中间节点if (r <= mid){modify(root * 2, l, r, k);//全在左边的情况,递归左子树}else if (l > mid)全在右边的情况,递归右子树{modify(root * 2 + 1, l, r, k);}else//负责左右都递归{modify(root * 2, l, mid, k);modify(root * 2 + 1, mid + 1, r, k);}update(root);//因为修改了左右子树,所以要合并左右子树return;
}long long query(int root, int l, int r)
{if (node[root].l == l && node[root].r == r){return node[root].sum;//如果区间正好吻合,则返回原值}pushdown(root);//下发懒惰标记,因为接下来要访问左右子树int mid = (node[root].l + node[root].r) >> 1;if (r <= mid)//同modify中的递归{return query(root * 2, l, r);}else if (l > mid){return query(root * 2 + 1, l, r);}return query(root * 2, l, mid) + query(root * 2 + 1, mid + 1, r);//这里要返回和
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];}build_tree(1, 1, n);//建树while (m--){long long op, x, y, k;cin >> op >> x >> y;if (op == 1){cin >> k;modify(1, x, y, k);//区间修改}else if (op == 2){cout << query(1, x, y) << endl;//区间查询}}return 0;
}
相关文章:
线段树模板
文章目录 线段树练习题目线段树概念区间维护辅助函数创建线段树 :build修改线段树 :modify查询线段树:query 全部代码 线段树 练习题目 洛谷题单 【模板】线段树 1 【模板】线段树 2 开关 扶苏的问题 线段树概念 线段树是一种高级数据结构&a…...
【TypeScript】知识点梳理(三)
#void前面提到了代表空,但有个特殊情况,是空不是空,细谈是取舍,但我们不深究hhh# 代码示例: type func () > voidconst f1: func function() {return true; } 定义了空,返回非空值,理论…...
题解:SP1741 TETRIS3D - Tetris 3D
这是一道二维线段树(树套树)标记永久化的模版题 前置知识点(来自董晓算法) 好,现在开始我们的分析: 题意简述: 在一个二维平面内,有给定的坐标,在这个坐标范围内加上…...
EWSTM8 IAR for STM8 软件分享
1. 软件简介 EWSTM8,即 IAR for STM8,全称为 IAR Embedded Workbench for STM8,它是 IAR ARM 嵌入式工作台之一,用于开发 STM8。IAR 有多个不同名的版本,对应不同的开发对象。 EWSTM8最新版本为V3.11(202…...
非机动车检测数据集 4类 5500张 电动三轮自行车 voc yolo
非机动车检测数据集 4类 5500张 电动三轮自行车 voc yolo 非机动车检测数据集介绍 数据集名称 非机动车检测数据集 (Non-Motorized Vehicle Detection Dataset) 数据集概述 该数据集专为训练和评估基于YOLO系列目标检测模型(包括YOLOv5、YOLOv6、YOLOv7等&#x…...
Chromium 中JavaScript FileReader API接口c++代码实现
FileReader 备注: 此特性在 Web Worker 中可用。 FileReader 接口允许 Web 应用程序异步读取存储在用户计算机上的文件(或原始数据缓冲区)的内容,使用 File 或 Blob 对象指定要读取的文件或数据。 文件对象可以从用户使用 <…...
k8s 中微服务之 MetailLB 搭配 ingress-nginx 实现七层负载
目录 1 MetailLB 搭建 1.1 MetalLB 的作用和原理 1.2 MetalLB功能 1.3 部署 MetalLB 1.3.1 创建deployment控制器和创建一个服务 1.3.2 下载MealLB清单文件 1.3.3 使用 docker 对镜像进行拉取 1.3.4 将镜像上传至私人仓库 1.3.5 将官方仓库地址修改为本地私人地址 1.3.6 运行清…...
南昌网站建设让你的企业网站更具竞争力
南昌网站建设让你的企业网站更具竞争力 在当今竞争激烈的市场环境中,一个高质量的网站不仅是企业形象的展示平台,更是吸引客户、提升业绩的重要工具。南昌作为江西的省会城市,互联网产业的蓬勃发展为企业网站建设提供了良好的机遇。 首先&am…...
【重学 MySQL】五十三、MySQL数据类型概述和字符集设置
【重学 MySQL】五十三、MySQL数据类型概述和字符集设置 MySQL数据类型概述MySQL字符集设置注意事项 MySQL数据类型概述 MySQL是一个流行的关系型数据库管理系统,它支持多种数据类型,以满足不同数据处理和存储的需求。理解并正确使用这些数据类型对于提高…...
《计算机原理与系统结构》学习系列——计算机的算数运算(上)
系列文章目录 目录 ALU行波进位加法器超前进位加法器整数运算加减法乘法无符号数相乘N位乘法数的工作流程N位乘法器改进:硬件资源更快速的乘法 MIPS中的乘法除法 32位除法器流程除法器改进 更快速的除法 MIPS中的除法总结 ALU ALU功能:对a,…...
如何在华为云服务器查看IP地址,及修改服务器登录密码!!!
1.在华为云服务器查看IP地址 (1).第一步: 先找到控制台 (2).第二步: 点击华为云Flexus云服务 (3)第三步: 找到公网IP,就找到华为云服务器IP地址啦。 注意:在操作以上步骤的前提是要已注册华为云账号及购买云服务器…...
JAVA并发编程高级——JDK 新增的原子操作类 LongAdder
LongAdder 简单介绍 前面讲过,AtomicLong通过CAS提供了非阻塞的原子性操作,相比使用阻塞算法的同步器来说它的性能已经很好了,但是JDK开发组并不满足于此。使用AtomicLong 时,在高并发下大量线程会同时去竞争更新同一个原子变量,但是由于同时只有一个线程的CAS操作会成功,…...
常见的基础系统
权限管理系统支付系统搜索系统报表系统API网关系统待定。。。 Java 优质开源系统设计项目 来源:Java 优质开源系统设计项目 | JavaGuide 备注:github和gitee上可以搜索到相关项目...
在 window 系统下安装 Ubuntu (虚拟机)
文章目录 零、Ubuntu 和 Vmware workstation 资源一、下载 Ubuntu二、下载 Vmware Workstation Pro三、安装 Vmware Workstation Pro四、创建虚拟机五、配置 Ubuntu 零、Ubuntu 和 Vmware workstation 资源 如果觉得自己下载 Ubuntu 和 Vmware workstation 麻烦,也…...
鸿蒙开发(NEXT/API 12)【访问控制应用权限管控概述】程序访问控制
默认情况下,应用只能访问有限的系统资源。但某些情况下,应用存在扩展功能的诉求,需要访问额外的系统数据(包括用户个人数据)和功能,系统也必须以明确的方式对外提供接口来共享其数据或功能。 系统通过访问…...
(10)MATLAB莱斯(Rician)衰落信道仿真1
文章目录 前言一、莱斯分布随机变量二、仿真代码与结果1.仿真代码2.仿真结果画图 后续 前言 首先给出莱斯衰落信道模型,引入了莱斯因子K,并给出莱斯分布的概率密度函数公式。然后导出莱斯分布随机变量的仿真表示式,建立MATLAB仿真代码&#…...
什么是重卡充电桩?
有什么广告?没有广告,纯纯的介绍。 在政策与市场双重驱动下,充电桩市场已经开启加速模式,行业的火苗越烧越旺。同时,随着新能源重卡的广泛普及,重卡充电桩也迎来了新的发展机遇。 此种背景下 ,…...
模拟实现消息队列(基于SpringBoot实现)
提要:此处的消息队列是仿照RabbitMQ实现(参数之类的),实现一些基本的操作:创建/销毁交互机(exchangeDeclare,exchangeDelete),队列(queueDeclare,…...
C语言:预编译过程的剖析
目录 一.预定义符号和#define定义常量 二.#define定义宏 三.宏和函数的对比 四、#和##运算符 五、条件编译 在之前,我们已经介绍了.c文件在运行的过程图解,大的方面要经过两个方面。 一、翻译环境 1.预处理(预编译) 2.编译 3…...
算法——单调栈
单调栈: 保持栈内的元素始终递增或递减。 单调递增 待处理数组{1,5,2,5,7,2,8} public void sameyIncrease(int[] nums) {Stack<Integer> stack new Stack<>();for(int i 0; i < nums.length; i) {//当栈空的时候可以直接进栈或者要进栈的数大于…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
