RMQ算法

一.概述

RMQ(Range Minimum/Maximum Query),即区间最值查询,是指这样一个问题:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在i,j之间的最小/大值。这两个问题是在实际应用中经常遇到的问题,下面介绍一下解决这两种问题的比较高效的算法。当然,该问题也可以用线段树(也叫区间树)解决,算法复杂度为:O(N)~O(logN),这里我们暂不介绍

二.算法思路

1.首先利用dp预处理出从i点开始往后的2^j的最大值,dp的时候将其拆分成两段

2.查询出左端点以i开始,终点以j开始的最大值

一篇非常好的博客http://blog.csdn.net/liang5630/article/details/7917702

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 int a[2000001];
 7 int minn[2000001][15];
 8 int fastpow(int a,int p)
 9 {
10     int base=a;
11     int ans=1;
12     while(p)
13     {
14         if(p%2)ans*=base;
15         base*=base;
16         p/=2;
17     }
18     return ans;
19 }
20 int main()
21 {
22     int n,m;
23     scanf("%d%d",&n,&m);
24     for(int i=0;i<=n;i++)
25         for(int j=0;j<=14;j++)
26         minn[i][j]=0x7ff;
27     for(int i=1;i<=n;i++)
28         scanf("%d",&minn[i][0]);// 第i个点跳1步能到达的点是其本身 
29     for(int j=0;j<=14;j++)// 2^j 
30     {
31         for(int i=1;i<=n;i++)// 根据dp的无后效性,要在j一定的情况下把每一个点跳完之后能到达的位置处理出来 
32         {
33             if(i+(1<<j)-1<=n)// 第二段区间保证在范围之内 
34             minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j]);
35         }
36     }
37     // 三段区间 i——i+2^(j-1)-1——i+2^j-1 
38     printf("0\n");
39     int k=log(m)/log(2);// 保证求值区间的长度在要求的范围之内 
40     // 带求区间 i-m to i
41     for(int i=2;i<=n;i++)
42     {
43         printf("%d\n",min(minn[i-m][k],minn[i-fastpow(2,k)+1][k]));
44         //                左端点            右端点 
45     }
46     return 0;
47 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ 3932: [CQOI2015]任务查询系统(主席树)

15100
来自专栏灯塔大数据

每周学点大数据 | No.41 join 操作

No.41期 join 操作 Mr. 王:第一个话题就是 join 操作。 join 操作在数据库中还是非常常见的。 小可:这个 join 指的是笛卡儿积操...

39370
来自专栏SeanCheney的专栏

《Pandas Cookbook》第08章 数据清理1. 用stack清理变量值作为列名2. 用melt清理变量值作为列名3. 同时stack多组变量4. 反转stacked数据5. 分组聚合后uns

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

20320
来自专栏恰童鞋骚年

剑指Offer面试题:27.最小的k个数

  这道题是典型的TopK问题,其最简单的思路莫过于把输入的n个整数排序,排序之后位于最前面的k个数就是最小的k个数。这种思路的时间复杂度是O(nlogn),但...

16920
来自专栏编程

这或许是对小白最友好的python入门了吧——9,数字深入体验

先给大家介绍一个函数:range(),这个函数是用来干嘛的呢?很简单,数数的,怎么数呢,我先给大家演示一下: for num in range(1,5): ...

21790
来自专栏王小雷

Python之数据聚合与分组运算

Python之数据聚合与分组运算 1. 关系型数据库方便对数据进行连接、过滤、转换和聚合。 2. Hadley Wickham创建了用于表示分组运算术语“spl...

27390
来自专栏性能与架构

Mysql order by排序优化

1. 加大max_length_for_sort_data参数的设置 在MySQL中,排序算法分为两种,一是只加载排序字段到内存,排序完成后再到表中取其他字段,...

37550
来自专栏闻道于事

数据库规范与数据类型选择

NUMBER :精度最高可达20个基数-100位,相当于39或40位十进制数,具体取决于小数点的位置。

23430
来自专栏JetpropelledSnake

Django学习笔记之Django QuerySet的方法

13950
来自专栏xingoo, 一个梦想做发明家的程序员

Lucene查询语法详解

Lucene查询 Lucene查询语法以可读的方式书写,然后使用JavaCC进行词法转换,转换成机器可识别的查询。 下面着重介绍下Lucene支持的查询: Te...

58790

扫码关注云+社区

领取腾讯云代金券