【学习笔记】值域分块、根号平衡和莫队

· · 算法·理论

0.前言

本人用带修莫队加 Splay 写树套树板子。结果发现 O(n^{\frac{3}{5}}\log n+n\log n) 过不去。

所以听了同学的去学了值域分块。

本文默认读者已掌握部分不同种类的莫队，以及序列分块的基础。

1.正文

简介

分块本质上是一种技巧。

拿维护序列信息为例子，我们对整个数列拆分成 \sqrt{n} 个块，修改和查询的时候可以直接利用整块的信息，而不需要一个一个暴力更新，保证了时间复杂度。

这是对数列进行分块，叫数列分块。

而对值域进行分块的技巧，就被称为值域分块。

值域分块维护的是一个集合，需要满足集合内的数据都存在某种可以到一个值域，且能够反映元素间大小关系的双射（或单射）。如最常用的离散化。

因此，值域分块常常配合离散化使用。

值域分块可以做到 O(1) 插入、删除一个数、O(\sqrt{n}) 查询全局排名、查询全局第 k 大，查询前驱、后继等操作——是在特定条件下，一众平衡树的平替，甚至优于平衡树。

主要思想

数列分块的每个位置维护的是数列上的数，而值域分块呢？没错，就是值出现的次数！

类比桶排序，我们用 cnt_x 代表当前集合 T 中 x 的出现次数。

对序列 cnt 进行分块，额外维护每个块内，即在某个值域范围内的所有数的出现次数总和，记为 cntblock_x。

那么显然有 \sum cnt=\sum cntblock=|T|。

除此之外，记块长为 s，belong_i 为值 i 所处的块编号，first_i 为编号为 i 的块的第一个值。

操作

\operatorname{insert}/\operatorname{erase}

很显然，插入 / 删除一个值为 x 的数，只需要将 cnt_x 和 cntblock_{belong_x} 自增 / 自减 1。

时间复杂度为 O(1)。

\operatorname{getrank}

对于值为 x 的数，求出有多少个数比 x 小，并把得到的结果加 1，就是 x 在其中的排名。

我们只需要累计所有小于 x 的数的出现次数即可。

对于整块，优先累加整块，直到 x 所在的前一块。然后再累加单个值。

\operatorname{getrank}(x)=\sum_{i=1}^{belong_x-1}cntblock_i+\sum_{i=first_{belong_x}}^{x-1}cnt_i

统计这个式子的时间复杂度为 O(\frac{n}{s}+s)。

\operatorname{getkth}

求出排名为 x 的数是多少。

在出现次数总和不大于 x 的情况下，累加整块的出现次数。然后继续累加单个值的次数，直到出现次数大于 x。

此时的值就是排名为 x 的数。

时间复杂度同样为 O(\frac{n}{s}+s)。

\operatorname{getpre}

求 x 的前驱，即小于 x，且最大的数。

我们可以先利用 \operatorname{getrank}(x) 求出 x 的排名 rank。

直接考虑本质，rank 代表有 rank-1 个数是小于 x 的，那么小于 x 的最大的数自然就是排名为 rank-1 的数。

那么有 \operatorname{getpre}(x)=\operatorname{getkth}(\operatorname{getrank}(x)-1)。

时间复杂度仍为 O(\frac{n}{s}+s)。

\operatorname{getnxt}

求 x 的后继，即大于 x，且最小的数。

类比 \operatorname{getpre}，要求大于 x 的数，需要先知道小于等于 x 的数有多少个。

记 rank=\operatorname{getrank}(x+1)，代表有 rank-1 个数小于 x+1，也就是小于等于 x。那么第一个大于 x 的数自然就是排名为 rank 的数，即 \operatorname{getkth}(rank)。

那么有 \operatorname{getnxt}(x)=\operatorname{getkth}(\operatorname{getrank}(x+1))。

时间复杂度仍为 O(\frac{n}{s}+s)。

关于复杂度

前面的操作，除去 \operatorname{insert} 和 \operatorname{erase}，块长的取值对这两个操作的复杂度没有影响，所有操作的复杂度都是 O(\frac{n}{s}+s)。

那么和普通分块类似，根据基本不等式，有 \frac{n}{s}+s \ge \sqrt{\frac{n}{s}\times s}。

