多层分块树

FFT_NTT_ · 2026-10-13 15:48:28 · 算法·理论

本文介绍一种我自己发明的多层分块实现的树形数据结构。支持 O(\log n) 单点修改，O(\log n) 区间查询，但是常数极大，码量不小，总结就是废物。

前言

回顾一下分块处理单点修改，区间查询的过程：

将数组分为 \sqrt n 个块，维护每个下标对应的值 a_i，整块求和 sum_i。

单点修改块 b 内的下标 i 时，直接修改 a_i 和 sum_b。

区间求和时，把区间拆成整块和散块，散块暴力累加，整块利用预处理的 sum 值查询。

本人在学习分块的时候，认为区间求和的过程不够优美，于是想出了一种双层分块：

注意到区间求和，本质上是拆成整块 sum_i 的区间和，散块 a_i 的前缀和，后缀和，再暴力维护，所以我再用分块维护 sum 的区间和，散块 a_i 的区间和，不就能做到 O(n^{1/4}) 单点修改，区间查询了吗？

当我沾沾自喜的时候，某个同学说：“你这个东西常数太大了。”然而执迷不悟坚持不懈的我决定不顾常数继续探究，最终得到了一种新的数据结构。名字还没想好，姑且叫它多层分块树吧。

结构

类似上面说的多层分块，递归定义多层分块树 tree(n)，维护长度为 n 的区间：

它的根节点 d 维护了一个值 v_d，表示长度为 n 的区间求和。该节点有 \sqrt n 个儿子，编号为 son_{d,i}，每个儿子对应一个 tree(\sqrt n)。对所有儿子的 v，再维护一个辅助 tree(\sqrt n) 做区间求和，其根为 root_d。

特别地，对于 n \le 3，暴力维护，原因后面再说。

操作

建树

下面的代码建立了一个多层分块树，下标范围为 [0,len]，即维护长度为 len+1 的区间。

当 len > 2，将区间按 B=\sqrt{len+1} 分块，动态开点存储儿子，对每个块递归建立多层分块树。再建立一个辅助多层分块树，根为 root_d。

当 len \le 2，因为 \sqrt{len+1} 下取整为 1，若再递归建立多层分块树，其维护区间长度仍为 len+1，会造成无穷递归。

void build(int d,int len){
    if(len>2){
        int B=sqrt(len+1);
        root[d]=cnt,cnt++,build(root[d],len/B),son[d].resize(len/B+1);
        for(int i=0;i<=len/B;i++){
            son[d][i]=cnt,cnt++,build(son[d][i],(i^(len/B))?B-1:len%B);
        }
    }
    return;
}

单点修改

下面的代码实现了多层分块树的单点修改。

当 len>2，更新节点的 v 值。注意到 x 所在的 d 的儿子，v 值改变了，于是在辅助多层分块树上x 所在儿子处执行单点修改，再继续递归进儿子作修改。注意当 x 处在最后一个块时，块长不是 B，而是 len \bmod B+1。

当 len \le 2，暴力维护。

void update(int d,int len,int x,int c){
    if(len>2){
        int B=sqrt(len+1);
        v[d]+=c,update(root[d],len/B,x/B,c);
        update(son[d][x/B],((x/B)^(len/B))?B-1:len%B,x%B,c);
    }
    else a[x][d]+=c,v[d]+=c;
    return;
}

这个东西应该可以做区间修改，像线段树一样用懒标记就行，但是由于作者太懒就让读者自己去探索吧。

区间查询

下面的代码以区间求和为例，实现了多层分块树的区间查询。

当 l=0 且 r=len 时，直接返回区间和 v_d。

当 len>2 时，分讨一下 l 和 r 是否在同一个块中，再利用儿子的信息和辅助多层分块树的信息递归往下查询，类似分块。

当 len \le 2 时，暴力维护。

int query(int d,int len,int l,int r){
    if(!l&&r==len)return v[d];
    int sum=0;
    if(len>2){
        int B=sqrt(len+1),siz;
        if((l/B)^(r/B)){
            sum =((l/B+1)^(r/B))?query(root[d],len/B,l/B+1,r/B-1):0;
            siz=((l/B)^(len/B))?B-1:len%B;
            sum+=query(son[d][l/B],siz,l%B,siz);
            siz=((r/B)^(len/B))?B-1:len%B;
            sum+=query(son[d][r/B],siz,0,r%B);
        }
        else{
            siz=((l/B)^(len/B))?B-1:len%B;
            sum=query(son[d][l/B],siz,l%B,r%B);
        }
    }
    else for(int i=l;i<=r;i++)sum+=a[i][d];
    return sum;
}

总代码

下面的代码用多层分块树实现了 【模板】树状数组 1，可以通过。

#include<bits/stdc++.h>
using namespace std;
constexpr int N=5e5+10;
int n,m,a[N],op,x,k,l,r;
struct duocengfenkuaishu{
    int root[N<<3],v[N<<3],a[4][N<<3],cnt=2;
    vector<int> son[N<<3];
    void build(int d,int len){
        if(len>2){
            int B=sqrt(len+1);
            root[d]=cnt,cnt++,build(root[d],len/B),son[d].resize(len/B+1);
            for(int i=0;i<=len/B;i++){
                son[d][i]=cnt,cnt++,build(son[d][i],(i^(len/B))?B-1:len%B);
            }
        }
        return;
    }
    void update(int d,int len,int x,int c){
        if(len>2){
            int B=sqrt(len+1);
            v[d]+=c,update(root[d],len/B,x/B,c);
            update(son[d][x/B],((x/B)^(len/B))?B-1:len%B,x%B,c);
        }
        else a[x][d]+=c,v[d]+=c;
        return;
    }
    int query(int d,int len,int l,int r){
        if(!l&&r==len)return v[d];
        int sum=0;
        if(len>2){
            int B=sqrt(len+1),siz;
            if((l/B)^(r/B)){
                sum =((l/B+1)^(r/B))?query(root[d],len/B,l/B+1,r/B-1):0;
                siz=((l/B)^(len/B))?B-1:len%B;
                sum+=query(son[d][l/B],siz,l%B,siz);
                siz=((r/B)^(len/B))?B-1:len%B;
                sum+=query(son[d][r/B],siz,0,r%B);
            }
            else{
                siz=((l/B)^(len/B))?B-1:len%B;
                sum=query(son[d][l/B],siz,l%B,r%B);
            }
        }
        else for(int i=l;i<=r;i++)sum+=a[i][d];
        return sum;
    }
}t;
int main(){
    scanf("%d%d",&n,&m),t.build(1,n-1);
    for(int i=0;i<n;i++)scanf("%d",&a[i]),t.update(1,n-1,i,a[i]);
    for(int i=0;i<m;i++){
        scanf("%d",&op);
        if(op==1)scanf("%d%d",&x,&k),x--,t.update(1,n-1,x,k);
        else scanf("%d%d",&l,&r),l--,r--,printf("%d\n",t.query(1,n-1,l,r));
    }
    return 0;
}

复杂度

空间复杂度

空间复杂度满足 T(n)=(\sqrt n+1)T(\sqrt n)+O(1)，而这个东西我显然是不会的，于是经过 AI 推导，有 T(n)=O(n)。

时间复杂度

建树

显然和空间复杂度相同，就是 O(n)。

单点修改