题目描述：

题目传送门

---

解题思路：

首先我们先忽略题目的标题（树状数组模板），我们来尝试一种新的算法——分块。

• 分块思想

分块是一种优美的暴力（by DFT）。他的核心思想在于将一个要维护的区间（长度为 $n$）分成又穷个 $\sqrt{n}$ 个子区间来进行分别维护。每个子区间的长度都为 $\sqrt{n}$，将我们所要查询的区间所覆盖的每个子区间的信息进行整合，就是我们要查询的区间的信息。

这样子将区间分块来处理有什么好处呢？因为它可以将对一个区间维护的复杂度均摊到每一个长度为 $\sqrt{n}$ 的小区间中，这中均摊会使得整体复杂度比原来的暴力更优，因为它可以每次把修改和查询的时间均摊为 $\Theta (\sqrt{n})$。

---

• 分块区间的构造

分块区间构造起来思维难度不高，我们直接在代码中的注释进行讲解和理解。

int S,C=0,belong[500010],st[10010],en[10010],sum[10010]={0};S代表每个子区间的长度，即为根号n取整。
C代表大区间所分成的子区间的个数，一般也是根号n取整
belong[i]代表原区间中的第 i 个元素所属子区间的编号
st[i] 表示第 i 个块的左端点，同理 en[i] 代表右端点
sum[i] 代表第i个块元素信息的整合，这里表示第i块中所有元素之和。inline void build()
{S=int(sqrt(double(n)));  //求出S的大小for(register int i=1;i<=n;i+=S)  //为每个块设立左端点和右端点{st[++C]=i;en[C]=min(n,i+S-1);}for(register int i=1;i<=C;++i)  //枚举所有的块{for(register int j=st[i];j<=en[i];++j)  //遍历每个块中的元素，将他们所属的块的编号记录{belong[j]=i;  //表示第j个元素是第i块的sum[i]+=a[j];  //统计第i块元素的和}}return ;
}

---

• 分块区间单点修改

显而易见，会因为单点修改而造成影响的只有此元素所在的块，因此直接修改就好了。

inline void single(int x,int k)  在第x个位置加上k
{a[x]+=k;sum[belong[x]]+=k;   //在x所属块的信息集合sum数组中进行修改return ;
}

---

• 分块区间的区间修改

我们使用一个数组 $delta$ ，$delt{a}_i$ 记录第 $i$ 个块 整个块被修改的变化情况，当且仅当这个块被完整的统一修改的时候，才会改变这个块的 $delta$。

设要修改的区间的左端点是 $x$,右端点是 $y$，那么要是 $x,y$ 刚好组成一个先前已经分块好了的块：

-------】【-------】【---块---】【-------】【-------】【-------[x-------y]

