分块大法

· · 题解

分块大法

1.1 概念

分块是一种暴力数据结构。分块的基本思想是把一个整体数列分成多块，使得查询时可以调用已经处理好的每块的信息。它的查询复杂度一般为 O(\sqrt{n}) 。修改复杂度不一定，在这一题中修改复杂度为 O(1) 。

1.2 为何选择分块？何时使用分块？

当然是因为它比较好想好写了！当题目中出现各种傻逼毒瘤一般比较难以实现的更新操作时，线段树、树状数组的更新操作均需进行较大改动才可使用时，就是分块派上用场的时候！

这道题好像更新很好实现啊，你是不是在打自己的脸啊?

2.1 一切的开始

要分块，首先要确定块的大小。一般来说，块的大小都为\sqrt{n}。这样大小的块可以保证整个序列被分成\sqrt{n}块。这样查询的时间复杂度可以达到平均。

分块算法中需要记录的信息有：

int sum[maxn];//一个块的和
int l[maxn];//一个块的左端点（起始点）
int r[maxn];//一个块的右端点（终结点）
int a[maxn];//原数组
int belong[maxn];//第i个元素属于第belong[i]个块
int block,num;//block表示块的大小，num表示块的数量。

分块的build函数代码为：

void build()
{
    block=sqrt(n);//块的大小是根号n
    num=n/block;if (n%block) num++;//有可能n不是完全平方数，这时块数需要加一
    for(int i=1;i<=num;i++)
    {
        l[i]=(i-1)*block+1;r[i]=i*block;
    }//对于左端点和右端点处理
    for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1;
    r[num]=n;//最后一个块的右端点一定为n
    for(int i=1;i<=num;i++)
        for(int j=l[i];j<=r[i];j++)
            sum[i]+=a[j];//预处理出所有块的和
}

2.2 更新操作

很简单，无须赘述，基本上代码一看就懂。

inline void updata(int x,int y)//第x个元素加上y
{
    a[x]+=y;
    sum[belong[x]]+=y;//第x个元素所在的块的总和也要加上y
}

2.3 查询操作

这基本上是分块最难的点。但实际也很简单。

查询共有两种情况：

A. 区间被一个块完整包含

直接暴力求解。因为块的大小最大为\sqrt{n}，所以复杂度为O(\sqrt{n})。

if (belong[x]==belong[y])
{
    for(int i=x;i<=y;i++) ans+=a[i];
    return ans;
}

B. 区间横跨多个块

这是我们讲述的重点。请看下面这张图：

如图，我们需要查询x至y的区间和。

首先，我们先暴力求出x到它所属的块的右端点的区间和。如下图所示：

上述操作即为暴力求解图中黑箭头到红箭头之间的区间和。代码如下 ：

for(int i=x;i<=r[belong[x]];i++) ans+=a[i];

接下来，我们会发现：

从x所属的下一个块开始，到y之前的一个块的区间内，所有块都是完整的

所以我们只需要使用之前处理出来的块的信息就可以啦。代码如下：

for(int i=belong[x]+1;i<=belong[y]-1;i++) ans+=sum[i];

然后重复类似开始的操作，暴力求解途中蓝箭头至y那一段即可。

for(int i=l[belong[y]];i<=y;i++) ans+=a[i];

所以分块中查询的函数部分如下：

inline int query(int x,int y)
{
    int ans=0;
    if (belong[x]==belong[y])
    {
        for(int i=x;i<=y;i++) ans+=a[i];
        return ans;
    }
    for(int i=x;i<=r[belong[x]];i++) ans+=a[i];
    for(int i=belong[x]+1;i<=belong[y]-1;i++) ans+=sum[i];
    for(int i=l[belong[y]];i<=y;i++) ans+=a[i];
    return ans;
}

3.1 完整code

分块的代码还是很好写的。需要注意的是这题数据有点大，所以要用读优+内联卡常过。

#include<bits/stdc++.h>
#define maxn 500007
using namespace std;
int sum[maxn],r[maxn],l[maxn],a[maxn],belong[maxn],block,num,n,m;
inline void write(int x)
{
    if(x<0) x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
inline int read()
{
    int x=0,f=1;char ch;
    for(;!isdigit(ch);ch=getchar()) f=ch=='-'?-1:1;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
    return x*f;
}
inline int query(int x,int y)
{
    int ans=0;
    if (belong[x]==belong[y])
    {
        for(int i=x;i<=y;i++) ans+=a[i];
        return ans;
    }
    for(int i=x;i<=r[belong[x]];i++) ans+=a[i];
    for(int i=belong[x]+1;i<=belong[y]-1;i++) ans+=sum[i];
    for(int i=l[belong[y]];i<=y;i++) ans+=a[i];
    return ans;
}
inline void updata(int x,int y)
{
    a[x]+=y;
    sum[belong[x]]+=y;
    //for(int i=1;i<=num;i++) printf("l: %d,r: %d,sum: %d\n",l[i],r[i],sum[i]);
    //putchar('\n');
}
inline void build()
{
    block=sqrt(n);
    num=n/block;if (n%block) num++;
    for(int i=1;i<=num;i++)
    {
        l[i]=(i-1)*block+1;r[i]=i*block;
    }
    for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1;
    r[num]=n;
    for(int i=1;i<=num;i++)
        for(int j=l[i];j<=r[i];j++)
            sum[i]+=a[j];
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    build();
    //for(int i=1;i<=num;i++) printf("l: %d,r: %d,sum: %d\n",l[i],r[i],sum[i]);
    for(int i=1;i<=m;i++)
    {
        int mode=read(),x=read(),y=read();
        if (mode==1) updata(x,y);
        else
        {
            write(query(x,y));
            putchar('\n');
        }
    }
    return 0;
}

就这么多啦。比赛临近，多写点题解攒RP。 Feather-Sea 祝您在洛谷好运连连！