线段树模板
文章目录
- 线段树
- 练习题目
- 线段树概念
- 区间维护
- 辅助函数
- 创建线段树 :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) {//当栈空的时候可以直接进栈或者要进栈的数大于…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
