分块学习笔记

_299817_ · 2022-11-18 18:38:17 · 个人记录

~~前言：分块其实很简单~~

~~马蜂比较奇怪，轻喷。~~

文章同步于CSDN

错误可以分享在评论里，欢迎指出。

有问题也可以在下面问，但是注意提问的智慧

码字不易，点个赞吧。

Part 1：主要思想（看完之后一定要继续看Part 2，不然很难理解）

分块，顾名思义，就是把一个数组分成很多块，然后保存块内的最值（或者其他的东西，这里以每块的和作为例子），最后查询时调用块内值即可。可以在 \Theta(n^{\frac{3}{2}}) ，也就是 \Theta(n\sqrt{n}) 的复杂度里解决区间问题（常用于解决 n 的级别在 10^5 的问题）。

我们一般把数组分成 \sqrt{n} 块，每块长 \sqrt{n}

比如说这样：

（在 n 不能整除 \sqrt{n} 的情况下，会分成 \sqrt{n} + 1 块，最后一块的长度为分完 \sqrt{n} 快后剩下的所有数的个数）

接着我们需要记录下每一个块的左端点 l_i ，右端点 r_i ，每个数属于哪个块 pos_i ，每个块的数的和 sum_i ，以及一个 lazy_i （1.这里的 lazy 的基本意思和线段树一样，但是它不会下传（特殊情况除外），等会会讲 2.注意这里的 pos 的 i 和其他的数组的 i 的意义不一样）

然后呢，我们就可以在这上面执行一些操作：

注:代码里的 a 数组是原数组

Part 2 代码实现

2.1 预处理（分块）

我们先记录好块长 num 和块数 cnt ，像这样：

num = sqrt(n); // 块长
cnt = n / num; // 块数
if(n % num != 0) // 如果n不能整除sqrt(n)
{
    cnt++; // 块的数量+1
}

接着我们记录好每一块的左端点和右端点，即 l_i 和 r_i。

for(int i = 1; i <= cnt; i++)
{
    l[i] = (i - 1) * num + 1; // 第i块的左端点
    r[i] = l[i] + num - 1; // 第i块的右端点，也就是左端点+块长-1
}
r[cnt] = n; // 如果最后一块没有num个，那么最后一块的右端点肯定就是n啦（即使最后一块有num个也是）

然后求出每个点属于那块和每个块的和，即 pos_i 和 sum_i。（注意 pos 的 i 和 sum 的 i 的意义不同）

for(int i = 1; i <= cnt; i++) // 循环每一个块
{
    for(int j = l[i]; j <= r[i]; j++) // 循环每一个块的左端点到右端点
    {
        pos[j] = i; // 每一个点属于哪个快
        sum[i] += a[j]; // 每个块的和
    }
}

然后预处理就结束啦！

// 预处理完整代码
void init() 
{
    num = sqrt(n);
    cnt = n / num;
    if(n % num != 0)
    {
        cnt++;
    }
    for(int i = 1; i <= cnt; i++)
    {
        l[i] = (i - 1) * num + 1;
        r[i] = l[i] + num - 1;
    }
    r[cnt] = n;
    for(int i = 1; i <= cnt; i++)
    {
        for(int j = l[i]; j <= r[i]; j++)
        {
            pos[j] = i;
            sum[i] += a[j];
        }
    }
}

时间复杂度为 \Theta(n) 。

2.2 区间修改

注：这里就不讲单点修改了，单点修改就只要让区间的左右端点相同即可。（注意：这里绝对不能直接修改数组的值，因为如果直接修改 a_i 是修改不了 sum 的，一定要调用修改函数）

这里的修改左端点叫 left ,右端点叫 right，为了不于上面的 l 和 r 数组重名。然后这里的修改指把这个区间的所有数都加上 v （ v 在代码里会提到）

首先我们要把 left 和 right 属于哪个块求出来，即 p 和 q。

int p = pos[left];
int q = pos[right];

接下来要分两种情况:

1. left 和 right 在同一块内

那么就直接暴力修改这个区间内的所有数，别忘记更新 sum 。

if(p == q) // left和right在同一块内
{
    for(int i = left; i <= right; i++) // 更新a[i]
    {
        a[i] += v;
    }
    sum[p] += v * (right - left + 1); // 更新sum[i]
    return;
}

