Binary-Indexed-Tree

1. 简介

定义问题如下：我们有n个盒子，可能的操作为：

1. 往第i个盒子增加石子(对应下文的update函数)

2. 计算第k个盒子到第l个盒子的石子数量(包含第k个和第l个)

原始的解决方案中(即用普通的数组进行存储，box[i]存储第i个盒子装的石子数)， 操作1和操作2的时间复杂度分别是O(1)和O(n)。假如我们进行m次操作，最坏情况下， 即全为第2种操作，时间复杂度为O(n*m)。使用某些数据结构(如

RMQ

) ，最坏情况下的时间复杂度仅为O(m log n)，比使用普通数组为快许多。 另一种方法是使用数状数组，它在最坏情况下的时间复杂度也为O(m log n)，但比起RMQ， 它更容易编程实现，并且所需内存空间更少。

2. 符号定义

• BIT: 树状数组

• MaxVal: 具有非0频率值的数组最大索引，其实就是问题规模或数组大小n

• f[i]: index为i的频率值，即原始数组中第i个值。i=1…MaxVal

• c[i]: index为i的累积频率值，c[i]=f[1]+f[2]+…+f[I]

• tree[i]: index为i的BIT值(下文会介绍它的定义)

• num^- : 整数num的补，即在num的二进制表示中，0换为1，1换成0。如：num=10101，则 num^- =01010

注意

: 一般情况下，我们令f[0]=c[0]=tree[0]=0，所以各数组的索引都从１开始。 这样会给编程带来许多方便。

3. 基本思想

1.png

2.png

1. a get parent(for sum)
   求a的补码b
   i-=(i&-i)

2. a get next(for update)
   求a的补码b
   i+=(i&-i)