分块

· · 个人记录

这是神奇的分块。

分块是一种基于暴力演变而来的数据结构思想（并非完全是数据结构），其原理非常原始和简单，也比较好写。

怎么说呢，分块其实是线段树的低配版，毕竟它们两个都是块状数据结构，并且都支持单/区的修/询，能维护各种值（譬如max，sum等），甚至在做区修时都可以使用懒标记来提升效率。

分块的基本套路是将一个区间分成几个长度相等的块（最后一个块的块长不一定是之前的块长）

例如：数组a 为

1 1 4 5 1 4 1 9 1 9 8 1 0 8 8 4 8

一共有17个数。

我们按照4个一块将其分为4块。

1 1 4 5 \qquad 1 4 1 9 \qquad 1 9 8 1 \qquad 0 8 8 4 \qquad8

在讲述后述内容前：

我们先声明一些定义：

给出公式：

第 i 个元素所在的块为第 \dfrac{(i-1)}{S}+1 个块

第 i 个块的起始位置为第 (i-1) \times S + 1 个元素，结束位置为第 n（数列长度）个元素（也就是数列末尾）或第 i\times S 个元素

约定：

数列（区间）长度为 n

块长（相等）长度为 S

\dfrac{(i-1)}{S}+1 = calc(i) (i-1) \times S + 1 = start(i) i\times S = end(i)

块长为 \sqrt n 时分块的复杂度最优，关于证明，在后面会讲到。

啊不是，8848胎核精野兽先辈手坤

问题1

在处理一个区间时，我们将其分为三个区间：

比如处理区间3~15，就将其分为：

4 5 \quad \qquad 1 4 1 9 \quad\! 1 9 8 1 \qquad \quad 0 8 8

中间两个块为中间整块。左右散块分别为"4 5" 和 "0 8 8".

假设我们需要如下操作：

首先对于修改操作，我们直接修改原数组 a[i] 即可。

然后由于我们的分块是个块状数据结构，我们对于每个整块都用一个数组记录每个块的最大值 max[calc(i)] ，并且通过修改最大值来快速查询。

所以，当我们修改完了该块时，我们需要修改这个块所属的max[calc(i)].

然后查询的时候，分别从左右两个散块所在的数列中暴力查找最大值，然后从中间的整块中暴力查找 max[calc(i)] ，最后比较三个区域的答案，返回最终的答案

代码：

void Modify(int x,int y) //将第x个数加y
{
  int k=(x-1)/s+1; //k为x所在块块号
  int L=(k-1)*s+1; //第k块的左界
  int R=k*s; //第k块的右界
  Max[k]=-inf;
  a[x]+=y;
  for(int i=L;i<=R;i++)
    if(a[i]>Max[k])Max[k]=a[i];
}

int Query(int x,int y) //询问a数列区间[x,y]的最大值
{
  int i=(x-1)/s+1; //i为x所在块块号，s为块长
  int j=(y-1)/s+1; //j为y所在块块号
  int ans=-inf;
  if(i==j) //[x,y]在同一块中，直接暴力枚举
  {
    for(int k=x;k<=y;k++)
    if(ans<a[k])ans=a[k];
  }
  else 
  {
    for(int k=x;k<=i*s;k++)//左侧部分
        if(ans<a[k])ans=a[k];
    for(int k=(j-1)*s+1;k<=y;k++)//右侧
        if(ans<a[k])ans=a[k];
    for(int k=i+1;k<j;k++)//被覆盖的整块
        if(ans<Max[k])ans=Max[k];
  }
  return ans;
}

int main()
{
  int i,k,x,y,t,ans;
  scanf("%d%d",&n,&m);
  s=int(sqrt(n)); //块的大小为根号n
  for(i=1;i<=s+1;i++)Max[i]=inf;
  for(i=1;i<=n;i++)
  {
    scanf("%d",&a[i]);
    k=(i-1)/s+1; //计算第i个数所在块的块号k
    if(a[i]>Max[k])Max[k]=a[i]; //Max[k]记录第k块的最大值
  }
  for(i=1;i<=m;i++)
  {
    scanf("%d%d%d",&t,&x,&y);
    if(t==1)Modify(x,y);
    else printf("%d\n",Query(x,y));
  }
}

修改 O(S) 询问 O(2\times s + n\times s)

问题2

那么对于区间修改呢？既然可以用懒标记，那么怎么用？

