基于多层分块嵌套的快速区间查询+修改算法

· · 休闲·娱乐

你是否因为分块算法的 O(\sqrt n) 区间操作太慢而烦恼？别着急，我们可以多套几层分块解决。

Part 1 双层分块嵌套

首先分析分块算法复杂度瓶颈。

整块查询非常慢，我们不难想到少开几块，可是这样散块可能非常多，怎么办？我们不妨继续使用分块来维护散块，根据数学知识，大块数量取 \sqrt[3]n，每个大块分的小块数量也取 \sqrt[3]n 最快。

此时我们的复杂度是 O(\sqrt[3]n) 的。

Part 2 多层分块嵌套

既然已经有了这样的优化思路，我们可以继续优化到 O(\sqrt[4]n)。那岂不是可以一直优化？

其实并不是，我们发现现在常数已经爆炸了。因此如果我们分块 k+1 层，那么时间复杂度事实上是 O(k\sqrt[k]n) 的，这样看起来就合理多了。根据我们的高中知识，当 k=\ln n 时取得最小值，此时：O(k\sqrt[k]n)=O(\ln n)。

但是这里有一个致命的问题！当 k=\ln n 时每层块数为自然对数 e，因此我们要对块数取整。

这里我取块数为二，容易证明，这样的区间操作复杂度是 O(\log n)。

我们可以采取递归的方式实现这个算法。

Part 3 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100010];
struct block{
    int l,r;//块左右端点
    int sum,add;//区间和懒标记
}tr[400010];
void pushup(int p){
    tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
}
void pushdown(int p){
    tr[p<<1|0].add+=tr[p].add;
    tr[p<<1|1].add+=tr[p].add;
    tr[p<<1|0].sum+=tr[p].add*(tr[p<<1|0].r-tr[p<<1|0].l+1);
    tr[p<<1|1].sum+=tr[p].add*(tr[p<<1|1].r-tr[p<<1|1].l+1);
    tr[p].add=0;
}
void build(int s,int t,int p){
    tr[p].l=s,tr[p].r=t;//记录块左右端点
    if(s==t){
        tr[p].sum=a[s];
        return;
    }
    int mid=s+t>>1;
    build(s,mid,p<<1|0);//递归建块
    build(mid+1,t,p<<1|1);
    pushup(p);
}
int query(int l,int r,int s,int t,int p){
    if(l<=s&&t<=r)return tr[p].sum;//整块直接返回
    pushdown(p);
    int mid=s+t>>1,res=0;
    //处理散块，继续套用分块
    if(l<=mid)res+=query(l,r,s,mid,p<<1|0);
    if(r>mid)res+=query(l,r,mid+1,t,p<<1|1);
    return res;
}
void modify(int l,int r,int c,int s,int t,int p){//同上
    if(l<=s&&t<=r){
        tr[p].add+=c;
        tr[p].sum+=c*(t-s+1);
        return;
    }
    pushdown(p);
    int mid=s+t>>1;
    if(l<=mid)modify(l,r,c,s,mid,p<<1|0);
    if(r>mid)modify(l,r,c,mid+1,t,p<<1|1);
    pushup(p);
}
main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,n,1);
    for(int i=0;i<m;i++){
        int op;
        cin>>op;
        if(op==1){
            int x,y,k;
            cin>>x>>y>>k;
            modify(x,y,k,1,n,1);
        }
        else {
            int x,y;
            cin>>x>>y;
            cout<<query(x,y,1,n,1)<<endl;
        }
    }
}