学到哪写到哪说是
既然打ACM可以用板子，我就不用再隔几天敲一遍板子了
只能说赢麻了
线段树
线段树是一种利用二分思想的数据结构，主要用于区间修改以及查询问题。
它的基本思想是可以用一下一个图来表示，其中最底层的是原数组
简单来说，对于每个区间的修改或者查询操作，我们都会将它用尽量大的小区间来表示。比如我们如果要查询a1到a3的和，我们就只需要查询a1和a2的根节点以及a3，而不用查询a1和a2。修改操作也是如此。
比如在修改时，我们假如要给1到4整体加1，那么只需要给写有10的节点加上1* 4即可。但这样会导致一个问题，那就是如果查询到更小的区间该怎么办。解决方法是通过向下传递，比如给10这个节点加上1，那么10把这个1再传递给3和7，然后再往下传递，直到传递到叶子结点。
但这样做的话每次修改好像都要 区间长度* logn次计算，还不如直接修改，于是我们有有了如下想法：
只有当查询到小区间或者修改到小区间时对其进行更新，其余情况只需把需要修改的值保存在他们的父节点上即可。例如我们要对1到4加上1，那么就只需要给值为10的这个节点加上4* 1，同时打上1的标记。如果再给1到4加一，那么就再加上1* 4，标记也++变为2.表示为需要向下传递2.然后此时如果我们需要查询1道2的和，需要从10的节点向下查找，此时就将10节点上的标记传递给子节点，值为3的根节点的值加上2* 2，同时继承标记2,值为7的根节点同理。然后我们判断发现值为3的节点的区域和要求的区域正好重合，于是直接返回节点3的当前值即可
完整代码如下，代码整体很好理解，不过比较长（比较不好理解的应该有修改时的down操作和up操作，如果判断一个节点的区域和要求的区域有重合但并不是完全覆盖，说明要求它的子节点，所以就需要down更新标记和答案。而全部更新完以后还需要up操作将最终值重新反馈给根节点。）
#include<bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
#define int long long
using namespace std;
const int maxn=5e5+7;
int n,m;
int ans[maxn<<1],tag[maxn<<1];
int a[maxn];
void up(int p)
{
ans[p]=ans[ls]+ans[rs];
return;
}
void build(int p,int l,int r)
{
if(l==r)
{
ans[p]=a[l];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
up(p);
}
void f(int p,int l,int r,int k)
{
ans[p]+=(r-l+1)*k;
tag[p]+=k;
}
void down(int p,int l,int r)
{
int mid=(l+r)>>1;
f(ls,l,mid,tag[p]);
f(rs,mid+1,r,tag[p]);
tag[p]=0;
}
void update(int p,int l,int r,int sl,int sr,int k)
{
if(l>=sl&&r<=sr)
{
ans[p]+=(r-l+1)*k;
tag[p]+=k;
return;
}
down(p,l,r);
int mid=(l+r)>>1;
if(sl<=mid) update(ls,l,mid,sl,sr,k);
if(sr>mid) update(rs,mid+1,r,sl,sr,k);
up(p);
}
int cha(int p,int l,int r,int sl,int sr)
{
int res=0;
if(l>=sl&&r<=sr)
{
return ans[p];
}
down(p,l,r);
int mid=(l+r)>>1;
if(sl<=mid) res+=cha(ls,l,mid,sl,sr);
if(sr>mid) res+=cha(rs,mid+1,r,sl,sr);
return res;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n);
for(int i=1;i<=m;i++)
{
int t,x,y,z;
scanf("%lld",&t);
if(t==1)
{
scanf("%lld%lld%lld",&x,&y,&z);
update(1,1,n,x,y,z);
}
else
{
scanf("%lld%lld",&x,&y);
printf("%lld\n",cha(1,1,n,x,y));
}
}
return 0;
}
树状数组
树状数组是利用线段树思想的一种衍生数据结构
众所周知，这是线段树
假如我们要求1到3的和，我们会用3+3=6，假如我们要求1到4的和，那我们能直接得到10不用计算
如果我们要求2到4的和呢？我们可以用2加上7来得到，但在树状数组中摒弃了这个想法，转而使用前缀和来实现，即用1到4的和减去1。但这样做的目的是什么？
我们可以想一下，如果我们对于每个区间都采用前缀和的方法求解，那么线段树中的某些部分是永远都不会用得到的。
而永远用不到的部分则是对于每个节点的右子节点，可以随意举例一个区间，尝试下是否能被图上剩下的这些节点所表示
答案是显然可以的。
然后我们再观察一下，会发现剩余节点的数量正好和n相同，于是我们想：是否可以将这些数全都填入1~n中对其进行操作？这便是树状数组的由来。
树状数组最核心的一个操作是lowbit操作，他的作用是求出每个节点的位置在用二进制表示后的最后一个1的位置。树状数组有个很有趣的性质，就是在成型的树状数组中，对于每个i,lowbit(i)的值就是i所对应的节点的长度。比如图中10对应的节点长度就是4,3对应的长度是2，1对应的长度是1（lowbit操作值与数值没关系，只与位置有关系）
并且还有一个性质就是对于一个i，i+(lowbit(i))就是它的父节点的位置，所以在修改单个点值时我们需要另i不断加上lowbit(i)直到n来修改值
而查找操作则是令i不断减去lowbit(i)直到0，然后把和全部加上，得到的便是从1到i的前缀和
完整代码如下
#include<bits/stdc++.h>
#define int long long
using namespace std;
int lowbit(int x)
{
return x&-x;
}
int n,m;
const int maxn=2e6+10;
int tree[maxn],a[maxn];
void update(int pos,int x)
{
while(pos<=n)
{
tree[pos]+=x;
pos+=lowbit(pos);
}
}
int sum(int x)
{
int res=0;
while(x>0)
{
res+=tree[x];
x-=lowbit(x);
}
return res;
}
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
update(i,a[i]-a[i-1]);
}
for(int i=1;i<=m;i++)
{
int t;
int x,y,z;
scanf("%lld%lld",&t,&x);
if(t==1)
{
scanf("%lld%lld",&y,&z);
update(x,z);
update(y+1,-z);
}
else printf("%ld\n",sum(x));
}
return 0;
}
`