对于左右两个散块，无论是修改还是查询，我们都直接修改数组本身，然后修改各自散块所属的 max[calc(i)]。

例如修改3~11，每个数增加1，此时数组变成

1 1 5 6 \qquad 1 4 1 9 \qquad 1 9 8 1 \qquad 1 9 9 4 \qquad8

然后，我们对于每个块，都像 max 数组一样给定一个懒标记 lazy ，像线段树一样记录累计未加的值。

在查询时，我们可以同上个问题的询问的思路写代码，但是在判定时需要算上 lazy 数组，并且有时不能改变原数组（比如加乘并用的修改），不然小概率会出锅。

当然，如果修改时发现左右端点在同一个块内，按照这个思路，程序会把整个块（只有左右散块所以没有中间整块）修改，故大概率会出锅（怎么又是锅啊），所以需要特判。

代码：


void Modify(int x,int y,int z) //将a数列的区间[x,y]整体增加z
{
  int i=(x-1)/s+1; int j=(y-1)/s+1; //计算x和y所在块块号，s为块长
  if(i==j) //[x,y]在同一块中
  {
    for(int k=x; k<=y; k++)
    {
      a[k]+=z;
      if(a[k]>Max[i])Max[i]=a[k];
    }
  }
  else 
  {
    for(int k=x; k<=i*s; k++) //左侧散块
    { 
      a[k]+=z; 
      if(a[k]>Max[i])Max[i]=a[k];
    }
    for(int k=(j-1)*s+1; k<=y; k++) //右侧散块
    {
      a[k]+=z; 
      if(a[k]>Max[j])Max[j]=a[k];
    }
    for(int k=i+1;k<j;k++) //被覆盖的整块
    {
        Lazy[k]+=z; 
    }
  }
}

int Query(int x,int y) //询问a数列的区间[x,y]的最大值
{
  int i=(x-1)/s+1; int j=(y-1)/s+1; //计算x和y所在块块号,s为块长
  int ans=inf;
  if(i==j) //[x,y]在同一块中
  {
    for(int k=x; k<=y; k++)
    {
        if(a[k]+Lazy[i]>ans)ans=a[k]+Lazy[i];
    }
  }
  else 
  {
  for(int k=x; k<=i*s; k++) //左侧散块
    if(a[k]+Lazy[i]>ans)ans=a[k]+Lazy[i]; 
  for(int k=(j-1)*s+1; k<=y; k++) //右侧散块
    if(a[k]+Lazy[j]>ans)ans=a[k]+Lazy[j];
  for(int k=i+1;k<j;k++) //中间的整块
    if(Max[k]+Lazy[k]>ans)ans=Max[k]+Lazy[k];
  }
  return ans;
}

时间复杂度 O(n+m\times \sqrt n)

求和操作同理。故暂不多谈。

那么有些关于分块的问题。

其实这个问题很古德。

虽然线段树的复杂度是O(log n) 的，但是线段树的代码十分复杂，不好写，而且比分块更容易出锅。分块的出锅点基本上是固定的，而线段树虽然“板子化明显”，其出锅的点却因题而异，反正就是不好找，写的话要写很久，相对分块而言比较浪费编程时间。

“一个优秀的选手，在大部分OI赛制的、排名不计运行时间的考试里，只要不TLE，往往需要使用代码运行时间换取编程时间。”

而且由于线段树自带~~大肠术~~大常数，在极限数据下可能速度不及分块。 - 为啥块长为 $\sqrt n$分块效率最高？ 均衡不等式，$a + b \ge \sqrt {2ab}$（注意看，是大于等于，不要眼花） 为什么这个成立的证明，这里略（两边同时平方一下然后展开你就懂了） 所以当 联系问题1中的询问操作，时间复杂度$O(2\times s + n\times s)

提取 2\times s + n \times s，故 \dfrac{n}{s}+ s \ge 2 \sqrt {\dfrac{n}{s}\times s}

所以我们要让 \ge 左右两边相等，这样时间复杂度才最低。

故当 s = \sqrt n 时，\dfrac{n}{s}+ s \ge 2 \sqrt {\dfrac{n}{s}\times s} 可转换为 \dfrac{n}{\sqrt n}+ \sqrt n \ge 2 \sqrt {\dfrac{n}{\sqrt n}\times \sqrt n}，即 \sqrt n+ \sqrt n \ge 2 \sqrt {\sqrt n\times \sqrt n}，2\sqrt n \ge 2\sqrt n，可得 \ge 左右两边相等，证毕。