高级数据结构：树状数组（区间修改、逆序对问题）

阅读原文时间：2021年04月25日阅读：1

前缀和与差分数组

1.前缀和数组

我们经常会遇到求一段区间的连续和问题，直接暴力求解（从左端点一直累加到右端点）时间复杂度为o(n)，貌似也不低…但是对于有m次询问的题，时间复杂度为O(mn)就显得有点捉襟见肘了，此时一个好的想法就是使用前缀和数组。

所谓前缀和数组，顾名思义就是维护一段序列的前缀和的数组，其实现也相当简单：

定义前缀和数组sum[N]，全部初始化为0，输入第i个数据x时，只要将sum[i]=sum[i-1]+x，就能递推得到整个前缀和数组，但要注意i要从1开始。

得到了前缀和数组，我们再来看求一段区间的连续和问题，如果左端点是从1开始，那么直接返回sum[i]即是答案，如果左端点为L且1，此时利用容斥原理，只要减去sum[L-1]的部分即是答案，时间复杂度仅为O(1)!

2.差分数组

记录数组中每个元素与前一个元素的差，注意不是连续的差，仅仅是相邻位置的差：minus[i]=a[i]-a[i-1]，此时我们注意到：，即差分数组的前缀和数组就是原数组。差分是一个很重要的思想，能让某些算法扩展出更多的功能。同样，差分思想与树状数组结合后，也会有一系列神奇的操作，具体看下文的介绍。

树状数组的使用

1.树状数组的建立：

树状数组建立的思想：

任意一个数均可用二进制表示，即被唯一分解为···，由此区间[1,x]可以进一步划分为O(logx)个小区间：

长度为：，

…… …… …… …… ……

长度为：···，···

对于任意自然数x，我们可以看出：区间的长度 = x的二进制只保留最末尾的1的值，而要取出这个最末尾的1我们需要借助位运算，具体实现代码如下，原理可以自己手算摸索下：

//lowbit操作
int lowbit(int x) {
    return x & (-x);
}

为什么叫树状数组呢？（其实也叫BIT和fenwick树，但树状数组无疑更形象···）这个问题很关键，强烈建议读者弄明白：

我们以1~8为例：

0001：：num[1]

0010：：num[1]+num[2]

0011：：num[3]

0100：：num[1]+num[2]+num[3]+num[4]

0101：：num[5]

0110：：num[5]+num[6]

0111：：num[7]

1000：：num[1]+num[2]+num[3]+num[4]+num[5]+num[6]+num[7]+num[8]

直接观察似乎看不出什么，但是如果我们将其理解成下面的树形结构，我们将发现一系列令人惊奇的规律！

1.树的深度为logn；

2.第x个结点的父结点为x+lowbit(x);

3.第x个结点的子结点个数为lowbit(x);

对于结论2，博主并不知道如何推导出来的，只能大致验证一下是否正确：

令x’=x+lowbit(x)，由与lowbit(x)定义为末尾的1，因此相加会强迫x进位即末尾的1会左移，其包含区间也一定至少扩大了两倍，lowbit(x’)>=2*lowbit(x)，所以x’ -lowbit(x’) +1 <= x +lowbit(x) – 2 *lowbit(x) +1 ——> x’-lowbit(x)+1<=x-lowbit(x)+1，其产生的区间一定包含了[x-lowbit(x)+1, x+lowbit(x)]，覆盖了[x-lowbit(x)+1, x]，也就是x’一定是x的父结点。实际上当你验证了1，2结点后，也能根据周期性推断出所有结点都具有此性质。

但有关本结论我无法给出严格的推导过程，只能大致验证一下是否正确，如果有哪位大佬能给出结论2的推导过程，还请留言告知本蒟蒻。

至于如何初始化树状数组，一个很直观且简单的方案就是先将数组全部置零，然后对每个位置调用单点修改函数更新数组的值（单点修改函数见下文），单点修改的时间复杂度为logn，一共n个位置，所以总时间复杂度为O(nlogn)：

for(int i=1; i<=n; ++i){
    cin >> x;
    update(i, x);
}

不过对于有些题，这样建立树状数组可能慢了一点，所以我们可以更高效的初始化：从小到大依次扫描所有结点，并通过lowbit操作找到它的父结点，累加进去。这样整个操作的时间复杂度仅为O(n)（测试了几题后发现运行时间没有明显的减少，额，这个我也很难解释为什么…），于此同时带来的代价则是耗费了更多的空间，如果遇见卡内存的题就可能直接MLE了~

