进阶数据结构

学到哪写到哪说是
既然打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;
}
`