区间最值问题-RQM(ST表，线段树)

1.ST表求解

ST表的实质其实是动态规划，下面是区间最小的递归公式，最大只需将min改成max即可

f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);

二维数组的f[i][j]表示从i开始连续2*j个数的最小/大值。

例如：我们给出一个数组a[10]={0,1,2,4,6,7,9,2,12,3};

我们可以给f[i][0]....f[n][0]先初始化为上面数组的值，我们将f[i][j]分为两端，一段是i到i+2^(j-1)-1为一段，i+2^(j-1)到i+2^j-1,f[i][j]就是分出来的这两个段的最大/小值。

于是有了递归公式。

写一道例题

P1816 忠诚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<set>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define TEST1 int T;cin>>T;while(T--)
#define TEST2 int T;T=1;while(T--)
#define lowbit(x) x&(-x) 
#define ll long long
using namespace std;
const int N = 100010;
const int M = 20;
int base1 = 131, base2 = 13311;
int p1 = 1e9 + 7, p2 = 1e9 + 9;
const ll mod = 1e9 + 7;
int n, a[N], f[N][M],m[N][M];
//创建ST表
void create() {
    //初始状态
    //f[i][0]表示从i开始长度为2^0的区间最值为a[i]本身
    for(int i = 1; i <= n; i ++) f[i][0] = a[i],m[i][0]=a[i];
    int k = log2(n);
    //枚举区间长度指数j
    for(int j = 1; j <= k; j ++)
        for(int i = 1; i + (1 << j) - 1 <= n; i ++)
        {
			f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
			m[i][j] = min(m[i][j - 1], m[i + (1 << j - 1)][j - 1]);
		}
            
}
//利用ST表查询区间[L,R]的最大值
int query1(int L, int R) {
	
    int k = log2(R - L + 1);
    return max(f[L][k], f[R - (1 << k) + 1][k]);
}
int query2(int L,int R)
{

	int k=log2(R-L+1);
	return min(m[L][k], m[R - (1 << k) + 1][k]);
}
int main()
{
    int m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) scanf("%d", a + i);
    create();
    while(m --) {
        int L, R;
        scanf("%d%d", &L, &R);
        printf("%d ", query2(L,R));
        
    }
}

其实就是区间最小值。

2.线段树

线段树其实也就是相当于区间分段，(a,b)的左孩子区间就是(a,(a+b)/2)和右孩子((a+b)/2+1,b)，(a.b)区间的最值就是他分出的两个区间的最值的最值。

对于上道例题的代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<set>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define TEST1 int T;cin>>T;while(T--)
#define TEST2 int T;T=1;while(T--)
#define lowbit(x) x&(-x) 
#define ll long long
using namespace std;
const int N = 2000010;
const int M = 1e9+2;
int base1 = 131, base2 = 13311;
int p1 = 1e9 + 7, p2 = 1e9 + 9;
const ll mod = 1e9 + 7;
ll n, m, a[N];
struct Node
{
	int l, r, minn = mod;
}tree[N];
void build(int i, int l, int r)
{
	tree[i] = { l,r };
	if (l == r)
	{
		tree[i].minn = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(i << 1, l, mid);
	build(i << 1 | 1, mid + 1, r);
	tree[i].minn = min(tree[i << 1].minn, tree[i << 1 | 1].minn);
}
int ask(int i, int l, int r)
{
	if (l == tree[i].l && r == tree[i].r) return tree[i].minn;
	int mid = tree[i].l + tree[i].r >> 1;
	if (r <= mid) return ask(i << 1, l, r);
	if (l > mid) return ask(i << 1 | 1, l, r);
	return min(ask(i << 1, l, mid), ask(i << 1 | 1, mid + 1, r));
}
void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	build(1, 1, n);
	for (int i = 1; i <= m; i++)
	{
		int l, r;
		cin >> l >> r;
		cout << ask(1, l, r) << " ";
	}
}
int main()
{
	TEST2
	solve();
	return 0;
}

3.其他例题

1.奶牛排队

1274. 奶牛排队 - AcWing题库

