树状数组详解(一维+二维+差分+前缀和+公式优化)

2021-04-27 2024-11-04 约 3500 字预计阅读 7 分钟 - 次阅读

1 问题引入

有这样一个问题:现在有这样一个数列$a$，你需要进行下面两种操作：

将某一个数加上 $x$
求出某区间$[l,r]$每一个数的和

数列长度为$n( 1\leq n \leq 10^5)$，操作总数为$p(1\leq p \leq 10^5)$，时间限制为$1s$，如果是你你该如何处理？

我们先来看看暴力能否出奇迹，对于单点修改操作，我们确实能在$O(1)$的时间完成，而对于区间求和操作，那么我们累加求和的时间复杂度为$O(r-l+1)$，在最坏的情况下，高达$O(n)$ ，这样算下来，处理这个问题需要$O(np)$的时间复杂度，$1s$是处理不完的。

那么，区间求和前缀和又是否可以呢？我们发现，如果用前缀和处理实际上就是让区间求和变为$O(1)$，而让单点修改就变为$O(n)$了，这样并没有任何变化。所以暴力做法肯定是不行的。

学过线段树的同学一定知道怎么写这道题，没学过的可以去学习下，这里指路一篇$blog$:线段树入门

但是，这道题用线段树未免也太大材小用了,况且线段树的代码量也十分多，所以树状数组就出现了，代码量少，简单易实现。我们继续往下看。

2 树状数组（单点修改，区间查询）

树状数组简单剖析

其中$A$数组是原数组，而$C$数组就是树状数组。为什么要一开始就放图呢？我们来发现一下它们的规律：

$C1 = A1$ $C2 = A1+A2$ $C3 = A3$ $C4 = A1+A2+A3+A4$ $C5 = A5$ $C6 = A5+A6$ $C7 = A7$ $C8 = A1+A2+A3+A4+A5+A6+A7+A8$

我们不难发现：$C[i] = A[i - 2^k+1] + A[i - 2^k+2] + … + A[i];$， //$k$为$i$的二进制中从最低位到高位连续零的长度，换句话说，$C[i]$管辖了包括$A[i]$自己的前$2^k$个元素，这样的好处是什么呢？我们发现，如果对某个元素更改了，那么我们只需要更改管辖了这个元素的$C$，那么如果对某个区间$[l,r]$求和，那么我们相当于求$SUM[r]-SUM[l-1]$，而求$SUM[i]$也特别简单，我们只需要求$i$这个点管辖的区间和$C[i]$并统计，再往前跳到未被$i$管辖的区间累加$C$即可，直到到达数组头部。也就是$SUM[i] = C[i] + C[i-2^{k_1 }]+ C[(i - 2^k_1) - 2^k_2] + …..；$。

lowbit函数求解$2^k$

那么关键的一个问题来了，我们怎么求$2^k$，我们知道$k$为$i$的二进制中从最低位到高位连续零的长度，所以$2^k=i&(i-1)$，这里不予证明。求$2^k$一般用一个函数来描述，即$lowbit$。如下：

1
2
3
int lowbit(int x){
    return x&(-x);
}

add函数：单点修改
对于单点修改，我们实际上很好处理，只需要将管辖这个点的$C$全部加上$x$即可，如下：

1
2
3
4
5
6
void add(int pos,int x){
    while(pos<=n){
        c[pos]+=x;
        pos+=lowbit(pos);
    }
}

getSum函数：区间求和
区间求和就是上文中利用的原理，我们很容易就能实现，我们首先要能求前$i$个元素的和，如下：

1
2
3
4
5
6
7
8
int getSum(int pos){
    int ans=0;
    while(pos>0){
        ans+=c[pos];
        pos-=lowbit(pos);
    }
    return ans;
}

那么，$[l,r]$区间的和自然易得，即为：getSum(r)-getSum(l-1)。

时间复杂度分析
不难，发现，树状数组实际上就是一棵树，其有$n$个结点，那么易知在单点修改和区间求和的问题处理上都能在$O(log_2n)$的时间内完成。所以总体时间复杂度为$O(nlog_2n)$，是非常有效的。

3 差分树状数组（区间修改，单点查询）

原理
我们首先要知道差分数组是什么，和前缀和数组其实离不开关系，$c[i]=SUM[i]-SUM[i-1]$，其中原数组相当于可以看成是存储了相邻两个前缀和的差值，那么映射到差分数组（因为原数组可以看成是存储了差分数组的前缀和）我们可以看成就是存储了相邻两个数之间的差值，即$d[i]=c[i]-c[i-1]$，而$d[1]=c[1]-c[0]=c[1]$，所以我们利用这个关系可以推导出:$a[i]=d[1]+d[2]+…+d[i]$，那么我们就是将单点查询转化为区间求和了，那么如果对于区间修改呢？对于差分数组，假设修改区间$[l,r]$，让这个区间每个元素$+x$，我们只需要更改$d[l]=d[l]+x$，$d[r+1]=d[r+1]-x$，这样我们保证只会影响到$[l,r]$这个区间的元素。故我们通过差分把这个区间修改、单点查询的问题转化为单点修改区间查询的问题，那么我们存储的树状数组实际和是哪个存储是差分数组的树状数组。

4 差分树状数组+公式优化（区间修改，区间查询）