因此，当且仅当 \frac{n}{s}=s=\sqrt n 时，时间复杂度取到最小值 O(\sqrt n)。

代码实现

初始化

设定块长为 \sqrt n，预处理出每个值属于哪个块，以及每个块的第一个值。

block_length=max((int)sqrt(n),1);
for(int i=1;i<=n;i++){
  belong[i]=(i-1)/block_length+1;
  if(!block_first[belong[i]]) block_first[belong[i]]=i;
}

\operatorname{insert}/\operatorname{erase}

只需要更新两个值即可。

void insert(int v){
    cnt[v]++;
    cnt_block[belong[v]]++;
}
void erase(int v){
    cnt[v]--;
    cnt_block[belong[v]]--;
}

\operatorname{getrank}

注意累加的时候都是小于，不能计算 cnt_x。排名初始为 1。

int getrank(int v){
    int rank=1;
    for(int i=1;i<belong[v];i++) rank+=cnt_block[i];
    for(int i=block_first[belong[v]];i<v;i++) rank+=cnt[i];
    return rank;
}

\operatorname{getkth}

一直累加 nowsum，直到 nowsum>=rank 成立。

此时的 nowpos 就是排名为 x 的数。

int getkth(int rank){
    int nowsum=0,nowblk=1;
    while(cnt_block[nowblk]+nowsum<rank) nowsum+=cnt_block[nowblk++];
    int nowpos=block_first[nowblk];
    while(cnt[nowpos]+nowsum<rank) nowsum+=cnt[nowpos++];
    return nowpos;
}

\operatorname{getpre}/\operatorname{getnxt}

直接代结论即可。

int getpre(int v){
    return getkth(getrank(v)-1);
}
int getnxt(int v){
    return getkth(getrank(v+1));
}

边界情况

一个数的前驱和后继有可能不存在。这种情况套用查询可能会导致一些奇怪的问题。

因此我们需要对特殊情况提前处理，办法很多，笔者更常用也更推荐的是将 \inf 和 -\inf 也加入离散化，并在初始化的时候提前将这两个数插入进去。

这样，当前驱后继不存在的时候，返回的就是 -\inf 或 \inf，再在后面的程序中特殊处理。

2.例题

P3369 【模板】普通平衡树

传送门

都说这是平衡树的平替了，不水个平衡树板子怎么行。

题目保证了一定存在前驱和后继，所以我们并不需要进行特殊处理，直接使用模板即可。

输入和输出的数有些需要离散化，有些不需要。注意分辨。

参考代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;

int m;
struct operations{
    int type,v;
}q[100010];

map<int,int> mp;
int mp_rev[100010],n;
vector<int> vec;

int block_length;
int belong[100010];
int block_first[510];

int cnt[100010];
int cnt_block[510];

void insert(int v){
    cnt[v]++;
    cnt_block[belong[v]]++;
}
void erase(int v){
    cnt[v]--;
    cnt_block[belong[v]]--;
}

int getrank(int v){
    int rank=1;
    for(int i=1;i<belong[v];i++) rank+=cnt_block[i];
    for(int i=block_first[belong[v]];i<v;i++) rank+=cnt[i];
    return rank;
}
int getkth(int rank){
    int nowsum=0,nowblk=1;
    while(cnt_block[nowblk]+nowsum<rank) nowsum+=cnt_block[nowblk++];
    int nowpos=block_first[nowblk];
    while(cnt[nowpos]+nowsum<rank) nowsum+=cnt[nowpos++];
    return nowpos;
}

int getpre(int v){
    return getkth(getrank(v)-1);
}
int getnxt(int v){
    return getkth(getrank(v+1));
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin>>m;
    for(int i=1;i<=m;i++) cin>>q[i].type>>q[i].v;

    for(int i=1;i<=m;i++) if(q[i].type!=4) vec.push_back(q[i].v);

    sort(vec.begin(),vec.end());
    mp[vec[0]]=++n;
    mp_rev[n]=vec[0];
    for(int i=1;i<(int)vec.size();i++) if(vec[i]!=vec[i-1]) mp[vec[i]]=++n,mp_rev[n]=vec[i];

    for(int i=1;i<=m;i++) if(q[i].type!=4) q[i].v=mp[q[i].v];

    block_length=max((int)sqrt(n),1);
    for(int i=1;i<=n;i++){
        belong[i]=(i-1)/block_length+1;
        if(!block_first[belong[i]]) block_first[belong[i]]=i;
    }

    for(int p=1;p<=m;p++){
        int op=q[p].type;
        if(op==1) insert(q[p].v);
        else if(op==2) erase(q[p].v);
        else if(op==3) cout<<getrank(q[p].v)<<"\n";
        else if(op==4) cout<<mp_rev[getkth(q[p].v)]<<"\n";
        else if(op==5) cout<<mp_rev[getpre(q[p].v)]<<"\n";
        else if(op==6) cout<<mp_rev[getnxt(q[p].v)]<<"\n";
    }

    return 0;
}

