线段树与树状数组练习
这篇文章曾经是我还很年轻的时候写的最长最用心的一篇。现在夕阳红了以后还是很佩服当时的那股劲。我不忍心擦去那时候的印记。
大改了一次文章。也有很多复杂度不对却水过去的地方，也修改了一次。
但是，看着当年的代码有些心塞啊。
——于2018-10-06
这篇文字不对线段树合树状数组是什么展开描述。
基础线段树
最普通的线段树代码大概是单点修改+区间查询。这份代码分为1个短程序和2个递归程序
短行程序：unite(int p)
就是在修改结束之后，Seg[p]的值用Seg[s[0]]与Seg[s[1]]的值来更新：
Seg[p].sum=Seg[p<<1].sum+Seg[p<<1|1].sum
递归程序：Getsum(int p,int l,int r)
判断边界：
if(Seg[p].l==l&&Seg[p].r==r)return Seg[p].sum;
递归，跳到下一个节点：
int m=(Seg[p].l+Seg[p].r)>>1;
if(r<=m)return Getsum(p<<1,l,r);
else if(m+1<=l)return Getsum(p<<1|1,l,r);
else return Getsum(p<<1,l,m)+Getsum(p<<1|1,m+1,r);
递归程序：Change(int p,int k,int w)//A[k]+=w
判断边界：
if(Seg[p].l==k&&Seg[p].r==k){Seg[p].sum+=w;return;}
递归，跳到下一个节点：
int m=(Seg[p].l+Seg[p].r)>>1;
if(k<=m)Change(p<<1,k,w);else Change(p<<1|1,k,w);
合并：
unite(p);
基础线段树的复杂度分析
对于Getsum程序：
在一个递归程序中：
一条线段有两个端点。这条线段的两个端点中，可能存在0至2个端点 与 当前线段树节点表示的线段的端点 重合。
为了方便表述，如果这条线段 有且仅有i(0<=i<=2)个端点 与 当前线段树节点表示的线段的端点 重合，我们就称之为“第i类线段”。
对于一条“第0类线段”，我们只需要花费O(1)的时间，使得
递归深度+1。
这条线段不被改变（r<=m或者m+1<=l） 或 变为两条“第1类线段”。
对于一条“第1类线段”，我们只需要花费O(1)的时间，使得
递归程序深度+1。
这条线段不被改变 或 使这条线段变为 一条“第1类线段”与 一条“第2类线段”。
对于一条“第2类线段”，我们只需要花费O(1)的时间，返回答案（Getsum的边界）。
由于线段树的深度是O(logn)，所以一次Getsum的时间复杂度是O(logn)。
对于Change程序：
很显然，一次Change的时间复杂度是O(树的深度)=O(logn)的。
带区间修改的线段树
这也是线段树强于树状数组的部分。
这里使用了tag的思想。按照基础线段树中Getsum的思路，同样，我们在遇到“第2类线段”的时候直接返回。那么这个递归程序的复杂度就是O(logn)。
但是这个节点的叶子节点还没有被修改。于是我们需要在这个节点打上一个tag。当需要访问呢到这个节点的子树的时候，先把这个节点的tag下传，再访问这个节点的子树。
这份代码分为3个短程序和2个递归程序。
短行程序：unite(int p)
与上面类似
短行程序：update(int p,int w)
更新节点p记录的和：
Seg[p].sum+=(Seg[p].r-Seg[p].l+1)*w;
更新节点p的tag：
Seg[p].tag+=w;
短行程序：down(int p)//下穿标记
下穿标记可以视为对两个儿子做一次update(son,tag)：
update(p<<1,Seg[p].tag); update(p<<1|1,Seg[p].tag);
清空p的tag
Seg[p].tag=0;
递归程序：Getsum(int p,int l,int r)
判断边界
下传标记：
down(p);
递归，跳到下一个节点
递归程序：Change(int p,int l,int r,int w)
判断边界
下传标记：
down(p);
递归，跳到下一个节点
合并
带区间修改的线段树的复杂度分析
相对于基础线段树，稍微改动的是Change部分。Change部分的复杂度可以参考基础线段树的Getsum复杂度分析。
可以得出，一次Getsum与Change的复杂度是O(logn)的。
区间和问题（此时的我还很年轻）
单点修改+区间查询
题目要求支持单点修改与区间查询。朴素线段树与朴素树状数组都是logn支持。
相信大家都更喜欢代码实现简单的树状数组吧。
线段树-当年的Pascal代码（可真长啊）：
我果然还是喜欢代码少的树状数组——其实似乎也不少多少，但是方便记忆一些（好吧其实是自己不喜欢线段树）
树状数组-当年的Pascal代码（可真长啊）：
现在都习惯压行了……真是坏毛病。
区间修改+单点查询
题目要求支持区间修改与单点查询。
我当时似乎就直接用了上面的代码（朴素线段树！），修改的复杂度其实是O(len)的。
线段树代码就略了吧，复杂度本来不能过的。
但是除了线段树之外，也可以使用树状数组。
一直想知道树状数组的logn区间修改与查询。后来知道，差分数组实现了这一点。
我们定义c[i]=a[i]-a[i-1]。
那么区间修改实际上只需要改变左端点与右端点的值。我们可以这样想：对于c[i]=a[i]-a[i-1]。如果 i与i-1都在[l,r]之间，那么c[i]其实不会改变。对于c[l]而言，c[l]=a[l]-a[l-1]。由于a[l-1]是不变的，所以c[l]要加上data。对于c[r+1]而言，c[r+1]=a[r+1]-a[r]，由于a[r+1]不变，所以c[r+1]要减去data。
那么对于单点查询，我们只需要求一趟前缀和即可。
所以我们用树状数组维护差分数组，即可解决单点查询与区间修改。
树状数组-当年的Pascal代码（可真长啊）：
初学时候的我在基本上掌握了树状数组的使用之后，来了一个小总结：
有所遗憾的是，差分数组的树状数组是不能与普通树状数组运用的。因此在我们把区间修改与单点查询都拉到O(logn)时，就不能继续操作区间查询了。
所以几个练习题也就把线段树与树状数组基本上涵盖了。
线段树单点修改为O(logn)，单点查询为O(logn)。区间修改为O(n)（用tag之后为O(logn)），区间查询为O(logn)，平均性比较好。
树状数组单点修改为O(logn)，单点查询为O(1)（在保留原数组的情况下）。区间修改为O(nlogn)，区间查询为O(logn)，单点修改与区间查询相差比较大。
差分数组的树状数组单点修改为O(logn)，单点查询为O(logn)。区间修改为O(logn)，区间查询为O(nlogn)。但是差分数组不能保留原数组，并且差分数组的树状数组与普通的树状数组不能一起维护。尽管线段树平均性较好，但是代码复杂度超过树状数组很多，所以也不被许多选手青睐。选择了时间复杂度，就要牺牲更多的时间去码程序，因此也是一种遗憾了。
不过没关系，完美并不美，有遗憾的东西才是完美的东西——毕竟这就更考验OIER的水平了，什么时候用什么算法，就是我们需要做的了。
可是当时我怎么知道树状数组其实也可以 区间修改+区间查询 呢？
区间修改+区间查询
codevs_1082（一个被我做过N遍的题……）
题目要求区间修改与区间查询。线段树的话，用tag就好。
当年的Pascal代码（可真长啊）（把unite与update直接写进去递归程序去了）：
接下来我们再讨论树状数组。
很显然一个差分数组是不可以解决区间查询与区间修改的。那么是否意味这树状数组就不能做这件事了呢？
不是！
考虑我们现在已经有了一个差分数组M[i]=A[i]-A[i-1]
接下来我们又有了一个维护差分数组的树状数组C[i]=M[1]+M[2]+M[3]+……+M[i]=A[i]
设S[i]为C[i]的前缀和。那么区间查询就变为了S[r]-S[l-1]。
现在关键是怎么把C[i]的前缀和算出来。
C[1]+C[2]+C[3]+……+C[i]=i*M[1]+(i-1)*M[2]+(i-2)*M[3]+……+2*M[i-1]+M[i]
(i-k)*M[k]不是定值，我们不能记录，但是我们发现i*M[i]是一个定值。
所以便可以得到
i*M[1]+(i-1)*M[2]+……+M[i] + 1*M[1]+2*M[2]+……+i*M[i] = (i+1)*(M[1]+M[2]+M[3]+……+M[i])=(i+1)*C[i]
所以
S[i]=C[1]+C[2]+……+C[i]=(i+1)*C[i]-(1*M[1]+2*M[2]+……+i*M[i])
所以令T[i]=i*M[i]。维护T与C即可实现。
当年的Pascal代码（可真长啊）：
尽管学到了新技巧，但似乎并不理想，因为这个时候树状数组的常常数已经非常大了。
在学会这一招后，自己发了一点感想。
只是这个差分数组与前缀和数组的配套就也要打上70多行的代码。所以——倒不如写线段树了。好吧我差不多要忘了线段树了。
而且这玩意很容易越界。比方说如果数据范围是longint，就可能需要一个int64来储存。不过常数小倒是真的——比线段树快多了。虽然理论上都是O(nlogn)的。
在做完了练习之后，接下来就的实践才是可贵的了。
差分数组多说一句
也是在学会了树状数组两种差分技巧之后得到的灵感启发：
差分数组的运用当然不止于树状数组一起。
比如说NOIP2012借教室就可以用差分数组完成O(n)的区间修改。比起任何树形结构都要快。只是有点美中不足，只能离线求解。因此，各位master有闲情也可以去看看吧。
关于区间加法与区间减法
区间加法与区间减法是在zkw的课件《统计的力量》里面学到的。OI里面也有很多类似的叫法，比方说信息的合并与分裂，其实都是说的一个意思。
线段树只基于区间加法，也就是说，序列问题中，只要需要维护的信息支持合并，理论上就可以使用线段树来做。支持区间加法的有很多，比方说sum（区间和），max（最大值），xor（异或和），以及其他很多奇奇怪怪的东西。
树状数组基于区间加法与区间减法，支持区间减法的信息就比较受到限制了，比方说max就不支持区间减法（就像我们知道一个序列的最大值以及他的子串的最大值，并不能得出剩余部分的最大值）。
——————————————分界线——————————————
接下来需要说一说对线段树的升级。
树状数组没有什么很大的拓展空间，但是线段树巨大的常数与代码量，以及只需要依赖于区间加法的优秀性质，总是让许多OIer想办法把它升级。
来说几个大家喜欢讨论的东西。
储存方式
主要分为堆式储存和链式储存。
堆式储存，也就是按照堆的方法，p的儿子是p<<1与p<<1|1。
一般在需要涉及到卡常数、速度的时候，需要用到堆式储存，例如zkw线段树。
一般堆式储存的空间需要开到4n（zkw线段树除外）。这是因为可能有一些没有划分好的节点的深度变为ceil(logn)+1，由于ceil(logn)的树是O(2n)大小的，对于某个深度为logn的节点，它的一个没有划分好的儿子的位置范围在[2n..4n]之间，因此需要O(4n)的空间。
实际操作中可以取4.5n。
链式储存，就是Seg[p]记录自己的左儿子与右儿子的位置。
一般需要动态处理的时候，需要用到链式储存，例如可持久化，线段树合并等等。
一般链式储存的空间只需要2n，因为其所需要的空间就是节点数。
实际操作中可以取2.5n。
动态开节点
虽然在初始的时候就把节点全部开完了。
但是只是想练习一下动态开节点。
最近搞树套树，结果不会线段树套线段树——且来学一发动态开节点版线段树。
动态开节点的方式也有很多：
在将要进入递归程序的时候，先判断这个节点是否存在，如果不存在，就先建立一个节点，然后搭建好父子关系，再访问这个节点。
思路与1一致，不过不单独写出来这句话（避免代码冗长），而是放在Down(p)里面。
已经进入了递归程序，发现当前节点p==0（即进入了一个空节点），就新建一个节点，并且令p==top（新建节点的编号）。
这样做，需要把所有的递归函数命名为一个int。在递归函数末尾，返回p（既可能是在这个递归程序里面新建的，也可能是之前就存在并没有被改动的）。在将要调用递归程序的时候（例如将要访问Seg[p].son[0]的时候）就重新赋值一次：Seg[p].son[0]=Function(Seg[p].son[0]);（其中Function(p)可能是Getsum(p)、Change(p)等等）
注意：
由于方法3需要返回节点p，那么如果一个递归函数本来就需要返回值（如Getsum(p)本来就需要返回一个sum），就会造成代码实现的不便利。
由于方法1与方法2代码的稍微冗长，有些场合（如线段树合并），并不会涉及到 上述类型函数访问空节点 的这种情况。所以我们还是可以选择方法3。
不下传标记的线段树
我似乎专门为此写了一篇文章……
zkw线段树
zkw当年在WC上有一个课件叫做《统计的力量》
里面把原理说得比较清楚了。
事实上背模板就好啦！
在这里专门说一下边界问题：
首先下标需要从原来的[1..n]变为[2..n+1]，所以事实上线段树需要容纳[1..n+2]的长度。相当于维护一个T数组，T[1]=0,T[n+2]=0,T[i]=A[i-1]。
k=ceil(log2(n+2)),M=1<<k,其中M表示最小的不小于n+2的二次幂。线段树数组大小为Seg[M<<1]，即[0..M<<1-1]。
A[i]对应的叶子节点是i+1(A变为T)+(M-1)(线段树叶子)=i+M，[l..r]对应的叶子区间是(l+M-1,r+M+1)。
双标记的线段树
我似乎也为此专门写了一篇文章……
乱入篇
我们用Splay来玩第三题如何？
个人解法：
总是觉得自己还是要掌握Splay做区间问题。虽然一般都是用线段树。
只用Pushdown的想法。
Tag标记的节点是还没有处理的节点。
那么我们在旋转的时候，要把p与f下传，还要下传p与f的儿子。因为后面的信息是通过儿子来更新的。
Pushdown的时候，当前节点的数值也要更新。
我似乎有为此专门写了一篇文章……