浅谈分块(综合篇目)
arfa
·
·
题解
浅谈分块
分块的用处?
分块可以处理区间的问题,作用类似于线段树。
分块的优缺点?
$II.$不过分块就是一个数组,所以空间复杂度是比较绝对的线性的,算起来就是$sqrt(n)*2+n$,就是$O(n)$。而线段树是$2*n$,虽然是$O(n)$,不过也是有点容易被卡的。
$III.$最后分块比较容易理解,适用于新手。
> ### 分块思想:优雅暴力
我们把一个数组(数的总数为$n$),分成$k$块,每一块有$kk$个数。怎么分呢?告诉你$kk$严格等于$sqrt(n)$,为什么?因为要均摊时间复杂度啊!(理解一下)
那么$k$一定有$sqrt(n)$块咯(因为$sqrt(n)^2=n$)。错!如果$k^2<>n$(也就是$n$不能被整开方),$k+=1/inc(k)$。(因为$n$并不一定完全平分)
好了,假设我们已经分好块了,我们要怎么知道下标为$n$的块是第几块?
$I.$假如$kk=4$。那么$1-4$是第一块,$5-8$是第二块,$9-12$是第三块.....
$II.$我们可以推出,如果$n\ mod\ kk=0$,那么下标$n$的块就是$n\ div\ kk$。否则就是$n\ div\ kk+1$。
```
1 2 3 4 5 6 7 8 9 10
■ ■ ■ ■ ■ ■ ■ ■ ■ ■
■■■■■ ■■■■■ ■■■■■ ■■■■■
```
$10$个数分为$4$块,每$1$块$3$个数。
> ### 分块怎么用?
我们分了块以后,我们就可以对其进行区间操作。首先先声明一些变量:$intersum,interadd,num$,意思分别为**一整块的值,整体加了多少,和一开始给的值**。
假如我们要把区间$l,r$全部加上$add$的话,我们就看这个区间内最左边的块的左下标和最右边的块的右下标(为了找出中间的块总和)。然后我们就对所有中间的块的$intersum[i]+add$,而多出来的,就$num[j]+add$就可以了(当然$i$可以重复用)。
也就是这样:
```
我修改(查询)区间3-10。
1 2 3 4 5 6 7 8 9 10
■ ■ ■ ■ ■ ■ ■ ■ ■ ■
■■■■■ ■■■■■ ■■■■■ ■■■■■
◆ ■■■■■■■■■■ ◆
```
其中◆就是要暴力$+add$的,而■就是一块一块区间加的。(要注意值改变的同时,$intersum$也要加)
无论是区间修改操作,还是区间查询操作,都可以这样弄。
> #### $Code
如果要看实现详情和细节,请看剪贴板。
猜想
我们再想一想,线段树可以干什么?
线段树可以求区间最大值,分块可以吗?假如我们有数组intermax存储的是区间最大,我们就可以对l,r区间进行最大块max,然后对多余的进行单个数max。这样子其实很多余,真的就不如O(n\ log\ n)或者ST表。(分块实现下界是O(sqrt(n)*3))。
线段树有权值线段树,分块可以存储权值吗?假如我们像求逆序对一样,每一个数(也就成了桶)都储存这出现次数。我们对其分块后,想要找a_i的逆序对,就直接在区间l,i区间和就可以了。
线段树分割出来主席树,分块又能怎样升华呢?那么本人很弱,就留给大家自己想吧。
例题
$II.$[线段树2](https://www.luogu.org/problemnew/show/P3373) 也是随便搞一搞,用分块可能会比线段树打懒标记好一些。
感谢 @larryzhong 大佬,推荐了这道题:[教主的魔法](https://www.luogu.org/problemnew/show/P2801)。这道题就是典型的分块的题目。为什么怎么了容易看出?
$N\leq1000000$。好的,还不信这道题一定要$O(n)$的复杂度。要注意线段树的点数是$2*N-1$。如果遇到的题空间很紧,请用分块。
至于区间问题,分块就很容易解决的啦。
(认真看完题目回来发现这题要用主席树qwq,是所以还是水分块吧qwq)