RMQ区间求最值 后缀数组height预处理(区间求最小值)

2024-06-12 01:58

本文主要是介绍RMQ区间求最值 后缀数组height预处理(区间求最小值),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

首先是一般的RMQ区间求最值问题

minsum[i][j]表示起始位置为i长度为j的区间内的最小值。RMQ利用二进制优化处理。

所以,他的状态转移方程就是  F[i, j]=max(F[i,j-1], F[i + 2^(j-1),j-1])

查询区间[i][j]的最小值相当于区间[i][k]和区间[t][j]的最小值,其中k>=t


void RMQ(int num)
{for(int j = 0; j < 19; ++j)for(int i = 1; i <= num; ++i){if(j==0)minsum[i][j]=arr[i];//初始化else if(i + (1 << j) - 1 <= num){minsum[i][j] = min(minsum[i][j - 1], minsum[i + (1 << (j - 1))][j - 1]);//此处为区间求最小值  如果要求最小值,把min相应的改为max就好}}
}

我是在学习后缀数组的时候接触到RMQ算法的,下面的代码是求suffix(i)跟suffix(j)的最大公共前缀的RMQ预处理

对于RMQ部分基本没有变化,只是初始化的时候arr改称了height数组

void init()//获取相对应的最长长度Log[i]=j表示2^j<=i并且j是满足条件的最大值
{Log[0] = -1;for(int i=1; i<=maxn; i++){Log[i]=(i&(i-1))?Log[i-1]:Log[i-1] + 1 ;}
}
int val(int x,int y)//x,y表示要比较的以x位置开头的后缀与以y开头的后缀
{if(x==y)return 1111111;x=rank[x];y=rank[y];int i=min(x,y);int j=max(x,y);i++;int tem=Log[j-i+1];return min(minsum[i][tem],minsum[j-(1<<tem)+1][tem]);
}
刚刚学习后缀数组,有写的不妥的地方还望指正。


这篇关于RMQ区间求最值 后缀数组height预处理(区间求最小值)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

Python使用vllm处理多模态数据的预处理技巧

《Python使用vllm处理多模态数据的预处理技巧》本文深入探讨了在Python环境下使用vLLM处理多模态数据的预处理技巧,我们将从基础概念出发,详细讲解文本、图像、音频等多模态数据的预处理方法,... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

css中的 vertical-align与line-height作用详解

《css中的vertical-align与line-height作用详解》:本文主要介绍了CSS中的`vertical-align`和`line-height`属性,包括它们的作用、适用元素、属性值、常见使用场景、常见问题及解决方案,详细内容请阅读本文,希望能对你有所帮助... 目录vertical-ali