也就是说存在第 $i$ 个块使得 $s{t}_i=x\&e{n}_i=y$，那么直接改变 $delt{a}_i$ 的值即可。

  int l=belong[x],r=belong[y];if(l==r&&st[l]==x&&en[l]==y){delta[l]+=k;  //记录第 l 个块的变化情况。return ;}

可是，要是 $x,y$ 并不是理想的刚好在一个块中，而是同时包含了一个不完整的块呢？

-------】【-------】【-------】【-------】【-------】【-------[x------------------y]

很简单，对于 $x,y$ 区间内，那些完整的块我们通过改变 $delta$ 来改变，而那些不完整的块，我们通过单点修改 $single$ 来一一改变他们的原值。

  for(register int i=x;i<=en[l];++i)  //改变左边的不完整区间single(i,k);for(register int i=st[r];i<=y;++i)  //改变右边的不完整区间single(i,k);for(register int i=l+1;i<r;++i)  //完整区间统一修改delta[i]+=k;

因此一个完整的区间修改函数 $range$ 就出来了

int delta[10010]={0};
inline void range(int x,int y,int k)
{int l=belong[x],r=belong[y];if(l==r&&st[l]==x&&en[l]==y){delta[l]+=k;return ;}for(register int i=x;i<=en[l];++i)single(i,k);for(register int i=st[r];i<=y;++i)single(i,k);for(register int i=l+1;i<r;++i)delta[i]+=k;return ;
}

---

• 分块的区间查询

任然考虑查询一个 $x,y$ 的区间，如果 $x,y$ 在同一个块内，那么也许会是这么一种情况：

-------】【-------】【-------】【-------】【-------】【-------[x-y]

此时，$x,y$ 的确在一个块内，但是又并不是全包含这个块内，这中情况我们就需要特判处理

  int l=belong[x],r=belong[y],ans=0;if(l==r){for(register int i=x;i<=y;++i)ans+=a[i]+delta[belong[i]];  //最朴素的对该区间进行求和，此时delta数组就派上用场了。return ans;}

至于剩下的情况，我们依旧可以尝试像区间修改那样思考，分为左边的不完整块，中间的完整块，右边的不完整块三个部分进行处理。这事，我们一开始对块的信息整合数组sum和变化记录数组delta的功能就体现出来了，他们极大程度的优化了完整块的处理。

  for(register int i=x;i<=en[l];++i)  //左半部分ans+=a[i]+delta[belong[i]];for(register int i=st[r];i<=y;++i)  //右半部分ans+=a[i]+delta[belong[i]];for(register int i=l+1;i<r;++i)  //完整的块直接利用sum和delta卡速累加即可ans+=sum[i]+delta[i]*(en[i]-st[i]+1);

这样就是一个完整的分块区间查询函数：

inline int query(int x,int y)
{int l=belong[x],r=belong[y],ans=0;if(l==r){for(register int i=x;i<=y;++i)ans+=a[i]+delta[belong[i]];return ans;}for(register int i=x;i<=en[l];++i)ans+=a[i]+delta[belong[i]];for(register int i=st[r];i<=y;++i)ans+=a[i]+delta[belong[i]];for(register int i=l+1;i<r;++i)ans+=sum[i]+delta[i]*(en[i]-st[i]+1);return ans;
}

---

• 分块必备卡常技能

由于分块的查找和修改操作都是近似 $\Theta (\sqrt{n})$ 的，因此对于此题目而言就是 $\Theta (m\sqrt{n})$ 即为 $\Theta (500000\ast \sqrt{500000})$ ，有点悬，因此我们要学会一种和分块一样优美的暴力美学——卡常。

• 关闭输入输出同步流
  为什么快我不知道但是只要打上这么三行就会快很多。

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

• 将函数设为内联函数
  实际的操作即为在每个函数名前加个 inline 。

inline void build()

• 不知原因的 register
  在循环变量的定义前都加个 register 也会变快

for(register int i=1;i<=n;i+=S)

• 玄玄乎乎的++i
  试着把所有的循环累加的 i++ 换成 ++i，这样尽然也能卡常数？！

for(register int i=1;i<=C;++i)

这样我们就能卡着 1000ms 的实现在 C++14的编译器帮助下惊险 AC（一次还过不了，要考rp和手气）！

更多离谱的卡常技能还有循环展开利用高速缓存性质等奇怪的东西，这里就姑且不提。

---

CODE：

#include <iostream>
#include <cmath>
using namespace std;
int n,m,a[500010],pos,b,c;
int S,C=0,belong[500010],st[10010],en[10010],sum[10010]={0};
inline void build()
{S=int(sqrt(double(n)));for(register int i=1;i<=n;i+=S){st[++C]=i;en[C]=min(n,i+S-1);}for(register int i=1;i<=C;++i){for(register int j=st[i];j<=en[i];++j){belong[j]=i;sum[i]+=a[j];}}return ;
}
inline void single(int x,int k)
{a[x]+=k;sum[belong[x]]+=k;return ;
}
int delta[10010]={0};
inline void range(int x,int y,int k)
{int l=belong[x],r=belong[y];if(l==r&&st[l]==x&&en[l]==y){delta[l]+=k;return ;}for(register int i=x;i<=en[l];++i)single(i,k);for(register int i=st[r];i<=y;++i)single(i,k);for(register int i=l+1;i<r;++i)delta[i]+=k;return ;
}
inline int query(int x,int y)
{int l=belong[x],r=belong[y],ans=0;if(l==r){for(register int i=x;i<=y;++i)ans+=a[i]+delta[belong[i]];return ans;}for(register int i=x;i<=en[l];++i)ans+=a[i]+delta[belong[i]];for(register int i=st[r];i<=y;++i)ans+=a[i]+delta[belong[i]];for(register int i=l+1;i<r;++i)ans+=sum[i]+delta[i]*(en[i]-st[i]+1);return ans;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;for(register int i=1;i<=n;++i) cin>>a[i];build();int d;for(register int i=1;i<=m;++i){cin>>pos;if(pos==1){cin>>b>>c>>d;range(b,c,d);}else{cin>>c;cout<<query(c,c)<<endl;}}return 0;
}