2. left 和 right 不在同一块内

比如说这样：

那么我们就把它分成 3 个部分来求：（部分的编号为紫色）

第一部分（即 left 到 left 所属块的右端点）我们就直接暴力加：

for(int i = left; i <= r[p]; i++) // 第一部分
{
    a[i] += v; 
}
sum[p] += v * (r[p] - left + 1); // 别忘记更新sum数组

第二部分（即除 left 和 right 所属块外所有中间的块，也就是被修改区间全部覆盖的块）我们就只加 lazy 数组。

for(int i = p + 1; i <= q - 1; i++) // 第二部分
{
    lazy[i] += v;
}

第三部分（即 right 所属块的左端点到 right ）我们也是暴力加:

for(int i = l[q]; i <= right; i++) // 第三部分
{
    a[i] += v;
}
sum[q] += v * (right - l[q] + 1); // 别忘记更新sum数组

区间修改就结束啦！

// 区间修改完整代码
void update(int left, int right, int v)
{
    int p = pos[left];
    int q = pos[right];
    if(p == q)
    {
        for(int i = left; i <= right; i++)
        {
            a[i] += v;
        }
        sum[p] += v * (right - left + 1);
        return;
    }
    for(int i = left; i <= r[p]; i++)
    {
        a[i] += v; 
    }
    sum[p] += v * (r[p] - left + 1);
    for(int i = p + 1; i <= q - 1; i++)
    {
        lazy[i] += v;
    }
    for(int i = l[q]; i <= right; i++)
    {
        a[i] += v;
    }
    sum[q] += v * (right - l[q] + 1);
}

时间复杂度为 \Theta(n\sqrt{n}) 。

2.3 区间查询

单点修改一样就不讲了。

区间查询和区间修改的思想差不多，也是先特判 left 到 right 在同一块内的情况，接下来依然分 3 个部分，依次查询，就是要注意加上 lazy 数组。

具体内容就不讲了，注释在代码里面

int query(int left, int right)
{
    int p = pos[left]; // left属于哪个块
    int q = pos[right]; // right属于哪个块
    int ans = 0; // 区间查询答案
    if(p == q) // 特判left和right属于同一块的情况
    {
        for(int i = left; i <= right; i++)
        {
            ans += a[i];
            ans += lazy[p]; // 注意ans要加上lazy数组
        }
        return ans; // 记得要返回ans
    }
    for(int i = left; i <= r[p]; i++) // 情况1，暴力
    {
        ans += a[i];
        ans += lazy[p]; // 不但要加上a数组，也要加上lazy数组
    }
    for(int i = p + 1; i <= q - 1; i++) // 情况2，加上sum和lazy数组
    {
        ans += sum[i];
        ans += lazy[i] * (r[i] - l[i] + 1); // 加区间长度个lazy数组
    }
    for(int i = l[q]; i <= right; i++) // 情况3，暴力
    {
        ans += a[i];
        ans += lazy[q]; // 加lazy
    }
    return ans; // 返回答案
}

时间复杂度为 \Theta(n\sqrt{n})

现在，分块的代码就完成啦！记得加 main 函数

完整代码（也是模板题P3372）：here

Part 3 一些关于分块的题目

1.P2357 守墓人

裸的板子题吧，代码就不放了。

~~现在分块似乎会被卡掉？~~

2.Loj上的9道分块模板

这里就只讲第二道，因为它极其经典，其他的题目也八九不离十。

他要求数列内小于某个值的元素个数，我们只需要把每个块的所有数用 vector 存下来，接着每次修改时就只要把 left 所在块和 right 所在块暴力处理，重新排序，然后由于中间的所有块都只要加 v ，所以他们的相对位置是不改变的，所以只要把 v 放进 lazy 里，不用重新排序，时间复杂度为 \Theta(n \log n)。

查询的时候因为每个块内的所有数都是单调的，所以只要暴力查询 left 和 right 所在块。接着二分中间的所有块，时间复杂度为 \Theta(n \log n)。

预处理的时间复杂度为 \Theta(n\log\sqrt{n})

数据是能过的。

注释代码