线段树（SegmentTree）和树状数组（FenwickTree）
前⾔
在刷题过程中，经常会遇到求数组某区间之和的问题：给出数组-1]，求数组下标i~j的元素之和a[i]+...+a[j]，0<=i<=j<n。
纯暴⼒做法是O(n)，即把区间的数加起来。
好⼀点办法的是创建⼀个前缀和（prefix sum）数组p，使得p[i]=a[0]+...+a[i]，那么所求结果就是p[j]-p[i-1]，当然i=0需要特别处理⼀下。这样准备⼯作是O(n)，查询只需要O(1)。
⼀般来说，数组不变的情况下⽅法⼆已经够⽤了。但是当数组有可能改变的时候，每次改变都需要更新前缀和数组，效率不⾼。
好在，有专门的数据结构来满⾜这种操作需求。今天我们就来简单学习⼀下线段树（Segment Tree）和树状数组（Fenwick Tree）。
线段树
顾名思义，线段树是树。具体⼀点，⼆叉树。那么“线段”⼆字如何体现？是把i-j区间之和想象成i-j的线段（我瞎猜的）。简⽽⾔之，线段树就是把区间之和⽤树来显⽰。
很⾃然地，根是整个数组区间，然后左右分半，依次类推。奇数情况下是左边多还是右边多呢？其实都可以，不过考虑区间[a,b]，最⾃然的写法可分为[a,(a+b)/2]与[(a+b)/2,b]，当b-a是奇数时右边多，这样写起来更⾃然⽅便些。
从⽹上搜了个图，这样更直观：
image.png
怎么构造这棵树呢？
⾸先要决定树的节点。左右⼦节点等属性是很⾃然的。同时需要存储表⽰的区间，以及区间之和。
需不需要指针指向parent节点呢？⼤可不必。
⾄于重要的⼏个操作，构造，查询，更新，抓住递归的特点，⾃下⽽上地进⾏，⼀切都显得⾃然了。
构造：递归，先构造左右，再构造⾃⼰，这样其实是从底层往上构造。
查询：同样递归，假如查询的区间就是⾃⼰马上返回，否则就有三种情况：查询左边，查询右边，两边都有。
更新：和查询类似，不同的是⼀次只更新⼀个元素，所以只会⾛⼀边。路径相当于查询[i,i]，下到最底层更新值。注意路径之上的节点也要跟着更新和。
代码量还是不⼩的，毕竟⽤了树。
树状数组
树状数组（也叫Binary Indexed Tree）就是指⽤数组来表⽰⼀棵树，这样空间上更节约。类似的还有binary heap。
那么树怎么放进数组呢？根据维基百科，对于数组⾥的下标i进⾏⼀个特定的位运算，就可以获得其⽗节点所在的下标。听起来很神奇？刚开始我也不知所云，直到看了Competitive Programming Algorithms的解释：
image.png
翻译⼀下。本质上我们需要的就是⼀个函数g，使得0<=g(i)<=i，这样的话假如T[i]=A[g(i)]+...+A[i]，我们想要求i的前缀和，因为已经有了g(i)之后的了，于是往前看，右边界就是g(i)-1，那么左边界是哪⾥呢？⾃然还是利⽤g函数，也就是说前⼀段是A[g(g(i)-1)]+...+A[g(i)-1]，根据定义这就是T[g(i)-1]。然后依次类推直⾄到0。
这样时间复杂度主要取决于g函数。假如g(i)=i，那么T=A；假如g(i)=0，那么T就是前缀和数组。这些我们都知道并不是最优选择。所以这个数据结构巧妙的地⽅就在于g函数的设定，使得查询和更新都能达到O(logn)的效率。
g(i)的定义：将i⼆进制表⽰的末尾的连续的1全部换成0，例如g(0b1001)=0b1000，g(0b1100)=0b1100，g(0b1111)=0。或者可以⽤位运算阐释：g(i)=i&(i+1)。
除此之外，我们还需要⼀个运算来更新。因为假如要更新i下标，我们得知道这个i到底在哪⼀段上，也就是说要找到所有的j，使得g(j)<=i<=j，然后更新T[j]。假设这个运算为h。h(j)=j|(j+1)。以i=10为例，第⼀个j⾃然是i本⾝，然后就是h(0b1010)=0b1011=11，⽽
g(0b1011)=0b1000=8⼩于10满⾜条件；下⼀个是h(0b1011)=15，同样满⾜条件。通过⼏个例⼦可以看出，j|(j+1)肯定是⼤于等于j的。
同样引⽤cp-algo⾥⾯的图，绿⾊代表T涵盖的范围：
image.png
值得注意的⼀点是这⾥的T下标是从0开始的，也可以从1开始。
什么意思呢？之前往前推，我们需要⽤g(i)-1，那么假如我们直接让T[i]=|g(i)+1,i|范围的和，往前推就直接是g(i)了，更⽅便。但是这样有⼀个问题，就是i=0的时候不满⾜之前的假设。因此，我们让T下标都增加1，也就是说其实T[1]对应的是A[0]，T[0]是0。
g和h函数也要相应调整。g(i)=i−(i & (−i))也就是把最后⼀个1变为0.h(i)=i+(i & (−i))即最后⼀个1进位。此写法显得更对称⼀些，因此⽹上⼤多采⽤这种。
代码实现：
