首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

区间问题之ST表算法

区间问题之ST表算法 1.ST算法思想 ST(Sparse Table)算法是一种用于解决RMQ(Range Minimum/Maximum Query,即区间查询)问题的离线算法。...ST算法描述:首先明确解决的是区间问题,那么对于给定的数组arr = [1,4,8,20, 10],长度为2^j的区间可以拆分成两个2^(j-1)的区间,那么对于dp[i][j],i表示区间起点,j...创建 dp[i][j]表示从i开始长度为2^j的区间,那么i和j的取值需要明确。...int n = input.size(); // 预处理每个区间的 int k = (int)(log((double)(n)) / log(2.0)); // 预处理区间长度等于1 for (int...给定[l, r],查询该区间的最大/最小,问题转化为从l向右覆盖2^k个数,从r向左覆盖2^k个数,一定覆盖整个区间[l, r],虽然会有重复覆盖,但不影响结果。

78910

疯子的算法总结14--ST算法(区间

②不过区间在增加时,每次并不是增加一个长度,而是基于倍增思想,用二进制右移,每次增加2^i个长度 ,最多增加logn次 这样预处理了所有2的幂次的小区间的  关于倍增法链接 查询: ③对于每个区间...,分成两段长度为的区间,再取个(这里的两个区间是可以有交集的,因为重复区间并不影响) 比如3,4,6,5,3一种分成3,4,6和6,5,3,另一种分成3,4,6和5,3,最大都是6,没影响。...因为位置过了一半,所以x到y的最小可以表示为min(从x往后2^t的最小,从y往前2^t的最小),前面的状态表示为f[t][x] 设后面(从y往前2^t的最小)的初始位置是k,那么k+2^t-...)预处理,O(1)查询  但不支持修改 预处理时间复杂度O(nlogn),查询时间O(1)。...y-z+1)/log(2));//注意y-z要加一才为区间长度 return min(map[z][x],map[y-(1<<x)+1][x]);//分别以左右两个端点为基础,向区间内跳1<<x的

