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

ST表(数据结构中的问题)

RMQ问题

RMQ问题指对于数值,每次给一个区间[l,r],要求返回区间区间的最大值或最小值

也就是说,RMQ就是求区间最值的问题

对于RMQ问题,容易想到一种O(n)的方法,就是用i直接遍历[l,r]区间,找出不断比较a[i]与max的大小关系,然后不断更新max,最后得出的就是最大值

但如果要进行多次查询,这个算法就会变得特别慢

于是,我们利用倍增和动态规划的思想,利用‘ST表’这个数据结构来帮助解决。

ST表

ST表是一种“静态求区间最值”的数据结构,本质上是一种dp。

假设我们要求区间的最大值(最小值类似),设状态st[i][j]表示从i开始,大小为2^j的长度的区间的最大值,即区间[i,i+2^j-1]的最大值

状态转移方程st[i][j]=max[st[i][j-1],st[i+(1<<(j-1))] [j-1]];      (1<<(j-1))相当于2^j-1

分成左右两个相等的区间

注意状态转移的方向和保证区间合法

区间查询

为了查询区间[l,r]的最大值,它可以分解为两个小区间的最大值,例如要求[2,7]的最大值,可以分解为[2,2+2*2-1],[7-2*2+1,7]的最大值,也就是(st[2][2],st[7-4][2]) 

                                    从2开始长度为2的最大值,和从5开始,长度为2的最大值

拓展一下,[l,r]区间,需要找出一个k,使得2^k<=r-l+1,k<=log2(r-l+1),可以分解为max(st[l][k],st[r-2^k+1][k])                    一个是从头开始,一个是从尾开始

int getMax(int l,int r){

        return max(str[l][k],st[r-(1<<k)+1][k]);

}

例题

区间最大值

题目描述

给定一个长度为 N 的数组 a,其值分别a1​,a2​,...,aN​。

现有 Q 个询问,每个询问包含一个区间,请回答该区间的最大值为多少。

输入描述

输入第 11 行包含两个正整数 N,Q,分别表示数组 a 的长度和询问的个数。

第 22 行包含 N 个非负整数a1​,a2​,...,aN​,表示数组 a 元素的值。

第 3∼Q+2 行每行表示一个询问,每个询问包含两个整数 L,R,表示区间的左右端点.

输出描述

输出共 Q 行,每行包含一个整数,表示相应询问的答案。

输入输出样例

示例 1

输入

5 5
1 2 3 4 5
1 1 
1 2 
1 3
3 4
2 5

输出

