题目描述

区间修改，单点询问

思路简述

我们看到题目是"树状数组"，但是身为蒟蒻的我总是写不对差分，于是我们来看一看一种最坏复杂度为$O(m\sqrt n)$的想法——分块！

分块的优点在于其极其好写，思路简单，可视为一种暴力的改进版

我们把这个数组分为$\sqrt n$块，这样做的好处很明显，每次进行修改可直接对整块进行加法，不是整块则一个一个加，两个操作的复杂度均为$\sqrt n$。询问时只需直接输出块所积累的和加上在处理单个时所积累的和即可。

我们发现这玩意最大跑了500多ms，过了本题。

代码及解释

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll z,y,x,t,L,n,m,a[500005],b[500005],c[10005];
//a数组存储单个累计的和
//b数组存储改数位于哪一块
//c数组存储整块累计的和
void add(ll x,ll y,ll z){
    if(b[x]==b[y])//这里要特判
        for(ll i=x;i<=y;i++) a[i]+=z;
    else {
        for(ll i=x;b[i]==b[x];i++) a[i]+=z;//单块的和
        for(ll i=y;b[i]==b[y];i--) a[i]+=z;
        for(ll k=b[x]+1;k<=b[y]-1;k++) c[k]+=z;//整块的和
    }
}
int main(){
    scanf("%lld%lld",&n,&m);
    L=sqrt(n);//块的大小
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(ll i=1;i<=n;i++) b[i]=(i-1)/L+1;//填写b数组
    for(ll i=1;i<=m;i++){//没什么要说的
        scanf("%lld%lld",&t,&x);
        if(t==1){
            scanf("%lld%lld",&y,&z);
            add(x,y,z);
        }
        else printf("%lld\n",(a[x]+c[b[x]]));
    }
    return 0;
}