分块入门 by hzwer

文章内容来自于「分块」数列分块入门1 – 9 by hzwer - 分块 - hzwer.com，如有侵权，请联系作者删除

---

入门1

给出一个长为n的数列，以及n个操作，操作涉及区间加法，单点查值。

这是一道能用许多数据结构优化的经典题，可以用于不同数据结构训练。

数列分块就是把数列中每m个元素打包起来，达到优化算法的目的。

以此题为例，如果我们把每m个元素分为一块，共有\(O(\frac{n}{m})\)块，每次区间加的操作会涉及\(O(\frac{n}{m})\)个整块，以及区间两侧两个不完整的块中至多2m个元素。

我们给每个块设置一个加法标记（就是记录这个块中元素一起加了多少），每次操作对每个整块直接O(1)标记，而不完整的块由于元素比较少，暴力修改元素的值。

每次询问时返回元素的值加上其所在块的加法标记。

这样每次操作的复杂度是\(O(\frac{n}{m})+O(m)\)，根据均值不等式，当\(m\)取\(\sqrt{n}\)时总复杂度最低，为了方便，我们都默认下文的分块大小为\(\sqrt{n}\)

#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 998244353
#define pi acos(-1)
#define inf 0x7fffffff
#define ll long long
using namespace std;
ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,blo;
int v[50005],bl[50005],atag[50005];
void add(int a,int b,int c)
{
    //修改每个元素的值
    //从a开始
    //如果a与b属于同一块，那么直接修改即可
    //不属于同一块，修改从a开始，到a所在块的右边界的区间元素，暴力修改
    for(int i=a;i<=min(bl[a]*blo,b);i++)
        v[i]+=c;

    //判断a与b是否处于同一块中
    //不属于同一块
    //修改从b所在块的左边界开始，到b的区间元素，暴力修改
    if(bl[a]!=bl[b])
        for(int i=(bl[b]-1)*blo+1;i<=b;i++)
            v[i]+=c;

    //a到b之间的元素块整块加值
    //如果a与b位于同一个块内，则不会进入循环
    for(int i=bl[a]+1;i<=bl[b]-1;i++)
        atag[i]+=c;
}
int main()
{
    //n表示有多少个元素，blo表示的分块的大小
    n=read();blo=sqrt(n);

    //读入n个元素
    for(int i=1;i<=n;i++)v[i]=read();

    //将每个元素分配到对应的块中
    for(int i=1;i<=n;i++)bl[i]=(i-1)/blo+1;

    //n表示n次操作
    for(int i=1;i<=n;i++)
    {
        //f表示操作的类型，a表示区间的左端点，b表示区间的右端点，c表示加上的值
        int f=read(),a=read(),b=read(),c=read();

        //区间修改
        if(f==0)add(a,b,c);

        //单点查询，这里的b表示查询的单点值
        if(f==1){
            printf("%d\n",v[b]+atag[bl[b]]);
            cout<<v[b]<<" "<<atag[bl[b]];
        }
    }
    return 0;
}

---

入门2

给出一个长为n的数列，以及n个操作，操作涉及区间加法，询问区间内小于某个值x的元素个数。

有了上一题的经验，我们可以发现，数列简单分块问题实际上有三项东西要我们思考：

对于每次区间操作：

1.不完整的块 的\(O(\sqrt{n})\)个元素怎么处理？

2.\(O(\sqrt{n})\)个 整块 怎么处理？

3.要预处理什么信息（复杂度不能超过后面的操作）？

我们先来思考只有询问操作的情况，不完整的块枚举统计即可；而要在每个整块内寻找小于一个值的元素数，于是我们不得不要求块内元素是有序的，这样就能使用二分法对块内查询，需要预处理时每块做一遍排序，复杂度\(O(nlog\ n)\)，每次查询在\(\sqrt{n}\)个块内二分，以及暴力\(2\sqrt{n}\)个元素，总复杂度\(O(nlog\ n+n\sqrt{n}log\sqrt{n})\)。

可以通过均值不等式计算出更优的分块大小，就不展开讨论了

那么区间加怎么办呢？

套用第一题的方法，维护一个加法标记，略有区别的地方在于，不完整的块修改后可能会使得该块内数字乱序，所以头尾两个不完整块需要重新排序，复杂度分析略。

