[洛谷日报第22期]可以代替线段树的树状数组？

树状数组进阶（1）

*前置知识：树状数组，如果没有学过请右转这篇文章：传送门，前缀和，差分。

*本文代码均未经编译，如有错误请指出。

*前排cqy,826755370，喜欢EXO，bigbang，BTS，ikon，nine percent，本命世勋。

引入

大家学了线段树与树状数组后，一定会觉得树状数组比线段树好写（背）多了，常数也小多了（分析lowbit操作，每次操作中每个节点被访问的概率是1/2,所以常数是1/2）但是美中不足的是树状数组不能区间修改+区间查询啊。事实上，树状数组可以做到这些，还可以查询第k大（小）值。

1、最简单的单点修改+区间查询

这个就不要我讲了吧，直接上代码:

2、稍微难一点点的区间修改+单点0查询

这里用的是差分的思想。

我们设原数组为a，则我们需要维护一个差分数组delta： delta[i]=a[i]-a[i-1]delta[i]=a[i]a[i1]

那么我们可以得到： $a[i]=\sum_{j=1}^idelta[j]

现在a[i]被表达成了一个数组内连续的几个元素的，这样我们就解决了查询的问题，那么我们该如何修改呢？

当我们需要将区间[l,r]上的每个数都加上x时，因为d数组是个差分数组，所以我们可以直接在树状数组上将delta[l]加上x，delta[r+1]减去x即可，代码如下：

重点来了！

3、区间修改+区间查询

我们还是需要引入delta数组，这里的delta[i]表示区间a[i...j]都需要加上的值的和。那么当我们需要将区间[l,r]上的每个数都加上x时，我们还是可以直接在树状数组上将delta[l]加上x，delta[r+1]减去x。

那么问题来了，如何查询区间[l,r]的和？

我们设a[1...i]的和为sum[i]，根据delta数组的定义，则：

这样我们就不难看sum[i]是由哪三个部分组成的了。我们需要用一个asum数组维护a数组的前缀和，delta1与delta2两个树状数组，delta1维护delta数组的和，delta2维护delta[i]*i的和，代码如下：

等等……线段树不是还能查最大最小值吗，事实上树状数组也能查。

4、区间最值

哦，我知道了，我来建树：

如果你是这么写的，那么恭喜你……写错了。

以下内容有些难理解，先放一张图：

我们回想一下，当初刚学树状数组时为什么很多人总会说树状数组不能用来求最值。那是因为树状数组可以看作是一种前缀和，求和时可以用ans=ans[r]-ans[l-1]的性质，但是求最值无法满足这种减法的性质。分析一下我们刚才的代码，这么写也不是不对，而是每次查询前都必须初始化，时间复杂度难以接受，让我们换一种写法试一试：

现在更新完某个数，之前的元素的值都是正确的了，显而易见，建树的时间复杂度是O(nlogn)的。

那么我们该如何修改呢？当然不能在父亲节点上直接修改啦（手动滑稽），换了一种建树的方式就是为了维护c数组的正确性，修改同样也要保证c数组的正确性，那么在更新父亲节点时，我们就需要查询它所有的儿子节点，代码如下：

不难发现，每层循环都是lowbit操作，时间复杂度为O（王逸松）O（log(n)*log(n)),其实也没多慢，当n=1e5时，logn约等于16,就把一个logn当成常数看，线段树常数也挺大的啊，树状数组代码量还这么少。

修改是修改完了，那么问题来了，我们该如何查询？

假设当前查询的区间是[l,r]，那么我们从r到l对每一个c数组的元素所控制的叶子节点进行判断。假设现在进行到了第i项，那么显然易得（看图）：该数控制的a数组的元素是 [i-lowbit(i)+1,i]。设L=i-lowbit(i)+1,R=i。如果l<=L<=r那么就将c[L]加入最值的判断中，接着L--……，否则的话就只对第R个元素加入，然后R--……，代码如下：