去除数组内的空值_数据结构(1)——树状数组（原理与核心代码）

爱被打了一巴掌 2023-01-06 15:52 108阅读 0赞

**1.1. 背景**

对于某一个序列，假设我们有以下的两个需求

*  快速求前缀和
 *  修改某一个数

如果我们使用**普通数组**保存序列并实现上述两种操作，则时间复杂度分为别

![Image 1][] .

如果我们使用**前缀和数组**保存序列并实现上述两种操作，则时间复杂度分为为

![Image 1][] .

假设我们有

![Image 1][] 个操作，则最坏情况下的时间复杂度为

![Image 1][] 。那么，有没有一种可能使得时间复杂度为

![Image 1][] ，也就是两个操作的时间复杂度都是

![Image 1][] 呢。

树状数组便是支持上述两种操作，且时间复杂度为

![Image 1][] 的一种数据结构。

### 1.2.基本原理 ###

### 1.2.1.区间的二进制划分 ###

我们知道，一个正整数

![Image 1][] 可以二进制分解为：

![Image 1][] 其中，

![Image 1][] .

也就是说，一个正整数

![Image 1][] ，我们可以将其分解为

![Image 1][] 个数的和，每个数的大小分别为

![Image 1][] 。

**那么，对于一个给定的区间**

![Image 1][]

**，我们可以将其分解为**

![Image 1][]

**个区间。每个区间的大小分别为**

![Image 1][]

**.**

按照如下的方式来划分这

![Image 1][] 个区间。

![bbcfc7757e9de758affeb4673e360aa2.png][]

*  长度为
    
    ![Image 1][] 的区间为：
    
    ![Image 1][]
 *  长度为
    
    ![Image 1][] 的区间为：
    
    ![Image 1][]
 *  长度为
    
    ![Image 1][] 的区间为：
    
    ![Image 1][]

……

*  长度为
    
    ![Image 1][] 的区间为：
    
    ![Image 1][]
 *  长度为
    
    ![Image 1][] 的区间为：
    
    ![Image 1][]

> 举例来说：对于
> 
> ![Image 1][] ，其二进制表示为
> 
> ![Image 1][] .那么我们可以将区间
> 
> ![Image 1][] 划分为：
> 
> ![Image 1][] 。

接下来，我们观察一下上面划分的区间，可以得到两个非常有用的结论：

**结论1：对于每一个区间**

![Image 1][]

**，其长度都是:**

![Image 1][] .

**结论2：区间**

![Image 1][]

**的右端点值**

![Image 1][]

**与其下一个区间**

![Image 1][]

**右端点值**

![Image 1][]

**的关系为:**

![Image 1][]

因此，我们可以通过如下代码产生上述的各个区间：

for(int i = x; i ; i -= lowbit(i)) printf("[%d %d]n", i - lowbit(i) + 1, i);

### 1.2.2. 二进制划分下的前缀和 ###

在1.2.1中，我们将

![Image 1][] 划分为

![Image 1][] 个区间，每个区间可以表示为

![Image 1][] ，并且最后一个区间的范围是

![Image 1][] 。

假设，我们有数组

![Image 1][] ，我们建立另一个数组

![Image 1][] 。其中，

![Image 1][] 为序列

![Image 1][] 的下标为

![Image 1][] 范围内的元素和，即

![Image 1][] .

> 对
> 
> ![Image 1][] 的补充说明：通过公式我们可以看出，
> 
> ![Image 1][] 表示的是数组
> 
> ![Image 1][] 在1.2.1节中介绍的最后一个区间的和。而最后一个区间的长度为
> 
> ![Image 1][] 的
> 
> ![Image 1][] 值(注意，这个很重要，后面要用到)

这样我们便可以建立在学习树状数组时必会见到的图：

![b1c55046b8654ef576be876d586d4ab1.png][]

> ![Image 1][] 时，
> 
> ![Image 1][] , 所以
> 
> ![Image 1][]
> 
> ![Image 1][] 时，
> 
> ![Image 1][] ,所以
> 
> ![Image 1][]
> 
> ![Image 1][] 时，
> 
> ![Image 1][] ，所以
> 
> ![Image 1][]
> 
> ![Image 1][] 时，
> 
> ![Image 1][] ，所以
> 
> ![Image 1][]

接下来，我们分析一下各个

![Image 1][] 之间的关系。

**(1)父节点找子节点**

对于节点

![Image 1][] ，其值为

![Image 1][] 。

**我们来看**

![Image 1][]

**可以由哪些子结点来构成。**

首先，由于

![Image 1][] 中包含

![Image 1][] ，而

![Image 1][] 必然不在其前面的

