数据结构 (一): 树状数组 / 二叉索引树 / BIT

曾经终败给现在 2022-02-04 04:53 225阅读 0赞

### 树状数组 ###

*  简介
 *  lowbit
 *  BIT 的组织方式
 *  代码 ( C 语言 )
 *   *  注意事项
 *  总结

# 简介 #

树状数组的学名是二叉索引树, Binary Indexed Tree, BIT, 下文以 BIT 简称.  
BIT 是一种特殊组织过的数组, 它和普通数组的**唯一区别是**:  
BIT 的核心任务是快速求区间和, 而数组的核心任务是**随机存取**, 因此, 二者在只是时间复杂度上有所不同:

由此可见, 在单点存取时普通数组是最快的 (没人比它更快), 而对于区间的求和操作, BIT 有很大的优势.

# lowbit #

一个数字的 lowbit 是它二进制数最右边1的值, 比如  
 l o w b i t ( 3 ) = l o w b i t ( 11 ) = 1 = 1 lowbit(3) = lowbit(11) = 1 = 1 lowbit(3)=lowbit(11)=1=1  
 l o w b i t ( 6 ) = l o w b i t ( 110 ) = 10 = 2 lowbit(6) = lowbit(110) = 10 = 2 lowbit(6)=lowbit(110)=10=2  
 l o w b i t ( 12 ) = l o w b i t ( 1100 ) = 100 = 4 lowbit(12) = lowbit(1100) = 100 = 4 lowbit(12)=lowbit(1100)=100=4  
我们观察一下  1 , 2 , . . . , 10 \{1, 2, ..., 10\} 1,2,...,10 的 lowbit 的值:  
 l o w b i t ( 1 , 2 , . . . , 10 ) = \{ 1 , 2 , 1 , 4 , 1 , 2 , 1 , 8 , 1 , 2 \} lowbit(1, 2, ... , 10) = \\\{1, 2, 1, 4, 1, 2, 1, 8, 1, 2\\\} lowbit(1,2,...,10)=\{ 1,2,1,4,1,2,1,8,1,2\}  
发现了没, 这个 lowbit 序列包含了一种二叉树的结构, lowbit 相同的位置都处在同一层. 这样我们就可以根据一个位置的 lowbit 得到它在二叉树的层级信息.

获取一个数字 lowbit 的公式:

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

# BIT 的组织方式 #

普通数组每个位置的值就是这个位置元素的值, 而 BIT 不一样, 它每个位置的值是一个区间和, 组织方式如下:  
![0069McTXly1g2rz1mp35qj30hq070dfv.jpg][]  
也就说, 一个节点的值是**它和它所有左孩子的和**  
从这样的组织方式我们可以看出:

1.  一个元素的值被包含在它和它所有的右父亲中
2.  以一个元素为结尾的前缀和是它所有左父亲的和 (比如前缀和 a\[0:7\] 的值等于a\[7\] + a\[6\] + a\[4\], 如图所示)

显然, 更新一个元素的值和区间求和的复杂度都是  O ( l o g N ) O(logN) O(logN), 因为都要对它一半的父亲操作.

# 代码 ( C 语言 ) #

#include <stdio.h>
 #include <string.h>
 
 #define MAXN 1000
 int bit[MAXN];
 
 int lowbit(int x) { return x&-x;}
 void init() { memset(bit, 0, sizeof(bit));}
 
 // 修改单个位置的值
 void add(int pos, int val) { 
 	while (pos < MAXN) { 
 		bit[pos] += val;
 		pos += lowbit(pos);
 	}
 }
 // 返回前缀和, 即 sum(a[0:pos])
 int prefixSum(int pos) { 
 	int sum = 0;
 	while (pos > 0) { 
 		sum += bit[pos];
 		pos -= lowbit(pos);
 	}
 	return sum;
 }
 // 返回区间和, 即 sum(a[from:to])
 int rangeSum(int from, int to) { 
 	return prefixSum(to) - prefixSum(from-1);
 }

## 注意事项 ##

BIT 的第一个元素应该是下标 1 开始的, 因为 0 没有 lowbit, 因为 0 的二进制里没有 1.

# 总结 #

学!

[0069McTXly1g2rz1mp35qj30hq070dfv.jpg]: /images/20220204/82de07dae1fa41969f2a39e2493061ba.png