分块-JZTXT

如果用暴力来把$[l,r]$区间内的数字都加上$c$，肯定会超时。
这时候，我们就可以用分块。

分块基本思想

分块，顾名思义，就是把一个数组分成很多区域，对于一整块区域，可以直接用一个数组来标记这个区间一共加上了几。对于不完整的块，可以直接在$a$数组上进行操作。

我们需要的数组：

$\ \ \ \ \ \ \ \ \ \ $ $block[i]$表示$i$所在的块的序号。
$\ \ \ \ \ \ \ \ \ \ $ $add[i]$表示序号为$i$的区间一共加上了几
$\ \ \ \ \ \ \ \ \ \ $ $a[i]$表示数组$a$

分块代码理解

代码部分1：分区域

输入了$a$数组后，我们需要把这个数组进行分区域，把分到区域的序号放在$block$数组里。每个块的长度为$\sqrt n$，所以，$a[i]$所在的区域序号为(i-1)/sqrt(n)+1，我们把这个数放到$block[i]$里面就完成了第一部分的操作。

代码部分2：一个元素的大小

使用分块，我们知道，下标为$i$的大小由两个部分组成。一个是本身的$a[i]$，还有一个就是存在$add$数组里的整块区间加上的数字。所以，它的总大小就是a[r]+add[block[r]]

代码部分3：区间加法

我们知道，区间加分为两个部分，一个是整体区域，一个不完整的部分。我们先来看不完整的部分。首先，我们进行区间加法的开始，肯定是$l$，但是我们不知道，到底是$r$大，还是$l$所在的区域更大，所以，我们要用带$min$函数，来看$l$到$r$中是否有完整的部分。

for (int i = l; i <= min(r, block[l]*v); i++) { //对于不在整块区域的区间加
    //block[l]*tmp l到l所在的区域结束这一小块区间
    a[i] += c;
}

接着，如果$l$和$r$所处的是同一个区域，就说明，已经完成了区间加法，可以返回了。

if (block[r] == block[l]) { //l和r所处的区间是同一块
    return ;
}

刚才处理的是左边部分的不完整部分，那么现在，就处理右边的不完整部分。

for (int i = (block[r] - 1) * v + 1; i <= r; i++) {
    a[i] += c;
}

最后，我们进行整块的加法。因为在$l$之前的部分已经算过了，$r$所在的部分也做过了，所以，我们只需要从两个区域的中间开始完整的加法。

for (int i = block[l] + 1; i <= block[r] - 1; i++) { //l到r中间的空间
    add[i] += c;
}

这题就解决了，下面是完整代码。

#include<cmath>
#include<vector>
#include<iostream>
#define endl "\n"
#define int long long
using namespace std;

const int N=50010;
int block[N],a[N],add[N];
int n,v;
//block 记录每个数字所处的块
//a 数组
//add 存每个块加上的数字

void Add(int l,int r,int c){//l~r +c
    for(int i=l; i<=min(r,block[l]*v); i++){//对于不在整块区域的区间加
        //block[l]*tmp l到l所在的区域结束这一小块区间
        a[i]+=c;
    }
    if(block[r]==block[l]){//l和r所处的区间是同一块
        return ;
    }
    for(int i=(block[r]-1)*v+1; i<=r; i++){
        a[i]+=c;
    }
    for(int i=block[l]+1; i<=block[r]-1; i++){//l到r中间的空间
        add[i]+=c;
    }
    return ;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cout.tie(0);
    cin>>n;
    v=sqrt(n);
    for(int i=1; i<=n; i++){
        cin>>a[i];
        block[i]=(i-1)/v+1;//给每个数字分块
    }
    for(int i=1; i<=n; i++){
        int opt,l,r,c;
        cin>>opt>>l>>r>>c;
        if(opt==0){
            Add(l,r,c);
            /*
            cout<<"IS"<<" ";
            for(int i=1; i<=n; i++){
                cout<<a[i]<<" ";
            }
            */
        }
        if(opt==1){
            //add[block[r]] 储存着下标为r的数字所需要加上的数字
            cout<<a[r]+add[block[r]]<<endl;
        }
    }
    return 0;
}