![Image 1][] 节点中，所以我们可以首先剔除

![Image 1][] 。

这样我们要求的就是

![Image 1][] 可以通过哪些

![Image 1][] 来构成。

在1.2.1节我们介绍到，区间

![Image 1][] 可以表示为

![Image 1][] 个区间。而这里我们已经将原问题转化成了求数组

![Image 1][]在区间

![Image 1][] 的和。所以，我们就可以采用1.2.1中介绍的方法将其表示为$

![Image 1][] 个区间的和。

我们来观察

![Image 1][] ，其可以表示为如下的通用二进制表示形式

![aedbf2c57bc9a2ac9f32b1787040171a.png][]

那么，当我们对其减

![Image 1][] 后，就可以变为

![2e46ad3e270a116947d439c0582a7da6.png][]

再来审视1.2.1节中的区间划分方式，并将顺序颠倒来看。

*  长度为
    
    ![Image 1][] 的区间为：
    
    ![Image 1][]

……

令

![Image 1][]

第一个区间的右端点就是

![Image 1][] 本身，这里就是

![Image 1][] ，

第二个区间的右端点就是去除

![Image 1][] 的最右边

![Image 1][] 后的值，也就是

![Image 1][] ，这里就是

![Image 1][]

第三个区间的右端点就是去除

![Image 1][] 的最右边

![Image 1][] 后的值，也就是

![Image 1][] ，这里就是

![Image 1][]

这样的话，对于

![Image 1][] ，我们只需要

![Image 1][] 个子节点就可以表示它。

**(2)子节点找父节点**

上面通过父节点找到了子节点。而我们实际在使用的时候是使用子节点来更新父节点。

对于

![Image 1][] ,如果我们修改了它的值，那么它直接影响到的数是什么呢。

在父节点找子节点的过程中，我们知道了对于

![Image 1][] ，其二进制表示为

![Image 1][] ，其直接子节点的形式都是

![Image 1][] 的形式。

那么，对于形如

![Image 1][] 形式的节点

![Image 1][] ，其直接父节点必然形如

![Image 1][] ，也就是

![Image 1][]

**那么，对于任意**

![Image 1][]

**，其直接父节点必然有且仅有一个：**

![Image 1][]

**，这样我们就可以通过迭代的方式找到**

![Image 1][]

**的所有父节点**

### 1.3. 树状数组的核心代码 ###

### 1.3.1. 修改 ###

当我们修改数组

![Image 1][] 的某个节点值后，通过1.2.2中的方式迭代更新其唯一的直接父节点。

void add(int x)
    {
         
        for(int i = x; i <= n; i += lowbit(i)) c[i] += change_value;
    }

### 1.3.2 查询 ###

查询就是求

![Image 1][] 的前缀和，根据1.1.1节的区间划分，很容易写出：

int sum(int x)
    {
         
        for(int i = x; i; i -= lowbit(i)) sum += c[i];  
    }

### 1.3.3 初始化 ###

初始化的过程就是根据原数组构建

![Image 1][] 数组的过程。

*  ![Image 1][]

// 递归更新本身及其父节点
    for(int i = 1; i <= n; i ++) add(i, a[i]);

*  ![Image 1][]

//方法1：
    //第一步：先求前缀和
    for(int i = 1; i <= n; i ++)
    {
         
        scanf("%d", &a[i]);
        a[i] += a[i - 1];
    }
    //第二步：根据定义求解
    for(int i = 1; i <= n; i ++) c[i] = a[i] - a[i - lowbit(i)];  
    
    //方法2：nlgn的方式是添加一个数，之后递归的更新它的直接父节点；
    // 这里的方法是采用的是当我们扫描到第i个点时，看tr[i]是由那些节点构成的。也就是在1.1.1节所述的方法。
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    for(int x = 1; x <= n; x ++)
    {
         
        c[x] += a[x];
        for(int i = x - 1; i >= x - lowbit(x) + 1; i -= lowbit(i))
            c[x] += c[i];           
    }

[Image 1]: 
[bbcfc7757e9de758affeb4673e360aa2.png]: /images/20221119/05c14b1e0f044013999a03888fa0720e.png
[b1c55046b8654ef576be876d586d4ab1.png]: https://img-blog.csdnimg.cn/img_convert/b1c55046b8654ef576be876d586d4ab1.png
[aedbf2c57bc9a2ac9f32b1787040171a.png]: https://img-blog.csdnimg.cn/img_convert/aedbf2c57bc9a2ac9f32b1787040171a.png
[2e46ad3e270a116947d439c0582a7da6.png]: https://img-blog.csdnimg.cn/img_convert/2e46ad3e270a116947d439c0582a7da6.png