原理
刚刚结束了利用差分实现区间修改，单点查询，而对于区间查询，这确实也是个问题。如果我们知道了区间查询，实际上这种类型的题我们就没必要使用线段树去写了，直接用树状数组就可以解决。我们来看，实际上还是利用差分数组，那么如何将区间查询的时间复杂度也变为$O(log_2n)$呢，区间查询的基础是快速求出数组$a[1:n]$的前缀和，而显然数组$a[1:n]$的前缀和为 $$a[1]+a[2]+…+a[i]=d[1]i+d[2](i-1)+…+d[i]1=d[1](i+1)+d[2](i+1)+…+d[i](i+1)-(d[1]*1+d[2]*2+…+d[i]i)\ =(i+1)(d[1]+d[2]+…+d[i])-(d[1]*1+d[2]*2+…+d[i]*i)$$ ，所以我们就可以在原来的数组$c[i]$记录$d[i]$的基础上。再开一个数组记录$d[i]*i$即可。这样，我们就实现了区间查询。

5 二维树状数组（单点修改，区间查询）

解释
数组$C[x]$记录了的是右端点为$x$、长度为$lowbit(x)$的区间的区间和。那么我们也可以类似地定义$C[x][y]$记录的是右下角为$(x,y)$，高为 $lowbit(x)$，宽为$lowbit(y) $的区间的区间和。那么按照一维树状数组去处理即可，这里给出这三个函数。
$lowbit$函数

1
2
3
int lowbit(int x){
    return x&(-x);
}

$add$函数

1
2
3
4
5
6
7
8
void add(int x,int y,int value){
    //在(x,y)处增加value.
    for(int i=x;i<=n;i+=lowbit(i)){
        for(int j=y;j<=n;j+=lowbit(j)){
            c[i][j]+=value;
        }
    }
}

$getSum$函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
int getSum(int x,int y){
    //如果求解[x1,y1]~[x2,y2]之间的和，那么就是getSum(x2,y2)-getSum(x2,y1)-getSum(x1,y2)+getSum(x1,y1).
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i)){
        for(int j=y;j>0;j-=lowbit(j)){
            ans+=c[i][j];
        }
    }
    return ans=0;
}

6 二维差分树状数组（区间修改，单点查询）

二维差分树状数组推导
处理这个问题，我们首先要知道二维差分数组怎么表示，那么还是和二维前缀和数组联系起来，即$c[i,j]=SUM[i,j]-SUM[i-1,j]-SUM[i,j-1]+SUM[i-1,j-1]$，原数组实际上就可以看做是存储了$(i,j)$的前缀和与$(i-1,j)$和$(i,j-1)$的前缀和的差值。那么映射到二维差分数组即是$d[i,j]=c[i,j]-c[i-1,j]-c[i,j-1]+c[i-1,j-1]$，其中$d[1,1]=c[1,1]$，那么$c[n][m]=\sum_{i=1}^{n}\sum_{j=1}^{m}d[i][j]$，所以对于区间修改，我们是给$(x_1,y_1),(x_2,y_2)$之间形成的矩阵加上$x$，那么实际上我们只需要变动四个点，$d[x_1][x_2]+=x,d[x_1][y_2]-=x,d[x_2][y_1]-=x,d[x_2][y_2]+=x$ ，那么这样就和一维差分数组一样了，区间修改单点查询问题我们利用二维差分数组就可以转化为单点修改区间查询了，我们的树状数组则是建立二维差分树状数组。那么这样这三个函数同理也很简单的就可以写出来了。

7 二维差分树状数组+公式推导（区间修改，区间查询）

推导
和一维的一样，如果我们需要求解$(x_1,y_1)$和$(x_2,y_2)$形成矩阵的和，同时又要实现区间修改，那么在原有的二维差分树状数组是行不通的，那么我们就需要将区间查询的时间复杂度也降为$log_2n$，我们知道$SUM[i][j]=\sum_{x=1}^i\sum_{y=1}^ja[x][y]$，而$a[x][y]=\sum_{u=1}^x\sum_{v=1}^yd[u][v]$，则$SUM[i][j]=\sum_{x=1}^i\sum_{y=1}^j\sum_{u=1}^x\sum_{v=1}^yd[u][v]$，由于这个公式非常复杂，所以我们可以按照一维差分树状数组那样来统计$d[u][v]$出现了多少次，我们发现，从$a[1][1]$到$a[i][j]$，$d[1][1]$都需要出现一次，则$d[1][1]$出现了$i\times j$次，那么同理$d[1][2]$出现了$i*(j-1)$次，其余同等规律。所以 $$SUM[i][j]=\sum_{x=1}^i\sum_{y=1}^jd[x][y](i+1-x)(j+1-y)$$
，我们同样可以将这样拆分成四个部分，即 $$SUM[i][j]=(i+1)(j+1)\sum_{x=1}^i\sum_{y=1}^jd[x][y]-(j+1)\sum_{x=1}^i\sum_{y=1}^jxd[x][y]-(i+1) \sum_{x=1}^i\sum_{y=1}^jyd[x][y]+\sum_{x=1}^i\sum_{y=1}^jxyd[x][y] $$。所以我们只需要在原来$C1[i][j]$记录$d[i][j]$的基础上，再开三个树状数组记录$d[i][j]*i,d[i][j]*j,d[i][j]*ij$即可。这样就可以通过数组$a[i][j]$的差分数组$d[i][j]$来得到$a[i][j]$的前缀和数组$SUM[i][j]$了。