78430
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    谁能想到,求算法还能优化?

    预计阅读时间:8 分钟 今天主要来聊两个问题:给一个数组,如何同时求出最大和最小,如何同时求出最大和第二大?...O(n),但如果我们以 if 判断的次数作为算法效率的评估标准,算一下 for 循环中 if 语句的判断次数: 第一个算法显然需要固定2n次 if 比较,第二个算法最坏情况需要2n次 if 比较。...接下来,我们想办法优化这两个算法,使这两个算法只需要固定的1.5n次比较。 最大和最小 为啥一般的解法还能优化呢?肯定是因为没有充分利用信息,存在冗余计算。...对于这个问题,还有另一种优化方法,那就是分治算法。大致的思路是这样: 先将数组分成两半,分别找出这两半数组的最大和最小,然后max就是两个最大中更大的那个,min就是两个最小中更小的那个。...对于第一个求最大和最小的问题的分治算法和这道题基本一样,只是最后合并子问题答案的部分不同,而且更简单,读者可以尝试写一下第一题的分治解法。

    82720

    有趣的算法(十一) ——分治法:快速​求

    有趣的算法(十一)——分治法:快速求 (原创内容,转载请注明来源,谢谢) 一、需求 一个数组,里面有若干的数字,现需要得到这一组数字的最大和最小。...二、简单分析 最基本的做法,是两两比对,可以区分出临时的最大和最小,再拿临时的最大和最小往后比较,有新的则更新。总的需要的比较次数是2n-2。 三、优化 使用分治法快速求。...即把数组分到最小的1-2个数,两两比较后,仅将最大和最小回传,再两两比较,回传新的,最终得出最大和最小。 分析需要比较的次数。当数组只有1个数时,T(1)=0;2个数时,T(2)=1。...当n不是2k,则次数会比3n/2-2略多,正好2的k次的数组长度时,这种算法较快。 四、实现 使用php编程,代码如下: <?...php $x = 0; //快速求-返回 array(min, max) function quickMost(array $nums) { $len = count($nums)

    1.6K120

    图像特征点匹配算法_bf模式匹配算法

    摘要:现阶段,基于特征点匹配算法,如SIFT,SURF等著名匹配算法,都是基于一个尺度空间来进行描述的,那么了解尺度空间是什么将是全面了解特征点匹配的关键性基础知识。...网上基于尺度空间的基础知识有很少的介绍,所以本文将主要介绍尺度空间,使读者在运用基于SIFT等特征匹配算法时,能从最基本的理论上思考问题和解决问题。...03 图像特征检测 最后再来看看图像特征提取中的应用,经典的就是sift,它就是构建了一个尺度空间来寻找最合适的峰值。...小结:简单的原理下面是复杂的数学推理和公式计算,而通透这些理论公式是非常枯燥乏味的过程,但同时也是基础最能给予人最深刻体会的过程。...通过了解尺度空间,我们可以知道尺度不变性是什么样的概念,那么特征点匹配算法等是怎么利用这种特性来建立鲁棒性强的特征提取算法的,感谢阅读,如有任何疑问请向我们留言,我们下章见!

    2.3K40

    数组之谜

    引言 在python中,求解一组数中的,可以让我们了解列表的运用和相关函数的利用。列表也算python学习的基础,更了解列表的相关的使用,可以让我们以后的python学习更有利。...问题 给定一组数,输出其最大与最小 示列: 输入:1 ,2, 3 ,4 输出:1 4 方法 可以利用python自带的函数max和min,还有用sorted给列表排序,输出其第一位和最后一位。...还可以用for和while循环来依次比较其大小,最后输出 实验结果与讨论 List_1 = [1, 2, 3, 4] print(max(list_1)) print(min(list_1)) List...: if i > a: a = i print(a) for i in list_1: if i <= a a = i print(a) 结语 数组有时候需要排序,用python自带的函数来求解数组的简单和最快捷的

    38910

    lol匹配算法

    第1步:确定你的实力: *假设你是solo,就直接使用你的个人匹配分(也就是elo匹配模式和排位赛有不同的匹配分) *假设你是预先组队的,你的匹配分是你队伍的平均分,而且会依据你组队的规模略微提高一些...第2步:确定你合适的对手: *首先,系统会基于你的elo,给你匹配跟你很相近的玩家。终于,系统会放宽匹配的条件,给你一些不是那么完美的匹配,由于你肯定也不想永远匹配不到人。...长期来讲,我的匹配分(Elo)是怎样被測量的? 我们使用了一个改动过的ELO系统。...*提升等级也会极大的提高你的elo。...这个要比一些我们曾见过的点对点算法-将随意的统计数据杂糅在一起推測分数-要可靠的多 发现这些优势,我们就知道对于预先组队的队伍,须要提高多少elo,来达成一个公平的匹配,确定一个适当的,在数学上合理的调整

    81120

    数组(获取

    数组的常见操作(获取) 1.获取需要进行比较,每一次比较都会有一个较大的,因为该不确定,通过一个变量进行存储 2.让数组中的每一个元素都和这个变量中的进行比较,如果大于了变量中的,就用该变量记录较大...3.当所有的元素都比较完成,那么该变量中存储的就是数组中的最大 初始化变量为第一个元素 初始化变量为索引,这个可以获取最大或者最大的脚标 java版: public class ArrayDemo...){ max=arr[x]; } } return max; } /** * 获取最大,...这个可以获取最大或者最大的脚标 * @param arr * @return */ public static int getMax2(int[] arr){...这个可以获取最大或者最大的脚标 * @param arr * @return */ public static function getMax2($arr){

    1.5K20

    『ACM-算法-ST算法』信息竞赛进阶指南--区间问题的ST算法

    任意一段的最小显然等于min(前半段最小,后半段最小)。 那么f[i][j]如何用其他状态来继承呢? j到j+2i-1的长度为2i,那么一半的长度就等于2^(i-1)。...②不过区间在增加时,每次并不是增加一个长度,而是基于倍增思想,用二进制右移,每次增加2^i个长度 ,最多增加logn次 这样预处理了所有2的幂次的小区间的 查询: ③对于每个区间,分成两段长度为的区间...,再取个(这里的两个区间是可以有交集的,因为重复区间并不影响) 比如3,4,6,5,3一种分成3,4,6和6,5,3,另一种分成3,4,6和5,3,最大都是6,没影响。...因为位置过了一半,所以x到y的最小可以表示为min(从x往后2t的最小,从y往前2t的最小),前面的状态表示为f[t][x] 设后面(从y往前2t的最小)的初始位置是k,那么k+2t-1=y,...,O(1)查询 但不支持修改 预处理时间复杂度O(nlogn),查询时间O(1)。

    44110
    领券