ST表详解
创始人
2025-05-29 06:09:17
0次

ST表（实现O(1)静态查询区间最值）

st表应用场景： max(f[i], f[i]) = f[i]
符合这个形式就可以用st表，比如最大值最小值，最小公倍数，最大公约数 ST表思想感觉还是二进制的应用
1. 每个数字都有自己的二进制表示
2. 即每个数字都可以用几个不同的2的次方长度表示出来
3. 比如13 （1101）
4. 1到13这个区间就可以表示为1--7，8--11，12--13即长度之和为8+4+1
5. 这样我们定义f[i][j]数组含义为从i开始长度为2的j次方的区间的最大值
6. 这样任何区间的最大值都能用f数组表示
7. 1到13区间的最大值就等于max(f[1][3], f[8][2],f[12][1])，但这样是O(logn)时间;
8. 但我们要实现O(1)查询，所以我们发现最值可以区间重复即1--5的区间最值可以表示为1到4的区间最值和2到5区间最值 中的最值
9. 所以我们可以用两个有交集的区间来表示我们所求的区间最值，而且必须保证这两个区间必须覆盖我们所求区间，我们发现两个区间长度（1 << log2(len)）一定大于原本的长度len，这里log2向下取整，因为这里本来就是以2为底的对数，两个这么长的区间长度加起来相当于原本log2(len) + 1的长度了，所以两个(1 << log2(len))的长度一定可以覆盖len，然后我们分别从这个区间开头取这个长度，和从这个区间的结尾取这个长度，然后求他俩的最值，就是原本我们所求区间最值了 
[洛谷ST模板题](https://www.luogu.com.cn/problem/P3865)
#include
#include
#include
#includeusing namespace std;const int N = 1e5 + 10;int f[N][50];
int n, m;inline int read(){int x = 0, f= 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x*10 + ch - 48;ch = getchar();}return x*f;
}int main(){n = read();m = read();for(int i = 1; i <= n; i ++){f[i][0] = read();}for(int j = 1; j <= log2(n); 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]);}}while(m --){int l, r;l = read();r = read();int len = r - l + 1;int lo = (int)log2(len);printf("%d\n", max(f[l][lo], f[r-(1<
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：deployment 滚动升级中的过程

下一篇：Stellar Data Recovery Toolkit 11.0 Crack

相关内容

热门资讯

linux入门---制作进度条 了解缓冲区 我们首先来看看下面的操作： 我们首先创建了一个文件并在这个文件里面添加了...
C++ 机房预约系统（六）：学... 8、 学生模块 8.1 学生子菜单、登录和注销 实现步骤： 在Student.cpp的...
JAVA多线程知识整理 Java多线程基础 线程的创建和启动 继承Thread类来创建并启动 自定义Thread类的子类&#...
【洛谷 P1090】[NOIP... [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G ...
国民技术LPUART介绍 低功耗通用异步接收器（LPUART） 简介 低功耗通用异步收发器...
城乡供水一体化平台-助力乡村振... 城乡供水一体化管理系统建设方案 城乡供水一体化管理系统是运用云计算、大数据等信息化手段࿰...
程序的循环结构和random库...   第三个参数就是步长     引入文件时记得指明字符格式，否则读入不了 ...
中国版ChatGPT在哪些方面... 目录 一、中国巨大的市场需求 二、中国企业加速创新 三、中国的人工智能发展 四、企业愿景的推进 五、...
报名开启 | 共赴一场 Flu... 2023 年 1 月 25 日，Flutter Forward 大会在肯尼亚首都内罗毕...
汇编00-MASM 和 Vis... Qt源码解析 索引 汇编逆向--- MASM 和 Visual Studio入门 前提知识ÿ...
【简陋Web应用3】实现人脸比... 文章目录🍉 前情提要🌷 效果演示🥝 实现过程1. u...
前缀和与对数器与二分法 1. 前缀和 假设有一个数组，我们想大量频繁的去访问L到R这个区间的和，...
windows安装JDK步骤 一、 下载JDK安装包 下载地址：https://www.oracle.com/jav...
分治法实现合并排序(归并排序)... 🎊【数据结构与算法】专题正在持续更新中，各种数据结构的创建原理与运用✨...
在linux上安装配置node... 目录前言1，关于nodejs2，配置环境变量3，总结 前言...
Linux学习之端口、网络协议... 端口：设备与外界通讯交流的出口 网络协议： 　　网络协议是指计算机通信网...
Linux内核进程管理并发同步... 并发同步并发 是指在某一时间段内能够处理多个任务的能力，而 并行 是指同一时间能够处理...
opencv学习-HOG LO... 目录1. HOG(Histogram of Oriented Gradients,方向梯度直方图)1...
EEG微状态的功能意义 导读大脑的瞬时全局功能状态反映在其电场结构上。聚类分析方法一致地提取了四种头表面脑电场结构ÿ...
【Unity 手写PBR】Bu... 写在前面 前期积累： GAMES101作业7提高-实现微表面模型你需要了解的知识 【技...