提高组知识1——ST表

[王皓宇 (小鸽子)]

和区间总和不同，最大值的维护可不是加加减减能做到的

那么我们先想一个小笨蛋做法

对于每次查询直接循环遍历

复杂度O(nm)

有点小炸

那我们稍微思考一下

不用修改的话，预处理也没关系哦~

直接维护所有区间的最大值

O(n²)，时间空间都有点炸

仔细思考一下

我们n²预处理，O(1)查询，复杂度能不能平均一下？

这里思考（shui）一下

---

可以的兄弟，可以的

考虑一下，你转移的时候是不是 A_{i,j} 直接从 A_{i,j-1} 转移过来的

但是m才2e6，转移这么多是否有一点冗余？

包的呀，不然我说它干嘛

那么我们就把他一分为二

这样 A_{i,j} 就可以从 A_{i,j/2} 转移过来

但我们明显是想要预处理更快，查询可以稍慢

那怎么办？

看一下

这是我们在处理 A_{1,4} 时用的所有值

那么长度为len的区间需要的值的数量不会超过len²（len>2，在len = 2ⁿ - 1 时为 2n-1）

但 len 不一定是2的幂次，但是求最大值，可以将区间拆分，也可以重叠

拆分的话和求和一样，分成多段并不会影响结果

重叠的话无非就是把重叠部分算两遍，求极值的话也不会影响结果（求和不行！！！）

既然不会影响结果，那我们就定义 st_{i,j} 是 i 往后 2^j 的数据最大值

如此一来我们就只需要考虑如何刚刚好 覆盖目标区域

回到这个问题

我们转换一下，给你一个正整数len，问你是否存在 k = 2ⁿ ,满足 k ≤ len 且 2k > len

这个k是绝对有的

首先，条件1只需要n≤log2(len)

其次，条件2不满足时，将k = 2k就行，因为它还是2的幂次

如何证明一定有k满足条件？

你可以把这个再转一下

(k ≤ len & 2k > len) => (k ≤ len & !(2k ≤ len))

就是当前满足，下一个不满足条件一

k 就是小于等于len的最大的二的幂次即 k = 2^{ ⌊log2(len)⌋}

答案就是 max(st[l][j],st[r-k+1][j])

达利园真好吃

下课！！！

[yhxyd0109 (章子木)]

依旧 达利园真好吃

[王皓宇 (小鸽子)]

憧憬也很好看哦~（bushi）

[杨子墨1 (yhxyd95)]

达利园好吃