【算法与数据结构】——树状数组

╰+攻爆jí腚メ 2022-11-09 11:19 220阅读 0赞

## 例题 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70]

如例题,类似于序列求和的问题,一般用前缀和解决,但是此题目中的数列的值是不断变动的,使用前缀和,时间复杂度更大.由此,我们引入树状数组的概念.

树状数组

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 1]

(A数组是原数组)

## 树状数组的规律: ##

c\[i\]包含的项数是i转化为2进制后,最右边一个1表示的值,比如i为6时转换为二进制110,最右边一个1表示的是2则c\[i\]表示两个连续的序列,a\[i\]和a\[i-1\]的和

由此可见,要知道C\[i\]是A\[i\]的哪几项和,关键是知道最低位的1代表的值.有两种方法

### 方法一: ###

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

### 方法二: ###

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

## 构造树状数组 ##

树状数组的构造其实就是更新操作,在后面对树状数组进行单点更新的过程就是构建c\[i\]树状数组的过程.

## 通过树状数组求前缀和 ##

我们要求前i项和(sum(i)),求和公式中必然有c\[i\] 例如:求sum(7),  
求和公式中必有c\[7\],因为c\[7\]只包含a\[7\],于是我们需要求前6项和,公式中需要有c\[6\],c\[6\]是包含a\[6\]和a\[5\]的,所以还需要加上前4项的和,再加上c\[4\],c\[4\]就包含了前面4项的和,于是有sum(7) = c\[7\]+c\[6\]+c\[4\];  
将sum(7)写成二进制形式就是sum(111)=c\[100\]+c\[110\]+c\[111\],i表示成二进制后,其中含有几个1,前i项和就由几个数相加,因此此算法的最差时间复杂度是log(n)

int sum(int i)	//求区间[1,i]所有元素的和
    { int ret = 0;
     while(i>0){
     ret+=c[i];			//从右往左区间求和
     i-=lowbit(i);
     }
     return ret;
    }

## 在生成树状数组的前提下求前缀和 ##

有了树状数组,这个问题就很简单了,只要让sum(L)-sum(L-1)即可.

## 单点更新 ##

树状数组更新时的效率就比最原始的前缀和序列快多了,更新a\[i\]只需要更新包含a\[i\]的数据即可,易知时间复杂度为log(n),代码如下:

void update(int i,int val)
    { while(i<=n)
    {c[i]+=val;
    i+=lowbit(i);  //由叶子节点向上更新c数组
    }
    }

## 经典应用 ##

求逆序对数  
给定n(<=100000)个正整数,希望对其从小到大排序,如果采用冒泡排序算法,计算需要进行的交换次数.  
**基本思想:**  
开一个数组c\[n+1\],初始化为0,记录前面数据的出现情况;当数据a出现的时候,就令c\[a\]=1.这样的话,若求a的逆序数,只需要算出在当前状态下c\[a+1,n\]中有多少个1,因为这些位置的数在a之前出现且比a大.  
如果不用树状数组的话每次添加一个数都要重新全部计算,复杂度将会很大O(n^2)

## 例题二![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 2] ##

这道题目的特点跟树状数组能解决的单点更新,区间查询类的问题有些不同,这道题目的特点是区间更新,单点查询,用树状数组很难解决这个问题了,由此引入差分数组的概念

## 解题的基本思路 ##

通过"差分"的方法(数组中记录的是每个元素和前一个元素的差),这样就把问题转化为常规树状数组了,只需要对于差分数组求前缀和,就能实现单点查询.

## 区间修改,区间查询类型. ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 3]  
对计算式做如下转换(其中d\[i\]表示差分数组,a\[i\]表示原数组)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 4]  
这样最后转换成了两个数组的前缀和,由此我们只需要结合树状数组的求前缀和的方法,根据转化后的公式构建树状数组求前缀和即可

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70]: /images/20221023/7ce5dfc66bf0484b81db0b179819bfd5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 1]: /images/20221023/640145f7ea8041d2bb9feb46d3b2a73b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 2]: /images/20221023/60d8354689004091a4e5934a964dbbae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 3]: /images/20221023/20f884deb9d44fa09679b57a2e746a97.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 4]: /images/20221023/b5cd3e9767ed4cdd9d430ea80084dae0.png