当前位置:网站首页>ST表预处理时的数组证明
ST表预处理时的数组证明
2022-07-07 01:25:00 【Harris-H】
ST表预处理时的数组证明
a i = x ( 2 x ≤ i < 2 x + 1 ) a_i=x(2^x\le i< 2^{x+1}) ai=x(2x≤i<2x+1)
递推方程: a i = a i 2 + 1 a_i=a_{\small\dfrac{i}{2}}+1 ai=a2i+1
证明:
a i 2 = x a_{\dfrac{i}{2}}=x a2i=x
2 x ≤ i 2 < 2 x + 1 2^x\le \dfrac{i}{2}<2^{x+1} 2x≤2i<2x+1
∴ 2 x + 1 ≤ i < 2 x + 2 \therefore 2^{x+1}\le i<2^{x+2} ∴2x+1≤i<2x+2
2 × i 2 ≤ i ≤ 2 x + 2 2\times \dfrac{i}{2}\le i\le2^{x+2} 2×2i≤i≤2x+2
证毕。
因此可以 O ( n ) O(n) O(n) 预处理对数数组。
然后 O ( 1 ) O(1) O(1) 实现区间查询。
附一个RMQ。
#define il inline
struct RMQ{
int f[N][20],b[N];//pay attention init f[i][0]
il void init(int n){
for(int i=2;i<=n;i++) //pre deal with
b[i]=b[i>>1]+1; //注意从2开始
for(int j=1;j<=b[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]);
}
il int que(int l,int r){
int x=b[r-l+1];
return max(f[l][x],f[r-(1<<x)+1][x]);
}
}rm;
边栏推荐
- CTFshow--常用姿势
- Ten stages of becoming a Senior IC Design Engineer. What stage are you in now?
- JVM监控及诊断工具-命令行篇
- SAP Spartacus checkout 流程的扩展(extend)实现介绍
- Bbox regression loss function in target detection -l2, smooth L1, IOU, giou, Diou, ciou, focal eiou, alpha IOU, Siou
- PTA 天梯赛练习题集 L2-002 链表去重
- Convert numbers to string strings (to_string()) convert strings to int sharp tools stoi();
- [FPGA tutorial case 14] design and implementation of FIR filter based on vivado core
- 目标检测中的损失函数与正负样本分配:RetinaNet与Focal loss
- Flask 1.1.4 werkzeug1.0.1 analyse du code source: processus de démarrage
猜你喜欢
10W word segmentation searches per second, the product manager raised another demand!!! (Collection)
PTA 天梯赛练习题集 L2-004 搜索树判断
Opensergo is about to release v1alpha1, which will enrich the service governance capabilities of the full link heterogeneous architecture
Jcmd of JVM command: multifunctional command line
Industrial Finance 3.0: financial technology of "dredging blood vessels"
Introduction to yarn (one article is enough)
深度聚类:将深度表示学习和聚类联合优化
ML's shap: Based on the adult census income binary prediction data set (whether the predicted annual income exceeds 50K), use the shap decision diagram combined with the lightgbm model to realize the
window下面如何安装swoole
go-microservice-simple(2) go-Probuffer
随机推荐
JVM监控及诊断工具-命令行篇
10W word segmentation searches per second, the product manager raised another demand!!! (Collection)
@pathvariable 和 @Requestparam的详细区别
绕过open_basedir
老板总问我进展,是不信任我吗?(你觉得呢)
Swagger3 configuration
Change the original style of UI components
JVM命令之 jstat:查看JVM統計信息
PTA 天梯赛练习题集 L2-004 搜索树判断
mac版php装xdebug环境(m1版)
Loss function and positive and negative sample allocation in target detection: retinanet and focal loss
CTFshow--常用姿势
cf:C. Column Swapping【排序 + 模拟】
PTA ladder game exercise set l2-004 search tree judgment
[InstallShield] Introduction
Go language learning notes - Gorm use - native SQL, named parameters, rows, tosql | web framework gin (IX)
Go语学习笔记 - gorm使用 - 原生sql、命名参数、Rows、ToSQL | Web框架Gin(九)
Introduction to yarn (one article is enough)
Bbox regression loss function in target detection -l2, smooth L1, IOU, giou, Diou, ciou, focal eiou, alpha IOU, Siou
window下面如何安装swoole