Binary Index Tree

中文名叫做树状数组

• During a lookup(sum), we just care about the right links we follow.(所以要把二进制的1从右往左递减)

• During an update, we just care about the left links we follow（从左到右）.

• This binary indexed tree does all of this super efficiently by just using the bits in the index.

  Build O(NLogN)

  Query O(LogN)

  Query O(LogN)

• 跟线段树比起来缺点是建树时间长过Segment Tree,只能Query Sum(0,k),不能求Range Min/Max Query, 并且讲解起来太麻烦

• 优点是代码容易实现，可以扩展到多维

视频讲解，很清楚

• Sum: compute a prefix sum array

• Add: add an value to an element

  

Binary Index Tree的核心思想是每个树都可能拆成N个2的次方数的和的形式来表示 假设给定一个n= 14的数组，分别算出[2^0, 2^0]，［2^0, 2^1］,[2^0, 2^2][2^0, 2^3]……的prefix sum

• 这样也就得到[1,1][1,2][1,4][1,8][3,3][5,5][5,6][7,7]区间的sum

• 可以发现第3个位置只须存[3,3]的sum

• 比如现在要求 sum(13),可以先求sum(13,13), 再求sum(9,12), 再求(1,8)

• 如何从sum(13,13)到sum(9,12)呢？可以往上往左

  

• 这里的求和的思想就是把idx的二进制表示的每一个"1"位上存的数都加起来，比如idx = 13,就是1101, sum(0,13) = arr[1101] + arr[1100] + arr[1000]

• arr[1101]表示的就是sum(13,13)

• arr[1100]表示的是sum(8,12)

• arr[1000]表示的是sum(0,8)

  

  实现

  

  注意事项

• 建立的BIT array是1-based index

• 原先的array还是0-based

• range_sum(start, end) = range_sum(end) - range_sum(start - 1)

• 还可以用树状数组实现product,XOR

• 但是不能实现RMQ!!!!最大的局限性