P3380 【模板】树套树

传送门

什么？树套树板子也能用值域分块？这题不是区间查询吗？

因为有一个东西叫莫队。

如果直接用带修莫队套 Splay，每次修改和查询的复杂度就都是 O(\log n)，总复杂度是修改和查询的复杂度之和，即 O(n^{\frac{3}{5}}\log n+n\log n)，很显然过不了。

但如果我们使用值域分块，修改 O(1)，查询 O(\sqrt{n})，总复杂度就会变为 O(n^{\frac{3}{5}}+n\sqrt n)。

我们发现，值域分块用更高的查询复杂度，换来了更低的修改复杂度。在一些修改次数远多于查询次数的情况下会有奇效。

正因如此，莫队算法也常常会配合值域分块，将高次数的修改和低次数的查询的时间复杂度达成一种平衡。也就是根号平衡。

需要注意，本题不保证一定存在前驱后继，需要进行特殊处理，如上文提到的把 \inf 和 -\inf 加入离散化等。

参考代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;

namespace name1{
    int n;
    int block_length;
    int block_first[100010];
    int block_last[100010];
    int belong[100010];

    int cnt[100010];
    int cnt_block[510];

    void insert(int v){
        cnt[v]++;
        cnt_block[belong[v]]++;
    }
    void erase(int v){
        cnt[v]--;
        cnt_block[belong[v]]--;
    }

    int getrank(int v){
        int rank=1;
        for(int i=1;i<belong[v];i++) rank+=cnt_block[i];
        for(int i=block_first[belong[v]];i<v;i++) rank+=cnt[i];
        return rank;
    }
    int getval(int rank){
        int nowsum=0,nowblk=1;
        while(cnt_block[nowblk]+nowsum<rank) nowsum+=cnt_block[nowblk++];
        int nowpos=block_first[nowblk];
        while(cnt[nowpos]+nowsum<rank) nowsum+=cnt[nowpos++];
        return nowpos;
    }

    int getpre(int v){
        int rank=getrank(v);
        return getval(rank-1);
    }
    int getnxt(int v){
        int rank=getrank(v+1);
        return getval(rank);
    }

    void init(int w){
        n=w;
        block_length=max((int)sqrt(n),1);
        for(int i=1;i<=n;i++){
            belong[i]=(i-1)/block_length+1;
            if(!block_first[belong[i]]) block_first[belong[i]]=i;
            block_last[belong[i]]=i;
        }
    }
}

namespace name2{
    int n,m;
    int a[50010];
    int block_length;
    int belong[50010];

    map<int,int> mp;
    int mp_rev[100010],unq;
    vector<int> vec;

    struct queries{
        int l,r,time,id,type,v;
        bool operator<(const queries&q)const{
            if(belong[l]!=belong[q.l]) return belong[l]<belong[q.l];
            if(belong[r]!=belong[q.r]){
                if(belong[l]&1) return belong[r]<belong[q.r];
                else return belong[r]>belong[q.r];
            }
            if(belong[r]&1) return time<q.time;
            else return time>q.time;
        }
    }q[50010];int qcnt;

    struct modify{
        int x,v;
    }d[50010];int dcnt;

    static inline void add(int x){
        name1::insert(a[x]);
    }
    static inline void remove(int x){
        name1::erase(a[x]);
    }
    static inline int calc(int type,int v){
        if(type==1) return name1::getrank(v)-1;
        else if(type==2) return mp_rev[name1::getval(v+1)];
        else if(type==4) return mp_rev[name1::getpre(v)];
        else if(type==5) return mp_rev[name1::getnxt(v)];
        else return 0;
    }

    int Ans[50010];

