ST表(区间查询

2024-08-28 08:52
文章标签 查询 区间 st

本文主要是介绍ST表(区间查询,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

解决的问题:

  • 数组区间查询最大值和最小值
  • 对于解决数组的树状数组的区间修改 ------- 线段树
  • 倍增思想

在这里插入图片描述
在这里插入图片描述

核心代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int num[N];
int f[N][N];
int main(){int n;cin>>n;//输入默认从1开始 for(int i=1;i<=n;i++) cin>>num[i];//创建st表for(int i=0;i<=20;i++){//枚举区间长度 2*i次方//2的20次方大约1.04e6 //当区间太大  会一直continue for(int j=1;j+(1<<i)-1<=n;j++){//区间末尾:j+2的i次方-1 不能越界 f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);//j到j+1<<i-1区间 由两个一半的区间组成//所以时间复杂度为nlogn }} //查询函数//给定左右闭区间l,R 查询最大值 int l,r;cin>>l>>r;int qujian=log2(r-l+1);//查看区间长度对应的log图//通过先分裂区间后 利用区间交集的方式去查询//记得左右  会用到lr  右边不能从l入手  从r入手 int res=max(f[l][qujian],f[r-(1<<qujian)+1][qujian]);cout<<res<<endl;return 0; }

这篇关于ST表(区间查询的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1114301

相关文章

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

在Java中基于Geotools对PostGIS数据库的空间查询实践教程

《在Java中基于Geotools对PostGIS数据库的空间查询实践教程》本文将深入探讨这一实践,从连接配置到复杂空间查询操作,包括点查询、区域范围查询以及空间关系判断等,全方位展示如何在Java环... 目录前言一、相关技术背景介绍1、评价对象AOI2、数据处理流程二、对AOI空间范围查询实践1、空间查

MySQL基本查询示例总结

《MySQL基本查询示例总结》:本文主要介绍MySQL基本查询示例总结,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Create插入替换Retrieve(读取)select(确定列)where条件(确定行)null查询order by语句li

MySQL中like模糊查询的优化方案

《MySQL中like模糊查询的优化方案》在MySQL中,like模糊查询是一种常用的查询方式,但在某些情况下可能会导致性能问题,本文将介绍八种优化MySQL中like模糊查询的方法,需要的朋友可以参... 目录1. 避免以通配符开头的查询2. 使用全文索引(Full-text Index)3. 使用前缀索

基于Redis实现附近商铺查询功能

《基于Redis实现附近商铺查询功能》:本文主要介绍基于Redis实现-附近商铺查询功能,这个功能将使用到Redis中的GEO这种数据结构来实现,需要的朋友可以参考下... 目录基于Redis实现-附近查询1.GEO相关命令2.使用GEO来实现以下功能3.使用Java实现简China编程单的附近商铺查询4.Red

mysql递归查询语法WITH RECURSIVE的使用

《mysql递归查询语法WITHRECURSIVE的使用》本文主要介绍了mysql递归查询语法WITHRECURSIVE的使用,WITHRECURSIVE用于执行递归查询,特别适合处理层级结构或递归... 目录基本语法结构:关键部分解析:递归查询的工作流程:示例:员工与经理的层级关系解释:示例:树形结构的数

SQL常用操作精华之复制表、跨库查询、删除重复数据

《SQL常用操作精华之复制表、跨库查询、删除重复数据》:本文主要介绍SQL常用操作精华之复制表、跨库查询、删除重复数据,这些SQL操作涵盖了数据库开发中最常用的技术点,包括表操作、数据查询、数据管... 目录SQL常用操作精华总结表结构与数据操作高级查询技巧SQL常用操作精华总结表结构与数据操作复制表结

MySQL 复合查询案例详解

《MySQL复合查询案例详解》:本文主要介绍MySQL复合查询案例详解,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录基本查询回顾多表笛卡尔积子查询与where子查询多行子查询多列子查询子查询与from总结合并查询(不太重要)union基本查询回顾查询

MySQL复合查询从基础到多表关联与高级技巧全解析

《MySQL复合查询从基础到多表关联与高级技巧全解析》本文主要讲解了在MySQL中的复合查询,下面是关于本文章所需要数据的建表语句,感兴趣的朋友跟随小编一起看看吧... 目录前言:1.基本查询回顾:1.1.查询工资高于500或岗位为MANAGER的雇员,同时还要满足他们的姓名首字母为大写的J1.2.按照部门

MyBatis模糊查询报错:ParserException: not supported.pos 问题解决

《MyBatis模糊查询报错:ParserException:notsupported.pos问题解决》本文主要介绍了MyBatis模糊查询报错:ParserException:notsuppo... 目录问题描述问题根源错误SQL解析逻辑深层原因分析三种解决方案方案一:使用CONCAT函数(推荐)方案二: