当前位置:网站首页>Array proof during st table preprocessing
Array proof during st table preprocessing
2022-07-07 06:18:00 【Harris-H】
ST Array proof during table preprocessing
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)
Recurrence equation : a i = a i 2 + 1 a_i=a_{\small\dfrac{i}{2}}+1 ai=a2i+1
prove :
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
Certificate completion .
So you can O ( n ) O(n) O(n) Preprocessing logarithmic array .
then O ( 1 ) O(1) O(1) Realize interval query .
Attached with one 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; // Attention from 2 Start
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;
边栏推荐
- 当我们谈论不可变基础设施时,我们在谈论什么
- 一个简单的代数问题的求解
- Markdown 并排显示图片
- CloudCompare-点对选取
- [FPGA] EEPROM based on I2C
- Find duplicate email addresses
- 软件测试知识储备:关于「登录安全」的基础知识,你了解多少?
- Personal imitation SSM framework
- JMeter's own functions are not enough? Why don't you develop one yourself
- If you don't know these four caching modes, dare you say you understand caching?
猜你喜欢
【FPGA教程案例13】基于vivado核的CIC滤波器设计与实现
JVM命令之 jstat:查看JVM統計信息
Dc-7 target
postgresql 数据库 timescaledb 函数time_bucket_gapfill()报错解决及更换 license
Ideas of high concurrency and high traffic seckill scheme
How to set up in touch designer 2022 to solve the problem that leap motion is not recognized?
win系统下安装redis以及windows扩展方法
基于ADAU1452的DSP及DAC音频失真分析
开发者别错过!飞桨黑客马拉松第三期链桨赛道报名开启
Software testing knowledge reserve: how much do you know about the basic knowledge of "login security"?
随机推荐
The solution of a simple algebraic problem
Mac version PHP installed Xdebug environment (M1 version)
yarn入门(一篇就够了)
3531. 哈夫曼树
Red hat install kernel header file
Go语学习笔记 - gorm使用 - gorm处理错误 | Web框架Gin(十)
Rk3399 platform development series explanation (WiFi) 5.53, hostapd (WiFi AP mode) configuration file description
693. 行程排序
How to keep accounts of expenses in life
如何在Touch Designer 2022版中设置解决Leap Motion不识别的问题?
Go language learning notes - Gorm use - Gorm processing errors | web framework gin (10)
[cloud native] what is the microservice architecture?
JVM命令之- jmap:导出内存映像文件&内存使用情况
Solve pod install error: FFI is an incompatible architecture
Redisl garbled code and expiration time configuration
SAP Spartacus checkout 流程的扩展(extend)实现介绍
Find duplicate email addresses
JVM命令之 jstat:查看JVM統計信息
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
对称的二叉树【树的遍历】