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

线段数--算法

线段树是常用来维护 区间信息 的数据结构

线段树可以在 O(logN) 的时间复杂度内实现

  • 单点修改
  • 区间修改
  • 区间查询
    • 区间求和
    • 求区间最大值
    • 求区间最小值

简单介绍一下线段树

线段树是一个将区间内的数不断细分的一种数据结构,也就是一个完全二叉树,用每一个叶子节点代表一个区间内的值

操作1:单点修改

单点修改是找到要修改的那个点所在的每一层的区间,最后通过叶子节点,修改为相应的值,然后向上递归

操作2:区间查询

区间查询[l,r]是指在线段树内从上向下查询,如果子区间的左右端点都在[l,r]内则不用在向下递归,直到找到所有的点

常用操作函数

  1. pushup(int u):用子节点的信息更新当前节点
    1. 参数u是根节点
static void pushUp(int u){node[u].sum=node[u<<1].sum+node[u<<1|1].sum;
}
  1. build(int u,int l,int r):在一段区间上初始化线段树
    1. 参数u是根节点,l是区间左端点,r是区间右端点
static void build(int u,int l,int r){if(l==r)node[u]=new Node(l,r,w[r]);else{node[u]=new Node(l,r,0);int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushUp(u);}
}
  1. modify(int u,int x,int v):修改某一点的值
    1. 参数u是根节点,x是要修改的节点,v是要增加或减小的值
static void modify(int u,int x,int v){if(node[u].l==node[u].r)node[u].sum+=v;else{int mid=(node[u].l+node[u].r)>>1;if(x<=mid)modify(u<<1,x,v);else modify(u<<1|1,x,v);pushUp(u);}
}
  1. query(int u,int l,int r):查询
    1. 参数u是根节点,l是区间左端点,r是区间右端点
static int query(int u,int l,int r){if(node[u].l>=l&&node[u].r<=r)return node[u].sum;int mid=node[u].l+node[u].r>>1;int sum=0;if(l<=mid)sum+=query(u<<1,l,r);if(r>mid)sum+=query(u<<1|1,l,r);return sum;
}

节点表示

父节点:x/2 ==> x>>1

左儿子:2x ==> x<<1

右儿子:2x+1 ==> x>>1|1


动态求连续区间和

package 线段树;import java.io.BufferedReader;
import java.io.InputStreamReader;public class Main {static int N=1000010;static Node[] node=new Node[N];static int[] w=new int[N];static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));static int n,m;static String[] $;static void pushUp(int u){node[u].sum=node[u<<1].sum+node[u<<1|1].sum;}static void build(int u,int l,int r){if(l==r)node[u]=new Node(l,r,w[r]);else{node[u]=new Node(l,r,0);int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushUp(u);}}static int query(int u,int l,int r){if(node[u].l>=l&&node[u].r<=r)return node[u].sum;int mid=node[u].l+node[u].r>>1;int sum=0;if(l<=mid)sum+=query(u<<1,l,r);if(r>mid)sum+=query(u<<1|1,l,r);return sum;}static void modify(int u,int x,int v){if(node[u].l==node[u].r)node[u].sum+=v;else{int mid=(node[u].l+node[u].r)>>1;if(x<=mid)modify(u<<1,x,v);else modify(u<<1|1,x,v);pushUp(u);}}public static void main(String[] args)throws Exception {$=br.readLine().split(" ");n=Integer.parseInt($[0]);m=Integer.parseInt($[1]);$=br.readLine().split(" ");for(int i=1;i<=n;i++)w[i]=Integer.parseInt($[i-1]);build(1,1,n);while (m-->0){$=br.readLine().split(" ");int k=Integer.parseInt($[0]);int a=Integer.parseInt($[1]);int b=Integer.parseInt($[2]);if(k==0)System.out.println(query(1,a,b));else modify(1,a,b);}}
}class Node{int l,r,sum;public Node(int l,int r,int sum){this.l=l;this.r=r;this.sum=sum;}
}