区间最大值与最小值的差

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<set>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define TEST1 int T;cin>>T;while(T--)
#define TEST2 int T;T=1;while(T--)
#define lowbit(x) x&(-x) 
#define ll long long
using namespace std;
const int N = 100010;
const int M = 20;
int base1 = 131, base2 = 13311;
int p1 = 1e9 + 7, p2 = 1e9 + 9;
const ll mod = 1e9 + 7;
int n, a[N], f[N][M],m[N][M];
//创建ST表
void create() {
    //初始状态
    //f[i][0]表示从i开始长度为2^0的区间最值为a[i]本身
    for(int i = 1; i <= n; i ++) f[i][0] = a[i],m[i][0]=a[i];
    int k = log2(n);
    //枚举区间长度指数j
    for(int j = 1; j <= k; j ++)
        for(int i = 1; i + (1 << j) - 1 <= n; i ++)
        {
			f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
			m[i][j] = min(m[i][j - 1], m[i + (1 << j - 1)][j - 1]);
		}
            
}
//利用ST表查询区间[L,R]的最大值
int query1(int L, int R) {
	
    int k = log2(R - L + 1);
    return max(f[L][k], f[R - (1 << k) + 1][k]);
}
int query2(int L,int R)
{

	int k=log2(R-L+1);
	return min(m[L][k], m[R - (1 << k) + 1][k]);
}
int main()
{
    int m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) scanf("%d", a + i);
    create();
    while(m --) {
        int L, R;
        scanf("%d%d", &L, &R);
        printf("%d\n", query1(L,R)-query2(L,R));
        
    }
}

2.求m区间内的最小值

P1440 求m区间内的最小值 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<set>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#define TEST1 int T;cin>>T;while(T--)
#define TEST2 int T;T=1;while(T--)
#define lowbit(x) x&(-x) 
#define ll long long
using namespace std;
const int N = 2000010;
const int M = 1e9 + 2;
int base1 = 131, base2 = 13311;
int p1 = 1e9 + 7, p2 = 1e9 + 9;
const ll mod = 1e9 + 7;
ll n, m, a[N];
struct Node
{
	ll l, r, minn = mod;
}tree[N];
void build(int i, int l, int r)
{
	tree[i] = { l,r };
	if (l == r)
	{
		tree[i].minn = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(i << 1, l, mid);
	build(i << 1 | 1, mid + 1, r);
	tree[i].minn = min(tree[i << 1].minn, tree[i << 1 | 1].minn);
}
int ask(int i, int l, int r)
{
	if (l == tree[i].l && r == tree[i].r) return tree[i].minn;
	int mid = tree[i].l + tree[i].r >> 1;
	if (r <= mid) return ask(i << 1, l, r);
	if (l > mid) return ask(i << 1 | 1, l, r);
	return min(ask(i << 1, l, mid), ask(i << 1 | 1, mid + 1, r));
}
void solve()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	build(1, 1, n);
	for (int i = 1; i <= n; i++)
	{
		if (i == 1)
		{
			cout << "0\n";
			continue;
		}
		int l=max(1ll,i-m), r=i-1;
		cout << ask(1, l, r) << "\n";
	}
}
int main()
{
	TEST2
		solve();
	return 0;
}

用单调队列更简单。。。

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【论文解读】可灵(快手)｜LivePortrait：具有拼接和重定向控制的高效肖像动画

【论文解读】可灵(快手)｜LivePortrait：具有拼接和重定向控制的高效肖像动画

&#x1f4dc; 文献卡 英文题目: LivePortrait: Efficient Portrait Animation with Stitching and Retargeting Control;作者: Jianzhu Guo; Dingyun Zhang; Xiaoqiang Liu; Zhizhou Zhong; Yuan Zhang; Pengfei Wan; Di ZhangDOI: 10.48550/arXiv.2407.03168摘要翻译: *旨在…
阅读更多...
ESP32CAM物联网教学02

ESP32CAM物联网教学02

ESP32CAM物联网教学02 物联网门锁 小智来到姑姑家门口&#xff0c;按了门铃&#xff1b;还在公司上班的姑姑用电脑给小智开了门&#xff0c;让他先进屋休息。小智对物联网门锁产生了兴趣&#xff1a;什么是物联网&#xff1f;为什么这么厉害&#xff1f; 初识物联网 我们在百…
阅读更多...
【论文阅读笔记】Meta 3D AssetGen