    void solve(){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=m;i++){
            int op;cin>>op;
            int x,y;cin>>x>>y;
            if(op==3) d[++dcnt]=(modify){x,y};
            else{
                int v;cin>>v;
                q[++qcnt]=(queries){x,y,dcnt,qcnt,op,v};
            }
        }
        while(1ll*block_length*block_length*block_length<=1ll*n*n*3) block_length++; // 之前学带修莫队的时候从大佬那里抄来的块长 还挺快的
        for(int i=1;i<=n;i++) belong[i]=(i-1)/block_length+1;
        sort(q+1,q+1+qcnt);

        for(int i=1;i<=n;i++) vec.push_back(a[i]);
        for(int i=1;i<=qcnt;i++) if(q[i].type!=2) vec.push_back(q[i].v);
        for(int i=1;i<=dcnt;i++) vec.push_back(d[i].v);
        vec.push_back(-INT_MAX);
        vec.push_back(INT_MAX);

        sort(vec.begin(),vec.end());
        mp[vec[0]]=++unq;
        mp_rev[unq]=vec[0];
        for(int i=1;i<(int)vec.size();i++) if(vec[i]!=vec[i-1]) mp[vec[i]]=++unq,mp_rev[unq]=vec[i];

        for(int i=1;i<=n;i++) a[i]=mp[a[i]];
        for(int i=1;i<=qcnt;i++) if(q[i].type!=2) q[i].v=mp[q[i].v];
        for(int i=1;i<=dcnt;i++) d[i].v=mp[d[i].v];

        name1::init(unq);

        name1::insert(1);
        name1::insert(unq);

        int nl=1,nr=0,ntime=0;
        for(int p=1;p<=qcnt;p++){
            int pl=q[p].l;
            int pr=q[p].r;
            int ptime=q[p].time;

            while(nl>pl) add(--nl);
            while(nr<pr) add(++nr);
            while(nl<pl) remove(nl++);
            while(nr>pr) remove(nr--);

            while(ntime<ptime){
                ntime++;

                int pos=d[ntime].x;
                bool chk=(nl<=pos&&pos<=nr);

                if(chk) remove(pos);
                swap(d[ntime].v,a[pos]);
                if(chk) add(pos);
            }
            while(ntime>ptime){
                int pos=d[ntime].x;
                bool chk=(nl<=pos&&pos<=nr);

                if(chk) remove(pos);
                swap(d[ntime].v,a[pos]);
                if(chk) add(pos);

                ntime--;
            }
            Ans[q[p].id]=calc(q[p].type,q[p].v);
        }
        for(int i=1;i<=qcnt;i++) cout<<Ans[i]<<"\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    name2::solve();

    return 0;
}

P2617 Dynamic Rankings

传送门

和上面的模板题一样，完全可以使用莫队+值域分块，以 O(n^{\frac{3}{5}}+n\sqrt n) 的时间复杂度通过。

本题和上面的模板题都需要注意的一点是：都用到了两个分块，要注意变量名不要弄混淆。最好可以开两个 namespace 来区别。

实际上大部分树套树的题目只要没强制在线都可以用莫队+值域分块卡过去。

因为和上一题非常相似，这里就不附代码了。

更多例题

P4137 Rmq Problem / mex

和上面类似，只不过块内维护的是这个块里不同种类的数的出现次数。同样可以做到 O(\sqrt n) 查询，达成平衡。

其实这题还能用 bitset 水过去。

P4396 [AHOI2013] 作业

需要同时维护上面两道题所需的信息。注意细节。

P5906 【模板】回滚莫队&不删除莫队

使用双端队列来记录每个数出现的位置，把每个数对应的队首和队尾的差放进值域分块维护的集合，查询时从右向左找到的第一个不为 0 的数就是答案。

可能略微卡常。

3.后记

其实还有一种值域分块，维护的是对应信息的前缀和。其复杂度与本文的值域分块恰好相反，可以做到 O(\sqrt n) 修改和 O(1) 查询。但因应用范围并不广（大概），这里不展开讲解，感兴趣的读者可以自行查阅资料。

分块思想是很重要的一种思想，在很多情景下都有它的影子。

万物皆可分块。我们可以对序列分块，对值域分块，甚至对查询分块，可谓变化多端。

最后，祝各位 CSP 2025 J/S/X rp++！

为什么我学值域分块结果找的例题都是莫队的。