Binary indexed tree (Fenwick tree)

  本文主要介绍Binary indexed tree (Fenwick tree),也叫树状数组

核心思想

  • 数组中每一个元素都是原数组中一个或多个连续元素之和;
  • 连续求和a[0]+a[1]+…+a[n]时,只需要树状数组几个元素之和,时间复杂度为O(logn);
  • 更改原数组某一元素值,只需要更改几个树状数组元素,时间复杂度为O(logn)。

  下图,是树状数组的示意图:

lowbit(x)函数

  定义lowbit(x)为x的二进制形式最右边1所对应的值。
  如,6的二进制是110 lowbit(6)=2。

前继

  上图中,e[3]的前继是e[2],e[6]的前继是e[4],即结点e[i]的前继为e[i-lowbit(i)]。

后继

  e[2]的后继是e[4],e[6]的后继是e[8],即结点e[i]的后继为e[i+lowbit(i)]。

  由示意图可看出,e[i]是原数组第i-lowbit(i)+1到第i项的和,计算原数组sum[6]=e[6]+e[4],更改a[1],只需要更新e[1],e[2],e[4]……直到最大值。

  Python实现树状数组代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class FenwickTree(object):
def __init__(self, n):
self.n = n
self.sums = [0] * (n + 1)
#更新元素
def add(self, x, val):
while x <= self.n:
self.sums[x] += val
x += self.lowbit(x)
def lowbit(self, x):
return x & -x #计算机内部-x是将x按位取反,再加1
#计算原数组a[0]+a[1]+…+a[x]
def sum(self, x):
res = 0
while x > 0:
res += self.sums[x]
x -= self.lowbit(x)
return res

用途

  求一个整数数组nums的逆序对数时,可以运用树状数组实现,时间复杂度降到O(nlogn)。

思路:

  1. 首先对nums去重,确定每一个元素具体排位;
  2. 从右向左,统计小于每个排位的元素个数,并将这一排位加入到树状数组。

  具体实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def countSmaller(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
#去重+排序
insort={}
for k,v in enumerate(sorted(set(nums))):
insort[v]=k+1
snums = [insort[x] for x in nums]
result = [0]*len(nums)
ft = FenwickTree(len(nums))
for i in range(len(snums)-1,-1,-1):
result[i]=ft.sum(snums[i]-1) #求出第snums[i]排位的逆序数
ft.add(snums[i],1) #将其加入树状数组
return result

分享