相关文章:

线段数--算法

线段树是常用来维护 区间信息 的数据结构 线段树可以在 O(logN) 的时间复杂度内实现 单点修改区间修改区间查询 区间求和求区间最大值求区间最小值 简单介绍一下线段树 线段树是一个将区间内的数不断细分的一种数据结构&#xff0c;也就是一个完全二叉树&#xff0c;用每一…...

JS的DOM操作和事件监听综合练习 (具备三种功能的轮播图案例)

下面是是对dom操作的一个综合练习 下面代码是html的基本骨架&#xff08;没有任何的功能&#xff09;&#xff1a; <!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <meta name"viewport" c…...

低温存储开关机问题

问题&#xff1a; 某消费电子产品在进行可靠性实验室&#xff0c;在低温-30C存储两个小时后&#xff0c;上电不开机。在常温25C时&#xff0c;开关机正常。 分析&#xff1a; 1、接串口抓log信息&#xff0c;从打印信息可以看出uboot可以起来&#xff0c;在跑kernel时&#x…...

mysql系列1—mysql架构和协议介绍

背景&#xff1a; 本文开始整理mysql相关的文章&#xff0c;用于收集数据库相关内容&#xff1b;包括mysql架构和存储方式、索引结构和查询优化、数据库锁等内容。思考如何根据具体的业务给出最优的分表规划和表设计、字段选择和索引设计、优化的SQL语句&#xff0c;以及数据库…...

设计模式——模板模式

定义与基本概念 模板模式&#xff08;Template Pattern&#xff09;是一种行为设计模式。它在一个抽象类中定义了一个操作的算法骨架&#xff0c;将一些步骤的实现延迟到具体子类中。这个抽象类就像是一个模板&#xff0c;定义了执行某个流程的基本框架&#xff0c;而具体的细…...

CV22_语义分割基础

1. 常见的分割类型 在计算机视觉领域&#xff0c;根据不同的应用场景和需求&#xff0c;分割任务可以分为几种主要类型。以下是几种常见的分割类型&#xff1a; 语义分割&#xff08;Semantic Segmentation&#xff09;&#xff1a; 语义分割的目标是将图像中的每个像素分配到…...

Dubbo源码解析-Dubbo的线程模型(九)

一、Dubbo线程模型 首先明确一个基本概念&#xff1a;IO 线程和业务线程的区别 IO 线程&#xff1a;配置在netty 连接点的用于处理网络数据的线程&#xff0c;主要处理编解码等直接与网络数据 打交道的事件。 业务线程&#xff1a;用于处理具体业务逻辑的线程&#xff0c;可以…...

【Canvas与标志】圆角三角形生化危险警示标志

【成图】 【代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"/> <head><title>圆角三角形生化危险警示标志 Draft1</title><style type&qu…...

解决Dcat Admin laravel框架登录报错问题,(blocked:mixed-content)

前言 在使用 Dcat Admin 后台登录时&#xff0c;发生 error 报错&#xff1a;(blocked:mixed-content) xhr VM484:1&#xff0c;浏览器拦截 其实这是浏览器在 HTTPS 页面中尝试加载 HTTP 资源&#xff0c;导致浏览器阻止了这些不安全的请求。 解决 在 .env 文件中添加或修改 AD…...

(三)Sping Boot学习——升级jdk1.8-jdk18

1.修改系统环境变量。 2.idea中修改配置。 3.项目setting中设置修改 4.更新后还要重新下载依赖mvn clean install &#xff0c;并且记住reload 项目。同时查看java -version查看一下jdk版本。...

语言模型中的多模态链式推理

神经网络的公式推导 简介摘要引言多模态思维链推理的挑战多模态CoT框架多模态CoT模型架构细节编码模块融合模块解码模块 实验结果运行代码补充细节安装包下载Flan-T5数据集准备rougenltkall-MiniLM-L6-v2运行 简介 本文主要对2023一篇论文《Multimodal Chain-of-Thought Reason…...

