发布于 摸鱼世界
2020.03.23
前言
以前其实也有接触过树状数组，但当时只是以为自己学会了，实际上模板都没背下来
y总：大多数数据结构难写，难调，难想，树状数组是一股清流，好写，好想。
今天就来说说树状数组。
正文
基本
首先认识树状数组能解决的基本问题：
1.单点修改
2.区间查询
就这两个了！区间修改&单点查询也是利用差分+这两种操作完成的。
树状数组的优势相较于普通数组，就是把修改和查询的时间进行了一个折中，把原来的修改\(O(1)\)，查询O\((n)\)优化为了修改，查询都是\(O(logn)\)。
接下来讲讲是怎么理解并实现树状数组的。
对于树状数组，我们维护了一些区间和，暂时把它们叫做c[]，原本的就叫做a[]吧。
假设当前要维护的数的总数为x，很显然(真的很显然)，我们可以把x拆成若干个2的幂的形式相加。为了方便表达，\(x=2^{i_k}+2^{i_{k-1}}+...+2^{i_1} \,\)，并且\(i\)序列递减.\(k<=log(n)\)。
这样对于当前的x，如果我们维护这样k个区间，分别表示：\((x-2^{i_1},x],(x-2^{i_1}-2^{i_2},x-2^{i_1}]...,(0,x-2^{i_1}-...-2^{i_{k-1}}]\)，就可以在\(O(log(x))\)的时间内求出1-x的前缀和了。
所以树状数组就是用来快速的维护这些区间的。
我们发现，右端点每次减去的二的次幂，恰好对应减去了上一次右端点二进制表示下的最后一个1。
举个栗子。\((5)_2=101\)，\(5=2^2+2^0\)，按照过程，第一个右端点减去的应该是\(2^0\)，得到\(5-1=4,(4)_2=100\)。第二个右端点减去的是\(2^2\)，得到\(4-4=0,(0)_2=000\)，两次操作，刚好把这两个1给对应减去了。
虽然看起来模拟很麻烦，但是在实际实现中，我们如果要找到这个数二进制下的最后一个1对应的数值，我们只需要用O(1)的时间计算。只需要这样写：
//声明包含库之后写
#define lowbit(x) (x&-x)
//或者写成这样函数的形式
int lowbit(int x)
{
return x&-x;
}
//需要用的时候直接调用就好了接下来就是怎么具体维护这个c[]的问题了。因为对于每一个右端点，区间的长度是固定的(lowbit(x))，所以我们只需要用右端点作为数组下标就好了，即c[R]=a[R-lowbit(R)+1~R]。
接下来出场的是树状数组的经典例子。目的是为了更直观地看出在树状数组中各个节点(?)之间的关系。
那现在如果要对某个单点进行修改的话应该怎么做呢？先考虑修改一个单点会影响到哪些c[]的值。
继续举例子。
比如我要修改a[1]的值，根据图片，很明显在这个例子中会影响到c[1],c[2],c[4],c[8]的值，它们全部都要变化。我们来观察这些数字的特性。首先把我要修改的下标和影响的下标都用二进制表示出来。
0001->0001,0010,0100,1000
发现什么了吗？再举个例子，这次修改a[5]的值。
0101->0101,0110,1000
是的，就是从当前这个下标开始，每次增加自己二进制表示下的最后一位对应的值。即i+=lowbit(i)，直到超出序列总长度。
这样，单点修改操作就很容易完成了。
void add(int start,int value)
{
for(int i=start;i<=n;i+=lowbit(i))
c[i]+=value;
}然后要考虑的，就是如何快速求前缀和。
依然通过举例子来发现规律。
1 求a[1]~a[7]的前缀和。
根据上面的图，我们需要返回c[7]+c[6]+c[4]的值。
0111->0111,0110,0100
2 求a[1]~a[5]的前缀和。
0101->0101,0100
我们发现，从起始位置开始，每次的下标都减去了二进制表示下的最后一位所对应的值。
所以我们可以这样来实现：
int ask(int x)
{
int tmp=0;
for(int i=x;i;i-=lowbit(i))
tmp+=c[i];
return tmp;
}要注意的是，询问得到的是存进去的数中的前缀和，所以如果要查询[l,r]区间的值，请用ask(r)-ask(l-1)得到。
洛谷模板题传送门
差分
洛谷模板题2传送门
不要问为什么还有2
可以看到，在原本的树状数组的基础上，它把基本操作变成了这样两个：
1.区间修改
2.单点查询
但是！树状数组在本质上还是只能维护单点修改&区间查询两个操作的，我们要怎么样才能把这两组操作之间完成一个转化呢？
先从单点修改->区间修改入手
如果在没有查询的题目里遇到区间修改的操作，我们会怎么做？当然是差分。如果要在[l,r]加上c，只需要a[r+1]-=c,a[l]+=c就可以了。
树状数组同理。再考虑单点查询。因为差分之后树状数组所求得的前缀和，也是差分数组的前缀和，恰好对应了需要查询的单点值，所以只需要在添加的时候不直接增加a[i]，而是增加a[i]-a[i-1]。
参考代码
差分+公式
理解了上面的差分树状数组，接下来还有更毒瘤
在上面的两个操作中，我们实际进行的操作都是一个单点+一个区间，两个操作都是单点就不用说了
也就是说，我们的树状数组又要实现这两个功能：
1.区间修改
2.区间查询
首先，为了照样完成区间修改操作，差分的思想我们必须保留，否则挨个修改会使时间复杂度爆棚。
那么我们要怎么在差分的情况下完成区间查询呢？
我们先来分析一下问题。区间查询，本质上是求原本的a[]的前缀和。但是因为每一个a[]中的值都是以差分b[]的形式存储的，所以每一个a[]的值我们都要用一次\(\sum_{i=1}^x b[i]\)来求得，但是我们要求的是前缀和，所以我们每次查询要求的是这样一个玩意：
\(\sum_{i=1}^x \sum_{j=1}^i b[i]\)
我们发现，对于每一个b[i]，它被累加的次数是一定的，这个时候用循环累加就很浪费时间。观察一下，每个\(b[i]\)在这个过程中，会被累加\((x-i+1)\)次。看下面的图形就知道了。
b1
b1 b2
b1 b2 b3
b1 b2 b3 b4
...
b1 b2 b3 b4 b5 ... bx于是我们的公式就可以变形成\(\sum_{i=1}^x (x-i+1)*b[i]\)。
再从括号里把-i项提取出来，得到\(\sum_{i=1}^x (x+1)*b[i] - \sum_{i=1}^x b[i]*i\)
于是，就变成了维护两个差分树状数组的问题了。
::aru
