【板子】分块解决线段树问题

小鱼儿 2024-03-25 22:29 80阅读 0赞

**不得不说，分块思想是真的帅啊**

[P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P3372 _ 1 - _ _ _ _luogu.com.cn]

题意：

![0531b0e139579e7f619144276d6d03ac.png][]

思路：

直接贴链接！

[算法学习笔记(23): 分块 - 知乎 (zhihu.com)][23_ _ - _ _zhihu.com]

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10;
    
    int n,m,sq,op,l,r,x;
    int a[mxn],block_st[mxn],block_ed[mxn],bl[mxn],sum[mxn],add[mxn];
    void modify_add(int l,int r,int x){
        if(bl[l]==bl[r]){
            for(int j=l;j<=r;j++){
                a[j]+=x;
                sum[bl[j]]+=x;
            }
        }else{
            for(int j=l;j<=block_ed[bl[l]];j++){
                a[j]+=x;
                sum[bl[j]]+=x;
            }
            for(int j=block_st[bl[r]];j<=r;j++){
                a[j]+=x;
                sum[bl[j]]+=x;
            }
            for(int i=bl[l]+1;i<bl[r];i++){
                add[i]+=x;
            }
        }
    }
    int query_sum(int l,int r){
        int res=0;
        if(bl[l]==bl[r]){
            for(int j=l;j<=r;j++) res+=a[j]+add[bl[j]];
        }else{
            for(int j=l;j<=block_ed[bl[l]];j++){
                res+=a[j]+add[bl[j]];
            }
            for(int j=block_st[bl[r]];j<=r;j++){
                res+=a[j]+add[bl[j]];
            }
            for(int i=bl[l]+1;i<bl[r];i++){
                res+=sum[i]+add[i]*(block_ed[i]-block_st[i]+1);
            }
        }
        return res;
    }
    void solve(){
        cin>>n>>m;
        sq=sqrt(n);
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=sq;i++){
            block_st[i]=n/sq*(i-1)+1;
            block_ed[i]=n/sq*i;
        }
        block_ed[sq]=n;
        for(int i=1;i<=sq;i++){
            for(int j=block_st[i];j<=block_ed[i];j++){
                sum[i]+=a[j];
                bl[j]=i;
            }
        }
        for(int i=1;i<=m;i++){
            cin>>op;
            if(op==1){
                cin>>l>>r>>x;
                modify_add(l,r,x);
            }else{
                cin>>l>>r;
                cout<<query_sum(l,r)<<'\n';
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[P3372 _ 1 - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P3372
[0531b0e139579e7f619144276d6d03ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/f09ee237c33d40258a5336c20a425e3e.png
[23_ _ - _ _zhihu.com]: https://zhuanlan.zhihu.com/p/114268236