[洛谷日报第20期]浅谈基础根号算法——分块（二）

2018-08-04 21:32 分类：滚动来源：洛谷科技

『甘肃龙网摘要_[洛谷日报第20期]浅谈基础根号算法——分块（二）』但是，如何用分块来维护区间最值？ 我们举个例子: 给定一个长的为n数列，求出任意区间[l,r]的最大值(1=l,r=n)(l=r) 可能你会说：我会线段树！ 但是拿分块又怎么做呢？ ----[洛谷日报第20期]浅谈基础根号算法——分...


但是，如何用分块来维护区间最值？

我们举个例子:

给定一个长的为n数列，求出任意区间[l,r]的最大值(1<=l,r<=n)(l<=r)

可能你会说：我会线段树！

但是拿分块又怎么做呢？

----[洛谷日报第20期]浅谈基础根号算法——分块//----甘肃龙网 //

还是拿这张图，我们现在给每个点上加了一个权值，每个块维护一下块内最大值

当我们查询任意一个区间[l,r]时，如果l所在的块与r所在的块相同，如[1,2]，则直接暴力查询即可，时间复杂度O(√n)

若其不在一个块但是块是相邻的，一样是暴力查询，时间复杂度O(√n)

若其块不相邻，如[1,10]，我们先处理两边的边块角块，先暴力查询1和10所在的块内最大值，最后直接查询中间块内最大值即可，时间复杂度O(√n)

所以总时间复杂度O(√n)

那如果加入了区间修改，又该怎么办呢？

我还是不用线段树(当然也不用树套树)

对于整块修改，我们打个加法标记，即当前块增加了多少，最大值相应的就增加了多少

而多于边块角块，暴力修改，特判最大值即可

所以总时间复杂度也是O(√n)

分块还能解决很多很麻烦的问题，比如寻找区间内前驱后继

我会树套树！

不好意思树套树太麻烦了

分块解法也非常的好理解，当我们分块的时候，就对每一个块进行排序，查找时，边块角块依旧暴力，整块使用lower_bound和upper_bound二分查找即可

推荐

会·生活

漫荒咋办

阅读(28)

有时刻发明可以看的也没保持下去，就是不感兴趣，还要等待真正爱好的番啊...

潮·科技

一加Nordn10 5g和100即将发布，中低端手机？

阅读(30)

其实现在能够看出来的一件事 ， 一加现在也开始逐渐增加自己的产品数量 ， 当然就是说现在不光是专门做旗舰手机了 ， 当然 ， 这是一个算是被动的改变 ， 一加看起来要发布新品了...