1
2
3
4
5
package ST;
import java.util.*;
public class chapter1 {public static void main(String[] args) {// TODO Auto-generated method stubScanner scan=new Scanner(System.in);int n=scan.nextInt();int q=scan.nextInt();long []a=new long [n];for(int i=0;i<n;i++) {a[i]=scan.nextLong();}int m=(int)Math.ceil(Math.log(n)/Math.log(2));//对m进行向上取整,2^nlong [][] st=new long [n][m];for(int i=0;i<n;i++) {st[i][0]=a[i];}for(int k=1;k<m;k++) {for(int i=0;i+(1<<k)<n;i++) {st[i][k]=Math.max(st[i][k-1],st[i+(1<<(k-1))][k-1]);}}while(q-->0) {int l=scan.nextInt()-1;//数组从0开始所以需要减1int r=scan.nextInt()-1;int len=r-l+1;int k=(int)(Math.log(len)/Math.log(2));int max= (int) Math.max(st[l][k],st[r-(1<<k)+1][k] );System.out.println(max);}}}

 

相关文章:

ST表(数据结构中的问题)

RMQ问题 RMQ问题指对于数值&#xff0c;每次给一个区间[l,r]&#xff0c;要求返回区间区间的最大值或最小值 也就是说&#xff0c;RMQ就是求区间最值的问题 对于RMQ问题&#xff0c;容易想到一种O&#xff08;n&#xff09;的方法&#xff0c;就是用i直接遍历[l,r]区间&…...

一、OpenCV(C#版本)环境搭建

一、Visual Studio 创建新项目 二、选择Windows窗体应用&#xff08;.NET Framework&#xff09; 直接搜索模板&#xff1a;Windows窗体应用(.NET Framework) 记得是C#哈&#xff0c;别整成VB(Visual Basic)了 PS&#xff1a;若搜索搜不到&#xff0c;直接点击安装多个工具和…...

ubuntu远程服务部署,Docker,蓝牙无线局域网,SSH,VNC,xfce4,NextTerminal,宝塔,NPS/NPC,gost,openwrt

SSH服务 apt update apt upgrade -y apt install -y openssh-server/etc/ssh/sshd_config PermitRootLogin yesDocker curl -fsSL https://get.docker.com | bash -s docker --mirror Aliyun apt install -y docker-compose宝塔 wget -O install.sh https://download.bt.cn…...

kettle安装与部署使用教程

kettle 官网下载与部署使用 文章目录 kettle 官网下载与部署使用1. 前言&#xff1a;2. 访问官方网站&#xff1a;3. Download Pentaho3.1 官网首页**滑动到最底**&#xff0c;寻找下载链接&#xff1a;3.2 跳转到下载界面后&#xff0c;选择 Pentaho Community Edition (CE)3.…...

【C语言】编译和链接

1. 翻译环境和运行环境 在ANSI C的任何⼀种实现中&#xff0c;存在两个不同的环境。 第1种是翻译环境&#xff0c;在这个环境中源代码被转换为可执⾏的机器指令&#xff08;⼆进制指令&#xff09;。 第2种是执⾏环境&#xff0c;它⽤于实际执⾏代码。 2. 编译环境 那翻译环境…...

Python学习: 错误和异常

Python 语法错误 解析错误(Parsing Error)通常指的是程序无法正确地解析(识别、分析)所给定的代码,通常是由于代码中存在语法错误或者其他无法理解的结构导致的。这可能是由于缺少括号、缩进错误、未关闭的引号或其他括号等问题造成的。 语法错误(Syntax Error)是指程序…...

WebGIS 之 vue3+vite+ceisum

1.项目搭建node版本在16以上 1.1创建项目 npm create vite 项目名 1.2选择框架 vuejavaScript 1.3进入项目安装依赖 cd 项目名 npm install 1.4安装cesium依赖 pnpm i cesium vite-plugin-cesium 1.5修改vite.config.js文件 import { defineConfig } from vite import vue fr…...

## CSDN创作活动:AI技术创业有哪些机会?

AI技术创业有哪些机会&#xff1f; 人工智能&#xff08;AI&#xff09;技术作为当今科技创新的前沿领域&#xff0c;为创业者提供了广阔的机会和挑战。随着AI技术的快速发展和应用领域的不断拓展&#xff0c;未来AI技术方面会有哪些创业机会呢&#xff1f; 方向一&#xff1…...

中医肝胆笔记

目录 肝胆的经络足厥阴肝经足少阳胆经 疏肝健脾的药舒肝益脾颗粒&#xff1a;逍遥丸&#xff1a;疏肝颗粒 -> 疏肝理气的力度大-> 肝郁的程度深&#xff0c;逍遥丸没用的是时候用这个加味逍遥丸 -> 清热的力度最大->适用 肝郁火大&#xff0c;舌苔黄丹栀逍遥丸->…...

理解Go语言中break语句是如何工作的

break语句常用来中断循环。当循环与switch或select一起使用时&#xff0c;开发者经常执行了错误的break语句。 让我们来看下面的示例。我们在for循环里使用了switch,如果循环索引值是2&#xff0c;那么我们想中断循环&#xff1a; package mainimport ("fmt" )func …...

11. 瀑布流布局

<!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><title>11.瀑布流布局</title><style>#cont…...

Flutter-发布插件到pub上传不上问题

问题1&#xff1a; 尝试指令&#xff1a; flutter packages pub publish --serverhttps://pub.dartlang.org问题2&#xff1a; 问题1解决后&#xff0c;进入验证身份&#xff0c;点击终端显示的链接&#xff0c;跳转到google验证&#xff0c;记得这里要科*学上网&#xff0c;点…...

Windows 2008虚拟机安装、安装VM Tools、快照和链接克隆、添加硬盘修改格式为GPT

一、安装vmware workstation软件 VMware workstation的安装介质&#xff0c;获取路径&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1AUAw_--yjZAUPbsR7StOJQ 提取码&#xff1a;umz1 所在目录&#xff1a;\vmware\VMware workstation 15.1.0 1.找到百度网盘中vmwa…...

c++的学习之路:12、vector(1)

这章主要是根据cplusplus中的文档进行使用Vector&#xff0c;文章末附上测试代码。 目录 一、什么是vector 二、vector的简单使用 三、代码 一、什么是vector 下图是cplusplus的简介&#xff0c;上面一共有六点&#xff0c;如下&#xff1a; 1、vector是表示可变大小数组…...

2024.2.17力扣每日一题——N叉树的层序遍历

2024.2.17 题目来源我的题解方法一 广度优先搜索&#xff08;队列实现&#xff09; 题目来源 力扣每日一题&#xff1b;题序&#xff1a;429 我的题解 方法一 广度优先搜索&#xff08;队列实现&#xff09; 和二叉树的层序遍历相同&#xff0c;只是在添加子节点的细节有所不…...

滑动窗口(尺取法/Python)

滑动窗口&#xff08;尺取法&#xff09; 算法含义&#xff1a; 在解决关于区间特性的题目时保存搜索区间左右端点&#xff0c;然后根据实际要求不断更新左右端点位置的算法 时间复杂度&#xff1a; O ( n ) O(n) O(n) 空间复杂度&#xff1a; O ( 1 ) O(1) O(1) 在历年真题…...

【打印SQL执行日志】⭐️Mybatis-Plus通过配置在控制台打印执行日志

目录 前言 一、Mybatis-Plus 开启日志的方式 二、测试 三、日志分析 章末 前言 小伙伴们大家好&#xff0c;相信大家平时在处理问题时都有各自的方式&#xff0c;最常用以及最好用的感觉还是断点调试&#xff0c;但是涉及到操作数据库的执行时&#xff0c;默认的话在控制台…...

Vue后台管理系统常用组件的优缺点分析

以下是Vue后台管理系统常用组件的优缺点分析&#xff1a; Element UI 优点&#xff1a; 丰富的组件库&#xff1a;Element UI 提供了大量的组件&#xff0c;包括表单、表格、弹窗、导航等&#xff0c;可以满足各种后台管理系统的需求。易于使用&#xff1a;Element UI 的组件…...

栈的应用——用栈实现算数混合运算表达式的计算

1、单目运算符双目运算符 算数运算符分为单目运算符和双目运算符等 单目运算符只需要一个操作数,双目运算符需要两个操作数 双目运算符最常见:常见的算术运算符:*/,比较运算符:<>=等等以下是一些单目运算符:正号 (+): 用于表示正数或给数值一个正号。例如:+5 仍然…...

动态规划—机器人移动问题(Java)

&#x1f600;前言 机器人移动问题是一个经典的动态规划应用场景&#xff0c;它涉及到在给定范围内的位置上进行移动&#xff0c;并计算到达目标位置的方法数。本文将介绍三种解决这一问题的方法&#xff1a;暴力递归、缓存法和动态规划。通过比较不同方法的优缺点&#xff0c;…...

第十一届蓝桥杯物联网试题(省赛)

对于通信方面&#xff0c;还是终端A、B都保持接收状态&#xff0c;当要发送的数组不为空再发送数据&#xff0c;发送完后立即清除&#xff0c;接收数据的数组不为空则处理&#xff0c;处理完后立即清除&#xff0c;分工明确 继电器不亮一般可能是电压不够 将数据加空格再加\r…...

【Python基础教程】5. 数

&#x1f388;个人主页&#xff1a;豌豆射手^ &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;python基础教程 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、…...

Qt中出现中文乱码的原因以及解决方法

Qt专栏&#xff1a;http://t.csdnimg.cn/C2SDN 目录 1.引言 2.原因分析 3.源文件的编码格式修改方法 4.程序内部使用的默认编码格式修改方法 5.QString转std::string的方法 6.总结 1.引言 在编写Qt程序的时候&#xff0c;或多或少都可能遇到用QString时候&#xff0c;明明…...

Linux 文件相关命令

一、查看文件命令 1&#xff09;浏览文件less 默认查看文件的前 10 行。 less /etc/services ##功能说明&#xff1a; #1.默认打开首屏内容 #2.按【回车】按行访问 #3.按【空格】按屏访问 #4.【从上向下】搜索用/111,搜索包含111的内容&#xff0c;此时按n继续向下搜&#x…...

K8S Deployment 简介, 1个简单的Kubernetes Deployment YAML 文件

当谈到 Kubernetes 集群中的应用程序部署和管理时&#xff0c;Deployment、ReplicaSet 和 Pod 是三个重要的概念。它们之间存在一定的关系和层次结构。下面是对 Deployment、ReplicaSet 和 Pod 的详细解释以及它们之间的关系。 Deployment&#xff08;部署&#xff09; Deploy…...

win11安装WSL UbuntuTLS

win11安装WSL WSL 简介WSL 1 VS WSL 2先决要求安装方法一键安装通过「控制面板」安装 WSL 基本命令Linux发行版安装Ubuntu初始化相关设置root用户密码网络工具安装安装1panel面板指导 WSl可视化工具问题总结WSL更新命令错误Ubuntu 启动初始化错误未解决问题 WSL 简介 Windows …...

第十题:金币

题目描述 国王将金币作为工资&#xff0c;发放给忠诚的骑士。第一天&#xff0c;骑士收到一枚金币&#xff1b;之后两天&#xff08;第二天和第三天&#xff09;&#xff0c;每天收到两枚金币&#xff1b;之后三天&#xff08;第四、五、六天&#xff09;&#xff0c;每天收到…...

Windows 11 中Docker的安装教程

选择正确的Docker版本 在Windows上&#xff0c;你可以安装两种类型的Docker&#xff1a;Docker Desktop和Docker Toolbox。Docker Desktop是针对Windows 10 Pro、Enterprise和Education版本的&#xff0c;这些版本内置了Hyper-V虚拟化支持。对于旧版本的Windows&#xff0c;比…...

纯C代码模板

一、快排 void QuickSort(int *a,int left,int right){if(left>right) return;else{int low left,high right;int pivot a[low];while(low<high){while(a[high] > pivot && low < high){high--;}a[low] a[high]; //必须先动a[low]while(a[low] < …...

二、GitLab相关操作

GitLab相关操作 一、组、用户、项目管理1.创建组2.创建项目3.创建用户并分配组3.1 创建用户3.2 设置密码3.3 给用户分配组 二、拉取/推送代码1.配置ssh(第一次需要)1.1 创建一个空文件夹1.2 配置本地仓账号和邮箱1.3 生成ssh公钥密钥1.4 gitlab配置公钥 2.拉取代码3.推送代码3.…...

建设一个网站需要做哪些工作/腾讯新闻发布平台

解决 Win7 32bit/64bit环境下&#xff0c;在使用VS2003的查找功能时&#xff0c;会导致VS2003无响应。 解决方法&#xff1a;找到VS2003的安装目录&#xff0c;修改"...\Microsoft Visual Studio .NET 2003\Common7\IDE"目录下的devenv.exe的属性&#xff0c;将其兼容…...

类似于众人帮的做任务赚佣金网站/引擎优化seo

C语言数组结构行优先顺序存储的实现 (GCC编译)。 1 /**2 * brief C语言 数组 行优先 实现3 * author wid4 * date 2013-11-025 *6 * note 若代码存在 bug 或程序缺陷, 请留言反馈, 谢谢!7 */8 9 #include <stdio.h>10 #include <stdlib.h>11 #include <stdarg.h…...

网页设计实验报告结果/优化大师win10

本文中概述的一些准则可以被客观地评价;其他的&#xff0c;则是有场景的、上下文环境的或主观的。 最重要的一点&#xff0c;是保持一致性。 一致性的代码更容易维护&#xff0c;更容易优化&#xff0c;需要更少的学习成本&#xff0c;并且随着新约定的出现或bug类的修复&…...

湛江住房和城乡建设局网站/百家号seo

注&#xff1a;C#语言发展十分迅速&#xff0c;而且仍然有很大的提升空间&#xff0c;所以现在写下的有关C#语言上的一些限制&#xff0c;可能过一两年就不同了&#xff0c;所以需要不断更新。至于C&#xff0c;因为已经很久没怎么变动&#xff0c;所以就容易得多。 (*) 允许初…...

恒一信息深圳网站建设公司2/百度快照推广

如今&#xff0c;在各行各业作业生产中&#xff0c;都能看到工业连接器、插头插座的身影&#xff0c;它能够传输高速、高容量和高精度的信号和电力&#xff0c;具有防水、防尘、抗震动、抗干扰等特性&#xff0c;被广泛应用在工业控制、通讯、医疗、交通、航空、军事等领域&…...

什么是微网站/微软bing搜索引擎

题目&#xff1a; 我是超链接 题解&#xff1a; 题目中有三个条件&#xff0c;我们先不管第三个看起来很长的条件&#xff0c;那么就是让求。 ∑i1n∑j1mij(i,j)∑i1n∑j1mij(i,j)经过类似 luogu3768的化简&#xff0c;我们得到的是∑T1nsum(nT)sum(mT)T∑t|Tμ(t)t∑T1nsu…...