当前位置: 首页 > news >正文

线段树模板

文章目录

  • 线段树
      • 练习题目
      • 线段树概念
      • 区间维护
        • 辅助函数
        • 创建线段树 :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;
}

相关文章:

线段树模板

文章目录 线段树练习题目线段树概念区间维护辅助函数创建线段树 &#xff1a;build修改线段树 &#xff1a;modify查询线段树&#xff1a;query 全部代码 线段树 练习题目 洛谷题单 【模板】线段树 1 【模板】线段树 2 开关 扶苏的问题 线段树概念 线段树是一种高级数据结构&a…...

【TypeScript】知识点梳理(三)

#void前面提到了代表空&#xff0c;但有个特殊情况&#xff0c;是空不是空&#xff0c;细谈是取舍&#xff0c;但我们不深究hhh# 代码示例&#xff1a; type func () > voidconst f1: func function() {return true; } 定义了空&#xff0c;返回非空值&#xff0c;理论…...

题解:SP1741 TETRIS3D - Tetris 3D

这是一道二维线段树&#xff08;树套树&#xff09;标记永久化的模版题 前置知识点&#xff08;来自董晓算法&#xff09; 好&#xff0c;现在开始我们的分析&#xff1a; 题意简述&#xff1a; 在一个二维平面内&#xff0c;有给定的坐标&#xff0c;在这个坐标范围内加上…...

EWSTM8 IAR for STM8 软件分享

1. 软件简介 EWSTM8&#xff0c;即 IAR for STM8&#xff0c;全称为 IAR Embedded Workbench for STM8&#xff0c;它是 IAR ARM 嵌入式工作台之一&#xff0c;用于开发 STM8。IAR 有多个不同名的版本&#xff0c;对应不同的开发对象。 EWSTM8最新版本为V3.11&#xff08;202…...

非机动车检测数据集 4类 5500张 电动三轮自行车 voc yolo

非机动车检测数据集 4类 5500张 电动三轮自行车 voc yolo 非机动车检测数据集介绍 数据集名称 非机动车检测数据集 (Non-Motorized Vehicle Detection Dataset) 数据集概述 该数据集专为训练和评估基于YOLO系列目标检测模型&#xff08;包括YOLOv5、YOLOv6、YOLOv7等&#x…...

Chromium 中JavaScript FileReader API接口c++代码实现

FileReader 备注&#xff1a; 此特性在 Web Worker 中可用。 FileReader 接口允许 Web 应用程序异步读取存储在用户计算机上的文件&#xff08;或原始数据缓冲区&#xff09;的内容&#xff0c;使用 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 运行清…...

南昌网站建设让你的企业网站更具竞争力

南昌网站建设让你的企业网站更具竞争力 在当今竞争激烈的市场环境中&#xff0c;一个高质量的网站不仅是企业形象的展示平台&#xff0c;更是吸引客户、提升业绩的重要工具。南昌作为江西的省会城市&#xff0c;互联网产业的蓬勃发展为企业网站建设提供了良好的机遇。 首先&am…...

【重学 MySQL】五十三、MySQL数据类型概述和字符集设置

【重学 MySQL】五十三、MySQL数据类型概述和字符集设置 MySQL数据类型概述MySQL字符集设置注意事项 MySQL数据类型概述 MySQL是一个流行的关系型数据库管理系统&#xff0c;它支持多种数据类型&#xff0c;以满足不同数据处理和存储的需求。理解并正确使用这些数据类型对于提高…...

《计算机原理与系统结构》学习系列——计算机的算数运算(上)

系列文章目录 目录 ALU行波进位加法器超前进位加法器整数运算加减法乘法无符号数相乘N位乘法数的工作流程N位乘法器改进&#xff1a;硬件资源更快速的乘法 MIPS中的乘法除法 32位除法器流程除法器改进 更快速的除法 MIPS中的除法总结 ALU ALU功能&#xff1a;对a&#xff0c;…...