【论文阅读笔记】Meta 3D AssetGen

【论文阅读笔记】Meta 3D AssetGen: Text-to-Mesh Generation with High-Quality Geometry, Texture, and PBR Materials Info摘要引言创新点 相关工作T23D基于图片的3d 重建使用 PBR 材料的 3D 建模。 方法文本到图像:从文本中生成阴影和反照率图像Image-to-3D:基于pbr的大型重…
阅读更多...
python 比webdriver更好用的ChromiumPage

python 比webdriver更好用的ChromiumPage

优点&#xff08;目前发现的&#xff09;&#xff1a; 不用配合selenium不用下载对应浏览器的webdriver&#xff0c;不用对应浏览器版本不用设置webdriver路径之类的设置目前没看到有出现像webdriver类似的浏览器被控制的提示&#xff0c;使用过程中好像也没被检测出来。每次不…
阅读更多...
unity3d：Shader知识点，矩阵，函数，坐标转换，Tags，半透明，阴影，深度，亮度，优化

unity3d：Shader知识点，矩阵，函数，坐标转换，Tags，半透明，阴影，深度，亮度，优化

基本结构 Shader "MyShaderName" {Properties {// 属性}SubShader {// 针对显卡A的SubShaderPass {// 设置渲染状态和标签Tags { "LightMode""ForwardBase" }// 开始Cg代码片段CGPROGRAM// 该代码片段的编译指令&#xff0c;例如&#xff1a;#p…
阅读更多...
【vite创建项目】

【vite创建项目】

搭建vue3tsvitepinia框架 一、安装vite并创建项目1、用vite构建项目2、配置vite3、找不到模块 “path“ 或其相对应的类型声明。 二、安装element-plus1、安装element-plus2、引入框架 三、安装sass sass-loader1、安装sass 四、安装vue-router-next 路由1、安装vue-router42搭…
阅读更多...
python基础篇（8）：异常处理

python基础篇（8）：异常处理

在Python编程中&#xff0c;异常是程序运行时发生的错误&#xff0c;它会中断程序的正常执行流程。异常处理机制使得程序能够捕获这些错误&#xff0c;并进行适当的处理&#xff0c;从而避免程序崩溃。 1 错误类型 代码的错误一般会有语法错误和异常错误两种&#xff0c;语法错…
阅读更多...
CTF常用sql注入（一）联合注入和宽字节

CTF常用sql注入（一）联合注入和宽字节

0x01 前言 给自己总结一下sql注入的常用姿势吧&#xff0c;记录一下学习 0x02 联合 联合注入的关键词是union SQL的union联合注入原理是联合两个表进行注入攻击&#xff0c;使用union select关键词来进行联合查询。 那么为什么我们在题目中一般是只写一个呢 因为 $sql &quo…
阅读更多...
逆变器学习笔记（三）

逆变器学习笔记（三）

DCDC电源芯片外围器件选型_dcdc的comp补偿-CSDN博客、 1.芯片的COMP引脚通常用于补偿网络&#xff1a; 芯片的COMP引脚通常用于补偿网络&#xff0c;在控制环路中发挥重要作用。COMP引脚接电容和电阻串联接地&#xff0c;主要是为了稳定控制环路、调整环路响应速度和滤波噪声…
阅读更多...
cs231n作业1——SVM

cs231n作业1——SVM

参考文章&#xff1a;cs231n assignment1——SVM SVM 训练阶段&#xff0c;我们的目的是为了得到合适的 &#x1d44a; 和 &#x1d44f; &#xff0c;为实现这一目的&#xff0c;我们需要引进损失函数&#xff0c;然后再通过梯度下降来训练模型。 def svm_loss_naive(W, …
阅读更多...
NAT 打洞

NAT 打洞

由于 ipv4 地址数量的有限性&#xff0c;导致实际网络部署模式中存在大量的 NAT 网络。对于 NAT 内部的主机&#xff0c;可以主动发起去公网的流量&#xff0c;但对于位于不同 NAT 内的两台主机而言&#xff0c;想要直接进行点对点的连接&#xff0c;就需要用到打洞技术了。 常…
阅读更多...
Bash ——shell

Bash ——shell

Bash作为用户与操作系统之间的接口&#xff0c;让用户通过命令行输入各种指令来控制和操作计算机系统。 shell的两种解释&#xff1a; 1.linux命令解释器 Terminal 终端 ——》shell命令 ——》 Linux kernel &#xff08;内核&#xff09; Linux内核的作用&#xff1a; 1.…
阅读更多...
AI与编程：一个学生的心路历程与思考

AI与编程：一个学生的心路历程与思考

前言 大家好&#xff0c;本人是在一个在校的大学生&#xff0c;方向是前端语言。爱好是码代码和看一点小新闻&#xff0c;游戏也是喜爱的。其实本篇文章的想法是源于网上一些人对AI以及对前端的看法&#xff0c;看完网上的评论后我也是有感而发。本篇文章的讨论中心也是围绕着A…
阅读更多...
IDA*——AcWing 180. 排书

IDA*——AcWing 180. 排书

IDA* 定义 IDA*&#xff08;Iterative Deepening A*&#xff09;是一种结合了深度优先搜索&#xff08;DFS&#xff09;的递归深度限制特性和A搜索的启发式估价函数的搜索算法。它主要用于解决启发式搜索问题&#xff0c;尤其是当搜索空间很大或者搜索成本不确定时。 IDA* 是…
阅读更多...
SprongBoot及其基础应用全套部署脚本和配置

SprongBoot及其基础应用全套部署脚本和配置

POM.xml配置 </dependencies> <!--skywalking日志监控依赖--><dependency><groupId>org.apache.skywalking</groupId><artifactId>apm-toolkit-logback-1.x</artifactId><version>8.5.0</version></dependency&g…
阅读更多...
轻松驾驭开发之旅：Maven配置阿里云CodeUp远程私有仓库全攻略

轻松驾驭开发之旅：Maven配置阿里云CodeUp远程私有仓库全攻略

文章目录 引言一、为什么选择阿里云CodeUp作为远程私有仓库&#xff1f;二、Maven配置阿里云CodeUp远程私有仓库的步骤准备工作配置Maven的settings.xml文件配置项目的pom.xml文件验证配置是否成功 三、使用阿里云CodeUp远程私有仓库的注意事项 引言 在软件开发的世界里&#…
阅读更多...
软件工程（上）

软件工程（上）

目录 软件过程模型&#xff08;软件开发模型&#xff09; 瀑布模型 原型模型 V模型 构件组装模型 螺旋模型&#xff08;原型瀑布&#xff09; 基于构件的软件工程&#xff08;CBSE&#xff09; 快速应用开发模型&#xff08;RAD&#xff09; 统一过程&#xff08;UP&a…
阅读更多...
Http Json参数到x-www-form-urlencoded参数的在线转换工具

Http Json参数到x-www-form-urlencoded参数的在线转换工具

Json参数到x-www-form-urlencoded参数的在线转换工具
阅读更多...
C语言 printf 函数多种输出格式以及占位输出

C语言 printf 函数多种输出格式以及占位输出

一、输出格式 在C语言中&#xff0c;printf 函数提供了多种输出格式&#xff0c;用于控制不同类型数据的输出方式。 1.整数输出格式 %d&#xff1a;以十进制形式输出整数。 %o&#xff1a;以八进制形式输出整数&#xff08;无前导0&#xff09;。 %x 或 %X&#xff1a;以十六进…
阅读更多...
CMD命令详细介绍 | 超详细版本！

CMD命令详细介绍 | 超详细版本！

文章目录 启动cmd命令用户启动使用管理员的账号启动 文件夹命令网络命令其他常用命令介绍常用快捷方式程序员相关命令 本文参考了博客园一篇帖子&#xff0c;ULR&#xff1a;cmd常用命令介绍(可收藏) - Mrwhite86 - 博客园 (cnblogs.com) CMD是Windows操作系统自带的命令行解释…
阅读更多...
最新文章

Copyright @ 2022~2023