树状数组及其应用

一.树状数组概述

1.引例分析

对于一般的数组操作主要有两种方式：求前缀和，修改值。

如果我们使用一般数组实现，则可以在 O(1) 内修改一个数，但求前缀和的复杂度为O(n)；

如果我们使用前缀和数组实现，可以实现 O(1) 求得前缀和，但修改某个数更新前缀和的复杂度为O(n)。

可以发现，上述两种操作总有一个是常数操作，一个是线性操作。因此总的时间复杂度为O(n)。那么能否让O(1)的操作变慢，而让O(n)的操作变快来实现一个平衡呢？这就是我们要说的树状数组，它使得求和和更新的每个操作都变成O(logn)复杂度。

2.定义及原理

（1）树状数组定义

树状数组的含义是将数组表示为稀疏树形结构，是一种能在 O(logn) 时间内对数组进行更新和区间维护的数据结构。

其本质就是利用二进制的特性将前缀和数组维护在树上的一种数据结构

，类似于线段树。

树状数组与线段树功能和作用类似，在复杂度上也同级。二者的主要区别如下：

复杂性：树状数组在时间复杂度上的常数明显优于线段树，并且更加简洁和轻量化，代码效率高。
功能性：树状数组的功能比较局限，只能处理简单的具有前缀和累计特性的区间维护、修改问题。而且树状数组的作用被线段树完全覆盖，凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能够解决的复杂区间问题树状数组未必能够解决。

（2）树状数组原理

树状数组的实现原理可以

从前缀和和线段树的关系上

去考虑。我们都知道线段树的每个节点都直接维护着每一个子区间的Value，而根据前缀和知识可以得知，一段子区间的Value除了直接通过线段树节点求出，我们也可以间接的通过

SUM[r] – SUM[l-1]

来获得。那么我们是否可以将线段树简化（压缩掉某些节点空间），和数组长度一样只保留n个节点，并使得

树节点仅仅保存的是前缀和

呢？这样就能将查询和修改都降低到 O（logn）。答案当然是可以的，如下：

其中A为我们的数组，C为树状数组。

其实现思路大致为：对于任意下标 x，根据任意正整数关于 2 的不重复次幂的唯一分解性质，它都可以由二进制组成表示。进而可以写为：
$x = 2^{i_1} + ... + 2^{i_k} ( i_1 < ... < i_k,k\leqslant logx)$
。因此我们可以把 1∼x 中的数分为

最多

logx 个区间序列。这些区间分别为
$(x-2^{i_1},x],(x-2^{i_1}-2^{i_2},x-2^{i_1}],...,(0,x-2^{i_1}-2^{i_2}-...-2^{i_{k-1}}]$
。假设我们已经把这些区间的和算好了，那么只需要最多求 logx 次就能求得1∼x的总和。那么就需要考虑如何处理出这些区间内部的总和。可以发现，上面区间划分后，第一个区间包含
$2^{i_1}$
个数，第二个区间包含
$2^{i_2}$
个数，第k个区间包含
$2^{i_{k}}$
个数。还可以发现，每个区间的数字长度都是区间右端点二进制表示下最后一个1所对应的次幂。简而言之，对于我们分出来的每个区间(l,r]，其长度一定是r二进制表示下

最后一个1所对应的次幂。

比如一个正整数 x 的二进制表示为 10101，则正整数 x 可以被“二进制分解”成
$2^4 + 2^2 + 2^0$
。进一步地，区间 [1, x] 可以分成 O(logx)个小区间：

长度为 2^4 的小区间 (0, 2^4] ，长度为 100
长度为 2^2 的小区间 (2^4, 2^4+2^2]，长度为10
长度为 2^0 的小区间 (2^4+2^2, 2^4+2^2+2^0]，长度为 0

综上所述，树状数组就是基于这种思想，根据二进制将区间分为 logx 个子区间序列，维护每个子序列的前缀和，从而满足快速区间查询和修改。在树状数组中，每个下标 index 处存储的值表示该节点处所维护的子序列和，而该节点所

管辖的序列长度

为 index 二进制表示下

最后一个1所对应的次幂tk（比如110 就是 10），

其所管辖的区间为(index-tk,index]

。

二.树状数组实现

1.关键点代码

（1）lowbit(x) 函数

可以看到在树状数组中，最重要的一部分就是如何获取二进制表示下

最后一个1所对应的次幂，也就是“二进制分解”下最小的 2 的次幂。

这里我们就引入一个 lowbit(x) 函数用于返回数字x二进制的最后一位1，表示节点x所管辖的区间长度，比如lowbit(0010) = 10 , lowbit(1000) = 1000

int lowbit(int x){
   return x&(-x);
}

该函数的原理为：

利用的负数在计算机中是以补码存储的特性，即一个数的负数就等于对这个数按位取反再加一。那么原码从右往左为0的部位取反之后全是1，而为1的部位取反之后全是0，但是由于要补码加一，就会导致从右往左开始进位直到取反后第一个为0（也就是原码中第一个为1）的地方，而其他地方都是不变的，所以我们只需要进行 x&(-x)就可以取出最低位的1了。

（2）区间求和

使用树状数组求区间 1~x 的前缀和，当然如果是求任意区间的和我们可以通过 sum[r] – sum[l-1] 的方式去间接求和。因为每一个下标 x 处的前缀和都被划分为了多个子序列区间，我们可以通过不断累计这些子区间和来在 O(logx) 时间内获得。累计方式如上述例子所示，