如何在华为云服务器查看IP地址,及修改服务器登录密码!!!

1.在华为云服务器查看IP地址 (1).第一步&#xff1a; 先找到控制台 (2).第二步&#xff1a; 点击华为云Flexus云服务 (3)第三步&#xff1a; 找到公网IP&#xff0c;就找到华为云服务器IP地址啦。 注意&#xff1a;在操作以上步骤的前提是要已注册华为云账号及购买云服务器…...

JAVA并发编程高级——JDK 新增的原子操作类 LongAdder

LongAdder 简单介绍 前面讲过,AtomicLong通过CAS提供了非阻塞的原子性操作,相比使用阻塞算法的同步器来说它的性能已经很好了,但是JDK开发组并不满足于此。使用AtomicLong 时,在高并发下大量线程会同时去竞争更新同一个原子变量,但是由于同时只有一个线程的CAS操作会成功,…...

常见的基础系统

权限管理系统支付系统搜索系统报表系统API网关系统待定。。。 Java 优质开源系统设计项目 来源&#xff1a;Java 优质开源系统设计项目 | JavaGuide 备注&#xff1a;github和gitee上可以搜索到相关项目...

在 window 系统下安装 Ubuntu (虚拟机)

文章目录 零、Ubuntu 和 Vmware workstation 资源一、下载 Ubuntu二、下载 Vmware Workstation Pro三、安装 Vmware Workstation Pro四、创建虚拟机五、配置 Ubuntu 零、Ubuntu 和 Vmware workstation 资源 如果觉得自己下载 Ubuntu 和 Vmware workstation 麻烦&#xff0c;也…...

鸿蒙开发(NEXT/API 12)【访问控制应用权限管控概述】程序访问控制

默认情况下&#xff0c;应用只能访问有限的系统资源。但某些情况下&#xff0c;应用存在扩展功能的诉求&#xff0c;需要访问额外的系统数据&#xff08;包括用户个人数据&#xff09;和功能&#xff0c;系统也必须以明确的方式对外提供接口来共享其数据或功能。 系统通过访问…...

(10)MATLAB莱斯(Rician)衰落信道仿真1

文章目录 前言一、莱斯分布随机变量二、仿真代码与结果1.仿真代码2.仿真结果画图 后续 前言 首先给出莱斯衰落信道模型&#xff0c;引入了莱斯因子K&#xff0c;并给出莱斯分布的概率密度函数公式。然后导出莱斯分布随机变量的仿真表示式&#xff0c;建立MATLAB仿真代码&#…...

什么是重卡充电桩?

有什么广告&#xff1f;没有广告&#xff0c;纯纯的介绍。 在政策与市场双重驱动下&#xff0c;充电桩市场已经开启加速模式&#xff0c;行业的火苗越烧越旺。同时&#xff0c;随着新能源重卡的广泛普及&#xff0c;重卡充电桩也迎来了新的发展机遇。 此种背景下 &#xff0c…...

模拟实现消息队列(基于SpringBoot实现)

提要&#xff1a;此处的消息队列是仿照RabbitMQ实现&#xff08;参数之类的&#xff09;&#xff0c;实现一些基本的操作&#xff1a;创建/销毁交互机&#xff08;exchangeDeclare&#xff0c;exchangeDelete&#xff09;&#xff0c;队列&#xff08;queueDeclare&#xff0c;…...

C语言:预编译过程的剖析

目录 一.预定义符号和#define定义常量 二.#define定义宏 三.宏和函数的对比 四、#和##运算符 五、条件编译 在之前&#xff0c;我们已经介绍了.c文件在运行的过程图解&#xff0c;大的方面要经过两个方面。 一、翻译环境 1.预处理&#xff08;预编译&#xff09; 2.编译 3…...

算法——单调栈

单调栈&#xff1a; 保持栈内的元素始终递增或递减。 单调递增 待处理数组{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) {//当栈空的时候可以直接进栈或者要进栈的数大于…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...