SCons:下一代构建工具,如何用 Python 驱动高效构建?

在现代软件开发中&#xff0c;构建工具是开发流程中不可或缺的一环。无论是小型项目还是跨平台的复杂工程&#xff0c;选择一个高效、灵活的工具都能显著提高开发效率和代码质量。SCons&#xff0c;一个以 Python 为基础的构建工具&#xff0c;通过自动化依赖管理、灵活的扩展性…...

springboot 整合 rabbitMQ (延迟队列)

前言&#xff1a; 延迟队列是一个内部有序的数据结构&#xff0c;其主要功能体现在其延时特性上。这种队列存储的元素都设定了特定的处理时间&#xff0c;意味着它们需要在规定的时间点或者延迟之后才能被取出并进行相应的处理。简而言之&#xff0c;延时队列被设计用于存放那…...

ES 基本使用与二次封装

概述 基本了解 Elasticsearch 是一个开源的分布式搜索和分析引擎&#xff0c;基于 Apache Lucene 构建。它提供了对海量数据的快速全文搜索、结构化搜索和分析功能&#xff0c;是目前流行的大数据处理工具之一。主要特点即高效搜索、分布式存储、拓展性强 核心功能 全文搜索:…...

分割一切2.0,SAM2详解

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;编程探索专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年11月24日20点03分 神秘男子影, 秘而不宣藏。 泣意深不见, 男子自持重, 子夜独自沉。 论文链接 点击开启你的论文编程之旅…...

Spring AI Fluent API:与AI模型通信的流畅体验

引言 随着人工智能&#xff08;AI&#xff09;技术的飞速发展&#xff0c;越来越多的应用场景开始融入AI技术以提升用户体验和系统效率。在Java开发中&#xff0c;与AI模型通信成为了一个重要而常见的需求。为了满足这一需求&#xff0c;Spring AI引入了ChatClient&#xff0c…...

基于python的长津湖评论数据分析与可视化,使用是svm情感分析建模

引言 研究背景及意义 上世纪初开始&#xff0c;中国电影就以自己独有的姿态登上了世界电影史的舞台。中国电影作为国家文化和思想观念的反映与延伸&#xff0c;能够增强文化自信&#xff0c;在文化输出方面有着极其重要的作用1[1]。 改革开放以来&#xff0c;随着生产力的提高…...

Lucene(2):Springboot整合全文检索引擎TermInSetQuery应用实例附源码

前言 本章代码已分享至Gitee: https://gitee.com/lengcz/springbootlucene01 接上文。Lucene(1):Springboot整合全文检索引擎Lucene常规入门附源码 如何在指定范围内查询。从lucene 7 开始&#xff0c;filter 被弃用&#xff0c;导致无法进行调节过滤。 TermInSetQuery 指定…...

shell完结

声明&#xff01; 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下&#xff0c;如涉及侵权马上删除文章&#xff0c;笔记只是方便各位师傅的学习和探讨&#xff0c;文章所提到的网站以及内容&#xff0c;只做学习交流&#xff0c;其他均与本人以及泷羽sec团队无关&a…...

【2024最新】基于Springboot+Vue的智慧食堂系统Lw+PPT

作者&#xff1a;计算机搬砖家 开发技术&#xff1a;SpringBoot、php、Python、小程序、SSM、Vue、MySQL、JSP、ElementUI等&#xff0c;“文末源码”。 专栏推荐&#xff1a;SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;Java精选实战项…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

日常一水C

多态 言简意赅&#xff1a;就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过&#xff0c;当子类和父类的函数名相同时&#xff0c;会隐藏父类的同名函数转而调用子类的同名函数&#xff0c;如果要调用父类的同名函数&#xff0c;那么就需要对父类进行引用&#…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...