const int N = 100005;
long long num[N], sum[N];
int n;//数据规模

//建立树状数组;
void build(){
    for(int i=1, x; i<=n; ++i){
        sum[i] += num[i];
        x = i + lowbit(i);
        if(x <= n)    
            sum[x] += sum[i];
    }
}

2.区间询问：

根据以上思想，我们用一个数组sum[i]来保存每个x对应区间的数之和，要计算num[1]到num[i]的和，只需要凑齐[1,i]这个区间，对于当前位置i，存储区间为[i-lowbit(i)+1，i], 那么它的上一个区间则以i-lowbit(i)结束，同时这也是其对应的x值，一直重复此操作，直到等于0为止（减去自身的lowbit值将得到连续的不重合的区间）：

//求num[1]到num[x]的和
long long solve(int x) {
    long long  ans = 0;
    for(int i=x; i>0; i-=lowbit(i))
        ans += sum[i];
    return ans;
}

3.单点修改：

如果修改了原数组num[i]一个位置的值，那么sum[i]数组中所有包含该值的位置都需要修改，即自身的所有父结点都需要修改，而x的父结点根据树状数组的特性可以知道等于x+lowbit(x)（加上自身的lowbit值将得到自身的父结点）：

//单点修改，x位置+y
void update(int x, int y) {
    for(int i=x; i<=n; i+=lowbit(i)) 
        sum[i] += y;
}

4.与差分数组结合后实现区间修改：

我们都知道树状数组的一个劣势就是无法进行区间修改，但是利用前面提到过的差分数组，我们却可以实现这个nb的功能。

区间修改，单点查询：

举个栗子：序列：2 3 4 5 6 7 9 差分数组：2 1 1 1 1 1 2

我们将原序列中的第2到第6个数+3 ：序列：2 6 7 8 9 10 9 差分数组：2 4 1 1 1 1 -1

此时我们发现差分数组中只有第2与第7两个位置的数据发生了改变。这是巧合吗？当然不是，其实只要稍微想想就能理解，一段区间（l，r）的数都增加了x，它们的差会改变吗？很显然不会，会改变的位置只有l与r+1。这样一个区间修改的问题就变为了单点修改的问题，只不过要修改两个点。同时我们知道差分数组的前缀和数组就是原数组，所以要实现区间修改，单点查询，我们只要将差分数组构造成树状数组，在进行区间修改时转变为单点修改就解决了！

这里再讲一下实际上用得更多的实现，其实我们可以不用构造原序列的差分数组，我们将原数组保留，然后建立一个全为0的数组，对其进行上述区间修改转单点修改操作（其实这个全为0的数组也是一个差分数组，只是它的原序列也全为0），这样做我们再查询前缀和，此时我们得到的其实就是原数组要增加的值，只要再与原数组的值相加就是最终答案。

区间修改，区间询问（要是弄不明白就直接上线段树吧）：

我们假设上面单点修改（不构造差分数组）的树状数组为bit[i]，原数组为num[i]，再构造原数组的前缀和数组sum[i]。

由上述分析得知bit数组的前缀和就是原数组要增加的值，即：

现在要求原数组的前缀和，则总共要增加的值为：

这个式子我们可以做一个变形，我们考虑bit[1]~bit[x]每一个数在式子中被运算的次数：bit[1]出现了x次，bit[2]出现了x-1次···bit[x]出现了1次，所以上式可变形为：。

我们目前只维护了bit[i]的前缀和，通过上式可知我们还要维护i*bit[i]的前缀和。

最终的答案就为：sum[x]+((x+1)*bit[i]的前缀和-i*bit[i]的前缀和)

5.二维树状数组：

从序列扩展到矩阵，一重循环改成二重循环即可：

//将(x，y)的值+z
void update(int x, int y, int z) {
    for(int i=x; i<=n; i+=lowbit(i))
        for(int j=y; j<=m; j+=lowbit(j))
             sum[i][j]+=z;
}

//从（1，1）到（x，y）的和
long long solve(int x, int y) {
    long long ans = 0;
    for(int i=x; i>0; i-=lowbit(i))
        for(int j=y; j>0; j-=lowbit(j))
            ans += sum[i][j];
    return ans;
}

区间修改的做法也能从一维拓展到二维，感兴趣的可以尝试着推导下。

例题及补充：

1.数星星（https://ac.nowcoder.com/acm/contest/965/B）

