【BIT：树状数组】未成年香蕉也能简单上手的数据结构
初印象
BIT 是 Binary Indexed Tree（树状数组）的缩写。它也叫 Fenwick树（费尼克树）。
是一种用于高效处理数组前缀和（或类似运算）以及单点更新的数据结构。
写在前面很重要的话：
初始数组要从 1 开始存储数据。
bit数组也要从 1 开始，bit[0]是没有意义的
bit初始化时，一定要把所有初始值set为0，后续在update数据
文章目的是让下里巴人也能看懂阳春白雪（这句话来自我最喜欢的《算法竞赛》）
初学有段时间把他和线段树和ST表有些搞混，后面会有详细的比较内容。
树状数组的原理和数学分析
这一段是我最难理解的部分，直接321上例图。
例：对于用户来说，如果要找到从1到n的sum值，我们可以把n转化为二进制数，例如：4 - 0100 ； 7 - 0111
求1到7的sum，可以看作【1-4】+【5-6】+【7】 即图中bit[4] + bit[6] + bit[7]
树状数组正是利用了n可以拆解为二进制，将每个前2n项作为一个集合；在剩下的项中重复再将每2n项作为一个集合重复这样一个操作，使得前缀和操作的时间复杂度变为logn。
lowbit(x)
这是树状数组精妙的一环，通过补码来完成最低位的 1 所对应的数值。
例：lowbit(12)，二进制 1100，最低位1对应右数第三位代表的是 4，所以返回 4。
def lowbit(self, x):
return x & -x预备知识：计算机如何表示负数
在计算机中，负数通常用补码表示：
正数的补码 = 原码
负数的补码 = 原码按位取反 + 1
通过数学推导，容易推导出 x & -x 返回最低1所对应位置的数值。
最关键一步之：i+=lowbit（i）
那么这个lowbit的有什么用呢，结论是：找到对于bit[index]改变之后，收到影响的最近的index。
i += self.lowbit(i)
如果一个区间的小区间的sum加了delta，那么包含小区间的大区间一定也会加上delta。
例如：a[4]的值改变 那么bit数组中，由sum【1，4】组成的bit[4]会改变；从而推导出sum【1，8】和bit[8]也一定会改变。
若a[5]改变，最直接导致bit[5]改变；推导出 bit[6]改变；接着是bit[8] 也会改变。
因此，只需要找出对于一个小区间来说，利用index+=lowbit(index)最近的大哥区间就行了。
（os：大哥区间是我自己取的名字，意会便可）
简单的数学论证：
对于index=2n，下一个会产生影响的必定是2n+1位，而lowbit(index)得到的正是2n；
对于不到2n的项，可以将其二进制后左边的项先不看，看作1[n个0]+情况，由于树状数组定义，与前面同理。
update (index, delta)
update函数用来更新bit数组中的数据，那么有哪些数据需要被更新呢？
由前面的推断可得，只要改变受影响数组即可，代码如下：
def update(self, index, delta):
i = index
while i <= self.n:
self.tree[i] += delta
i += self.lowbit(i)query(self, index)
query是查询原始数字a数组中从1到index的总和，因此只需要一步步把bit数组中，对应答案的总和加起来即可。
不难发现，对于一个index，while循环的次数是其二进制下1的个数，这正是树状数组的优秀之处。
def query(self, index):
res = 0
i = index
while i > 0:
res += self.tree[i]
i -= self.lowbit(i)
return res复杂度
更新单点数据：logN
查询单点数据：logN
查询区间总和：logN
空间复杂度：N
#N为BIT数组长度，其优秀的性质关键在于 查询1~N前缀和的时间复杂度logN。
关于树状数组能实现的题目共性
例题有：P5200 [USACO19JAN] Sleepy Cow Sorting G - 洛谷
P3660 [USACO17FEB] Why Did the Cow Cross the Road III G - 洛谷
先叠甲：上两题不只是有树状数组的做法，但是再知道用树状数组的前提下，本蒟蒻竟然也是能在60min内AC这两道的，足以证明对于辨别出算法熟练度的掌握和对算法的选择对写题很有讲究。
最开始思维比较固化，认为树状数组的快速前缀和似乎只能解决这种单点改变，求区间和的问题，线段树算法都可以很好的解决动态数组区间求和问题，没有树状数组啥事情，但是树状数组写起来简单啊！！
其实作为初学者，通过树状数组的练习来锻炼这个对题目分析和抽象能力还是值得一试的。
树状数组对于前缀和的运算之外，有的时候是一个计数的作用。（delta设置为1）
当某个数m加入，此时比m小的数已经出现过的次数可以马上得出，这是一个和插队，逆序对(P6278)等等有关的问题。
本人的理解：在解决，一个一个数字插入数列，统计逆序对总和，这个问题上展现出巨大优势。
和线段树的对比
省流：线段树更牛逼
树状数组的优势：
代码简单，十几行和几十行，还是分得清的。
实际运行起来，线段树是递归和树状数组是循环，运行效率更高。
空间复杂度为O(n)；线段树为O(4n)；
劣势：
功能方面，区间修改能力弱，需要nlogn，而线段树是logn；
树状数组有的功能线段树都有；
无法实现 区间最值问题。（因为树状数组的底层逻辑是求和）
和ST表的联系
因为我对ST表好感度很高，所以来对比一下，其实没什么可比性，二者相差内容很多。
ST表处理静态问题，区间运算很好用。不适用于需要修改单点值的算法。
只不过二者对于二进制的处理有些相像之处，都是将数拆分成其二进制，区间之和，思想过程有相似之处。
代码实现
class BIT:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def lowbit(self, x):
return x & -x
def update(self, index, delta):
i = index
while i <= self.n:
self.tree[i] += delta
i += self.lowbit(i)
def query(self, index):
res = 0
i = index
while i > 0:
res += self.tree[i]
i -= self.lowbit(i)
return res
def rangesum(self, left, right):
return self.query(right) - self.query(left)上下分别为BIT模板代码的py和cpp实现
#include <iostream>
#include<vector>
using namespace std;
typedef long long ll;
class BIT {
private:
vector<ll> tree;
int n;
int lowbit(int x) {
return x & -x;
}
public:
BIT(int size) : n(size) {
tree.resize(n+1, 0);
}
void update(int idx, int val) {
while (idx <= n) {
tree[idx] += val;
idx += lowbit(idx);
}
}
ll query(int idx) {
ll sum = 0;
while (idx > 0) {
sum += tree[idx];
idx -= lowbit(idx);
}
return sum;
}
ll rangeQuery(int l, int r) {
return query(r) - query(l - 1);
}
};下为洛谷P5200 题解
import sys
N = int(input())
class BIT:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def lowbit(self, x):
return x & -x
def update(self, index, delta):
i = index
while i <= self.n:
self.tree[i] += delta
i += self.lowbit(i)
def query(self, index):
res = 0
i = index
while i > 0:
res += self.tree[i]
i -= self.lowbit(i)
return res
def get(self,x):
return self.query(x) - self.query(x-1)
def rangesum(self, left, right):
return self.query(right) - self.query(left)
cow =list( map(int, sys.stdin.readline().split()))
tmp = N-1
while cow[tmp]>cow[tmp-1] and tmp>0:
tmp -= 1
cow_left = cow[0:tmp]
cow_right = cow[tmp::]
step = N - len(cow_right)
bit = BIT(N)
ans=[]
for x in cow_right:
bit.update(x, 1)
lengh = len(cow_left)
for i in range(lengh):
tmp = 0 + lengh - i - 1 + bit.query(cow_left[i])
bit.update(cow_left[i],1)
ans.append(tmp)
print(step)
ans = list(map(str, ans))
print(' '.join(ans))
下为洛谷p3660题解
class BIT:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def lowbit(self, x):
return x & -x
def update(self, index, delta):
i = index
while i <= self.n:
self.tree[i] += delta
i += self.lowbit(i)
def query(self, index):
res = 0
i = index
while i > 0:
res += self.tree[i]
i -= self.lowbit(i)
return res
def get(self,x):
return self.query(x) - self.query(x-1)
def rangesum(self, left, right):
return self.query(right) - self.query(left)
N = int(input())
flags = [-1] * (N+1)
bit = BIT(2*N)
ans = 0
for i in range(1,1+2*N):
bit.update(i, 1)
x= int(input())
if flags[x] == -1:
flags[x] = i
else:
bit.update(flags[x],-1)
bit.update(i,-1)
ans += bit.rangesum(flags[x], i)
# print(bit.get(flags[x]),bit.get(i))
print(ans)后记！！
终于写完了！！！！！！！开心！！！！！
最开始学BIT的时候就有写博客的冲动，在一边写的过程中我也是终于把原理搞懂了！！！好开心！！！！啊啊啊！！！
里面有很多我的思考痕迹和我自己独有的思考模式，想讲的内容很多，还是尽全力表达出来了！！
前前后后写了三四个小时，在车上一直在写，白天也一直在写我都要哭了，拖了两个星期，在这两天写出来了好有成就感五五五五。
感谢所有人！！！！我喜欢写后记!写后记的时候终于可以开香槟了！
此乃一稿，我还会润色！
使用了draw.io这个网站画图！我觉得很好用！
下次我会讲笛卡尔树！
感谢看到这里！kiss!!!
二编：
我发现我的字太大了。手机上看好大一片的。
评论