Binary Indexed Array

Posted on In

Definition

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

  1. update(index, delta): 将delta加到index位置上。
  2. prefixSum(index): 求 sum[1, index]的值。
  3. rangeSum(from, to): 求 sum[from, to] 的值。

时间复杂度：

  1. update(index, delta): 更新需要循环更新每一个parent的值，从index开始到最后一个parent。复杂度为O(n)。
  2. prefixSum(index): 直接返回sum[index + 1]即可，复杂度为O(1)。
  3. rangeSum(from, to): 直接返回sum[to + 1] - sum[from]即可，复杂度为O(1)。

Build

现在有个nums初始数组，通过这个数组构造一个BITArray。
构造Binary Indexed Array。

  1. 实现insert(index, delta):
1
2
3
4
5
6
function insert(index, delta) {
  while (index < this.BITArray.length) {
    this.BITArray[index] += delta
    index += index & -index // BIT中，parent的index计算方法为：parent = child + (child & -child)
  }
}
  1. 构造 BITArray:
1
2
3
4
5
6
function MyArray(nums) {
  this.BITArray = new Array(nums.length + 1).fill(0)
  for (let i = 0, len = nums.length; i < len; i++) {
    this.insert(i + 1, nums[i]) // 在每个index处循环插入，delta就是初始值。
  }
}
  1. 实现sum(index):
1
2
3
4
5
6
7
8
9
function sum(index) {
  let sum = 0
  while (index > 0) {
    sum += this.BITArray[index]
    index -= index & -index // BIT中，child的计算方法为：child = parent - (parent & -parent)
  }

  return sum
}
  1. 实现perfixSum(from, to)
1
2
3
function perfixSum(from, to) {
  return this.sum(to + 1) - this.sum(from)
}