扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
位运算
创新互联是一家集网站建设、网站制作、网站页面设计、网站优化SEO优化为一体的专业网络公司，已为成都等多地近百家企业提供网站建设服务。追求良好的浏览体验,以探求精品塑造与理念升华,设计最适合用户的网站页面。 合作只是第一步，服务才是根本,我们始终坚持讲诚信，负责任的原则，为您进行细心、贴心、认真的服务,与众多客户在蓬勃发展的市场环境中,互促共生。
与& 或| 异或^ 左移<< 右移>>
\(x<
\(x>>y=\frac{x}{2^{y}}\)
\(2a+1=(a<<1)|1\)
\(a\)%\(2=a\)&\(1\)
st表
当st表合并的复杂度为\(O(1)\)时，st表构建的复杂度为\(O(nlogn)\),查询的复杂度为\(O(1)\)，但是st表并不支持修改。
求区间最大值/最小值：复杂度\(O(n)\)
st表的核心在于倍增和DP。
\(f[i][j]\)表示以第\(i\)个数作为左端点，长度为\(2^{j}\)的区间的最值，也就是\([i,i+2^{j}-1]\)的区间最值。
\(f[i][0]=a[i]\)
\(f[i][j]=merge(f[i][j-1],f[i+2^{j-1}][j-1])\)
询问一个区间\([l,r]\)的区间最值，
区间的极值就是两个长度为\(2^{k}\)的子区间的极值。
设 $ k = \left \lfloor log ( r - l + 1 ) \right \rfloor $ ,那么，
\(ans=merge\{f[l][k],f[r-2^{k}+1][k]\}\)
merge函数表示信息合并，询问最大值时用max，询问最小值时用min。
例题
【问题描述】
我们有一个n行m列的矩阵。
K次询问矩阵矩阵最值。
注意
1、如果块重叠对最后的答案有影响，那么不能使用st表处理。
2、调用一次cmath库中的\(log_{2}\)函数时间复杂度是\(O(logn)\)的，我们可以预处理出Log数组。
并非原创，仅是整理，请见谅
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网