在加法标记下的询问操作，块外还是暴力，查询小于（x – 加法标记）的元素个数，块内用（x – 加法标记）作为二分的值即可。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAXN=1e5+10;
int aa[MAXN],be[MAXN],tag[MAXN];
vector<int> v[MAXN];
int n,block;
//重构
void reset(int x){
    //先清空数组
    v[x].clear();

    //对该块内的元素进行重构
    //注意最后一块可能不是完整的一块 所以需要取min(n,x*block)
    for(int i=(x-1)*block+1;i<=min(n,x*block);i++){
        v[x].push_back(aa[i]);
    }

    //对块中的元素进行重构 排序 方便后续的二分查找
    sort(v[x].begin(),v[x].end());
}
void add(int a,int b,int c){
    //修改从a到b的区间内的元素
    //可能从a到b会跨块 所以取min(be[a]*block,b)
    for(int i=a;i<=min(b,be[a]*block);i++){
        aa[i]+=c;
    }

    //重构块
    reset(be[a]);

    //如果a与b不属于同一块 那么需要重构b所在的块
    //注意是从b所在块的左边开始重构
    if(be[a]!=be[b]){
        for(int i=(be[b]-1)*block+1;i<=b;i++){
            aa[i]+=c;
        }
        //别忘了重构块
        reset(be[b]);
    }

    //对从a到b之间的块进行重构
    //如果a与b不属于同一块 则需要将位于它们之间的块打上标记
    //注意不需要重构块 因为块中的元素值都加上了c
    for(int i=be[a]+1;i<=be[b]-1;i++){
        tag[i]+=c;
    }
}
int query(int a,int b,int c){
    int ans=0;
    //查询从a到b的区间内大于c的元素
    //可能从a到b会跨块 所以取min(be[a]*block,b)
    for(int i=a;i<=min(be[a]*block,b);i++){
        //be[a]改成be[i]可行吗
        //可行
        if(aa[i]+tag[be[i]]<c)ans++;
    }

    //判断a与b是否位于同一块
    //如果a与b不属于同一块 那么需要重构b所在的块
    //注意这里只是询问，不需要重构
    if(be[a]!=be[b]){
        for(int i=block*(be[b]-1)+1;i<=b;i++){
            //be[b]改成be[i]也可行
            if(aa[i]+tag[be[i]]<c)ans++;
        }
    }

    //对从a到b之间的块进行重构
    //如果a与b不属于同一块 则需要将位于它们之间的块中的元素进行二分查找
    //注意不需要重构块
    for(int i=be[a]+1;i<=be[b]-1;i++){
        int x=c-tag[i];
        ans+=lower_bound(v[i].begin(),v[i].end(),x)-v[i].begin();
    }
    //返回答案
    return ans;
}
int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr);
    n;cin>>n;
    // 输入n个数
    for(int i=1;i<=n;i++)cin>>aa[i];

    //分块大小确定
    block=sqrt(n);

    //对每个数确定其对应的块
    for(int i=1;i<=n;i++){
        be[i]=(i-1)/block+1;
        v[be[i]].push_back(aa[i]);
    }

    //对每个块内的元素进行排序
    for(int i=1;i<=be[n];i++){
        //wsm要重构
        //为了后面询问的需要，我们使用的是二分查找，但是不一定所有的块都会被重构
        // 所有我们需要提前对每个块进行重构 也就是对块中的元素进行排序
        sort(v[i].begin(),v[i].end());
    }

    //n此询问
    for(int i=1;i<=n;i++){
        int f,a,b,c;cin>>f>>a>>b>>c;
        if(f==0)add(a,b,c);
        if(f==1)cout<<query(a,b,c*c)<<"\n";
    }
    return 0;
}

---

入门3

给出一个长为n的数列，以及n个操作，操作涉及区间加法，询问区间内小于某个值x的前驱（比其小的最大元素）。

n<=100000其实是为了区分暴力和一些常数较大的写法。

接着第二题的解法，其实只要把块内查询的二分稍作修改即可。

不过这题其实想表达：可以在块内维护其它结构使其更具有拓展性，比如放一个 set ，这样如果还有插入、删除元素的操作，会更加的方便。

分块的调试检测技巧：

可以生成一些大数据，然后用两份分块大小不同的代码来对拍，还可以根据运行时间尝试调整分块大小，减小常数。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e5 + 10;
int a[MAXN], be[MAXN], tag[MAXN];
int n, block;
set<int> s[1050];
//修改加值
void add(int x, int y, int z) {
    //一样的情况
    for (int i = x; i <= min(y, be[x]*block); i++) {
        //需要先删除 再修改元素 再存入块中
        s[be[i]].erase(a[i]);
        a[i] += z;
        s[be[i]].insert(a[i]);
    }

    //一样的情况
    if (be[x] != be[y]) {
        for (int i = block * (be[y] - 1) + 1; i <= y; i++) {
            s[be[i]].erase(a[i]);
            a[i] += z;
            s[be[i]].insert(a[i]);
        }
    }

    //跨块 整块加上标记
    for (int i = be[x] + 1; i <= be[y] - 1; i++) {
        tag[i] += z;
    }
}
//询问
int query(int x, int y, int z) {
    int ans = -1;

    //一样的情况
    //注意这里的val是值+标记
    //a[i]如果被修改了 则一定不会被加上tag
    //若加上tag 则不会被加上值
    for (int i = x; i <= min(y, be[x]*block); i++) {
        int val = a[i] + tag[be[i]];

        if (val < z)
            ans = max(ans, val);
    }

    //一样的情况
    if (be[x] != be[y]) {
        for (int i = block * (be[y] - 1) + 1; i <= y; i++) {
            int val = a[i] + tag[be[i]];

            if (val < z)
                ans = max(ans, val);
        }
    }

    //跨块
    //注意num得改为z-tag[i]
    for (int i = be[x] + 1; i <= be[y] - 1; i++) {
        int num = z - tag[i];
        //找到第一个值为num的元素 因为set是自动排序的
        set<int>::iterator it = s[i].lower_bound(num);

        //找不到则跳过
        if (it == s[i].begin())
            continue;

        //记得要找比它小的 所以要减1
        --it;
        ans = max(ans, *it + tag[i]);
    }

    return ans;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    n;
    cin >> n;
    //获取分块大小
    block = sqrt(n);

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    //划分块 将元素加到对应的块中
    // 这里的块用堆实现
    for (int i = 1; i <= n; i++) {
        be[i] = (i - 1) / block + 1;
        s[be[i]].insert(a[i]);
    }

    //n次操作
    for (int i = 1; i <= n; i++) {
        int f, x, y, z;
        cin >> f >> x >> y >> z;

        if (f == 0) {
            add(x, y, z);
        }

        if (f == 1) {
            cout << query(x, y, z) << "\n";
        }
    }

    return 0;
}