通过 x-=lowbit(x) 来去往前一个子区间

，统计数据。

int getAns(int x){
   int ans = 0;
   for(int i = x;i>0;i-=lowbit(i)){
       ans+=sum[i];
       //ans = max(ans,sum[i]);
   }
   return ans;
}

注意：

这里一定>0判断，因为lowbit(0) = 0 ，会陷入死循环。

（3）单点更新

在单点更新时，我们只需要更新该点及其父区间的值即可。而在树状数组上，子序列的前缀和节点又是对称的，所以我们直接通过 x+=lowbit(x) 就可以移动到其父节点（将lowbit(x) 看作子区间长度）。

void Update(int x,int val){
   for(int i = x;i<=n;i+=lowbit(i)){
      sum[i]+=val;
      //sum[i] = max(sum[i],val);
   }
}

三.树状数组应用

1.求逆序对问题

问题描述：

给你一段长为 n 的数字序列，求出其中的满足 i < j 且 A[i] > A[j] 的逆序对的数目

分析：

这里可以用树状数组统计逆序对数目。我们可以将问题转化为求当前数字 x 处，[1,x] 区间内比 x 小的数目和。因此我们遍历整个数组，当插入当前数字时统计一下比当前数字小的数字个数getAns(x)，则 i-getAns(x) = 比当前大的数字个数（i表示当前已经插入几个数字了），总和就是逆序对数目。但是注意这里数字不一定是1~n连续的，也不一定都是正数，所以为了合理化应用树状数组我们需要进行离散化，比如：

val : 4 100 -1 6

index: 1 2 3 4

离散化以后，问题就转化为求出其中的满足 A[i] < A[j] 且 i > j 的下标逆序对的数目：

val: -1 4 6 100 (满足A[i]<A[j])

index: 3 1 4 2 (我们只需要找i>j的部分对数即可，相当于统计下标，变为1~n的开销)

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 7;
struct Node{
    int val,index;
    bool operator<(const Node &another)const{
         return val<another.val;
    }
}node[maxn];
int sum[maxn],n;
int lowbit(int x){
   return x&(-x);
}
int getAns(int x){
   int ans = 0;
   for(int i = x;i>0;i-=lowbit(i)){
       ans+=sum[i];
   }
   return ans;
}
void Update(int x,int val){
   for(int i = x;i<=n;i+=lowbit(i)){
      sum[i]+=val;
   }
}
int main()
{
    while(scanf("%d",&n)!=EOF&&n){
        for(int i = 1;i<=n;i++){
            scanf("%d",&node[i].val);
            node[i].index = i;
        }
        memset(sum,0,sizeof(sum));
        sort(node+1,node+n+1);//离散化
        int ans = 0;
        for(int i = 1;i<=n;i++){
            Update(node[i].index,1);
            ans+=(i-getAns(node[i].index));
        }
        printf("%d\n",ans);
    }
    return 0;
}

四.树状数组进阶

1.区间更新，单点查询

区间更新，单点查询

操作与上述的单点更新，区间查询操作相反。顾名思义，就是将一段连续区间内的所有值进行修改，然后查询单点的值。使用传统的树状数组肯定是不行的，这里我们可以通过

“差分”

操作，将该问题转化为单点更新，区间查询。

（1）差分数组

对于输入数组 a 来说，令
$d[i] = a[i] - a[i-1],1\leqslant i \leqslant n(a[0] = 0,d[1] = a[1])$
，则数组 d 就是数组 a 的差分数组。差分数组在区间序列上具有以下性质：

单点查询：因为
$d[i] = a[i] - a[i-1]$
，则
$a[i] = d[i] + a[i-1] = \sum_{j=1}^{i}d[j]$
，即单点

a[i] 的值可以通过求 d[i] 的前缀和来查询

。

区间修改：当修改区间

[l,r]

的值加上

x

时，对于差分数组 d 来说，只有

d[l] 加上了 x

，

d[r+1] 减小了 x

，因此只需要更新差分数组 d 的两个端点值即可。

（2）代码实现

综上所述，我们可以将区间修改转化为对差分数组区间端点的两次单点修改操作，将单点查询转化为对差分数组的求取前缀和操作，对差分数组进行树状数组建树。

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 7;
int a[maxn],c[maxn];

int lowbit(int x){return x&(-x);}

int getAns(int x){
   int ans = 0;
   for(int i = x;i>0;i-=lowbit(i)){
       ans+=c[i];
   }
   return ans;
}

void Update(int x,int val){
   for(int i = x;i<=n;i+=lowbit(i)){
      c[i]+=val;
   }
}

int main()
{
    while(scanf("%d",&n)!=EOF&&n){
        a[0] = 0;
        memset(c,0,sizeof(c));
        for(int i = 1;i<=n;i++){
            scanf("%d",&a[i]);
            Update(i,a[i]-a[i-1]);
        }

        //区间更新[x,y]加上k
        Update(x,k) //A[x] - A[x-1]增加k
        Update(y+1,-k); //A[y+1] - A[y]减少k

        //查询单点i值
        int sum = getAns(i);

    }
    return 0;
}

原文链接：https://blog.csdn.net/qq_40772692/article/details/88694970