一道很经典的题目，同时也体现了树状数组的一个非常重要的用途：求逆序对！

先来看看这道题本身：粗略读题后的第一印象是这题应该是一个二维树状数组的问题，因为涉及到了两个方向——x轴与y轴。但是仔细读题，会发现y轴本身是有序的，呈一个升序排列！为充分利用这个有序性，我们可以沿y轴方向处理，这样对于题目“位于左下方”中“下方”的要求，实际上就已经满足且不需我们考虑了。于是，我们就只用考虑“左方”，即每颗星星之前有多少颗星星的x坐标小于等于该星星的x坐标。把横坐标看成一个序列，问题就转化为求每个数之前有多少小于等于它的数，这正是求逆序对的一个重要过程。

实际上我们已经有归并的方法来求得逆序对了，但是使用树状数组又快又实用，所以下面来看看如何用树状数组求逆序对：

按惯例举个栗子，假定降序为排序顺序，给出序列： 5 4 3 2 1

首先建立一个全为0的树状数组，然后我们依次扫描该序列，第一个数是5，我们就在树状数组第5个位置+1，同时计算树状数组1~5位置的前缀和，就得到该位置前面共有多少个数小于等于5（包括了它本身，减去1即可），答案累加这个值；第二个数是4，就在树状数组第4个位置+1，同时计算树状数组1~4位置的前缀和，就得到该位置前面共有多少个数小于等于4（同样包括了它本身，减去1即可），答案继续累加，以此类推直到扫描完整个序列，最终累加完成的答案就是逆序对数，本例很显然等于0。我们再来考虑排列顺序是升序又该如何操作：升序即要求每次求出某位置前有多少个数大于该位置的值，而上述过程我们算出的是小于等于该位置的数量，不过可以很快想到，利用容斥原理，用当前总共读入的数的个数减去小于等于该位置的数量，即可得到我们想要的答案。

2.数列操作（https://ac.nowcoder.com/acm/contest/965/A）

一个标准的模板题，这里之所以拿出来是因为这题卡了时间又卡了空间（但是loj上的这题一个都没卡，汗），所以不能用高效初始化，也不能用线段树，以及需要快速读入，其它就没什么了，权当检测下模板对不对吧。

顺便给一下快读的模板：

template<typename type> 
void read(type &num){
    int sign=1;
    long long res=0;
    char ch=getchar();
    while (!isdigit(ch)) 
        sign=ch=='-'? 0:1,ch=getchar();
    while (isdigit(ch)) 
        res=res*10+(ch^48),ch=getchar();
    num=sign? res:-res;
}

3.A Tiny Problem with intergers（https://ac.nowcoder.com/acm/contest/1032/B）

区间修改，单点查询。模板题，按上面讲的直接套。嗯……还是再次强调下有两种写法以及它们的区别：

构造差分数组：

其余的东西太占篇幅了，干脆不写了。。。
for(int i = 1; i <= n; ++i){
    cin >> num[i];
    update(i,num[i]-num[i-1]); //在输入的时候就构造差分数组
}
//输出时就不用加上原数组的值
cout<<solve(a)<<"\n";

不构造差分数组，这种写法更加常见也更好用：

同样占篇幅，不写，就是这么任性。。。
for(int i = 1; i <= n; ++i)
    cin >> num[i];      //输入时未构造差分数组
//输出时要加上原数组的值
cout<<num[a]+solve(a)<<"\n";

4.A Simple Problem with Integers（https://ac.nowcoder.com/acm/contest/1032/C）

区间修改，区间询问，具体解法参见上文。

5.打鼹鼠（https://ac.nowcoder.com/acm/contest/965/F）

二维数组模板题，直接套上面的模板就完事了，唯一要注意的是求从(a，b)到(c，d)的区间和的时候，不是solve(c,d)-solve(a-1,b-1)，而是solve(c,d)-solve(c,b-1)-solve(a-1,d)+solve(a-1,b-1)，自己画个图就知道了。

上面的例题没什么难题，主要是对应一些知识点，应该还算全面了，至于更多的有点难度的题，以后有机会再更新，讲实话，写博客真的好累啊，而且还没有什么人看QAQ。

手机扫一扫

移动阅读更方便

你可能感兴趣的文章

一键安装lnmp 环境

LeetCode 周赛上分之旅 #44 同余前缀和问题与经典倍增 LCA 算法

OpenLDAP服务器搭建

GaoNeng：我是如何为OpenTiny贡献新组件的？