A Quick Note of Binary Index Tree

What is it

  • A binary index tree, also known as a tree array, also known as Fenwick Tree, is still essentially an array that implements O(logn) time complex range queries and updates. It can be interpreted as better than segment tree in specific cases.

What problem is solved (application scenario)

  • Just like the emergence of the segment tree, a data structure emerged to solve recurring range queries and updates. There is a certain efficiency gain compared to using prefix sums (O(n) updates and queries).

  • The advantage is that it's faster in time, the disadvantage is that it's a little hard to understand.

Key points

lowbit

Define a function lowbit that finds the number of bits that a number goes through when it starts counting from the far right until it meets 1. This can be achieved in the code by bitwise operations

public int lowbit(int val) {
    return val*(-val);
}
  • The bull's-eye is coming.

                                     lowbit
    
                    o                ├ 1000 = 8
            ┌───────┴───────┐        │
            o               o        ├ 100  = 4
        ┌───┴───┐       ┌───┴───┐    │
        o       o       o       o    ├ 10   = 2
      ┌─┴─┐   ┌─┴─┐   ┌─┴─┐   ┌─┴─┐  │
      o   o   o   o   o   o   o   o  ├ 1    = 1
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5  │
    
    

We can see patterns here, same level nodes have same ending.

  • And when a node n is a right child, n - lowbit(n) is its parent: for example 12, 12 - lowbit(12) = 12 - 4 = 8 is exactly the parent 8 of 12. And when a node is a left child, n - lowbit(n) is its grandfather: e.g. node 10, 10 - lowbit(10) = 10 - 2 = 8, is the left grandfather of 10.
  • When a node n is a right child, n + lowbit(n) is its grandfather node: for example, 6 + lowbit(6) = 6 + 2 = 8 corresponds to the right grandfather node of 6; when a node n is a left child, n + lowbit(n) is its parent, for example, node 4, 4 + lowbit(4) = 4 + 4 = 8 is the parent node of 4. is the parent node of 4.
  • You can also see that n - lowbit(n) + 1 corresponds to a node on a complete bifurcation, starting from the node corresponding to the number n and taking the left child of the node up to the node at the first level. For example, the node where 12 is located, keep taking the left child of the node, and you end up with 9, and 9 = 12 - 4 + 1 = 12 - lowbit(12) + 1.
  • With lowbit we can quickly locate in a complete binary tree.

Build the index

image-20230322163817560
                o
        ┌───────┴───────┐
        o               x
    ┌───┴───┐       ┌───┴───┐
    o       o       x       o
  ┌─┴─┐   ┌─┴─┐   ┌─┴─┐   ┌─┴─┐
  o   o   o   o   x   x   o   o
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
A:                2 1 3 1
BIT:                   (7)

You can see that 12 - lowbit(12) + 1 = 12-4+1=9, so BIT[12] = A[9] + A[10] + A[11] + A[12]. Similarly, to calculate BIT[8], we need to calculate A[1] + ... + A[8], since 8 - lowbit(8) + 1 = 1.

Principle and implementation

Summation

  • With BIT, if we solve for sum(k), we just need to sum k and the left grandfather/parent node of k. The complexity is O(logn).
  • Let's take 6 for example, BIT[6] is equivalent to A[5] + A[6], but we have to compute A[1] + ... + A[6], so also A[1] + ... + A[4], which in BIT corresponds exactly to BIT[4]. Taking 14 as another example, BIT[14] = A[13] + a[14], which is still short of A[1] + ... + A[12], so we find 14 - lowbit(14) = 14 - 2 = 12, and since BIT[12] = BIT[9] + ... + BIT[12], so it is still short of A[1] + ... + A[8], which exactly corresponds to BIT[8], and we have 12 - lowbit(12) = 12 - 4 = 8.

So the sum(k) operation is to find the sum of node k and its parent node.

Update nodes

  • From BIT's node-defining formula you can until that a certain value of the original array is updated, it affects all its right grandfather/parent nodes
  • This can be obtained by k + lowbit(k). For example A[9] has changed, and by definition we need to update BIT[9], BIT[10], BIT[12]. This update can be implemented by lowbit(n)+n with a time complexity of O(nlogn).

Initialization

  • With the help of the update operation, the update function is called to update each value. The complexity is O(nlogn).
import static org.junit.Assert.assertEquals;

/**
 * Created by szhang on 2023/3/20
 */
public class BinaryIndexedTree {
    int[] nums;
    int[] tree;

    public BinaryIndexedTree(int[] nums) {
        this.nums = nums;
        this.tree = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            update(i, nums[i]);
        }
    }

    public void update(int i, int val) {
        int diff = val - nums[i];
        nums[i] = val;
        for (int j = i + 1; j <= nums.length; j += j&(-j)) {
            tree[j] += diff;
        }
    }

    public int sumRange(int i, int j) {
        return sum(j+1) - sum(i);
    }

    private int sum(int k) {
        int sum = 0;
        for (int i = k; i > 0; i -= i*(-i)) { // i*(-i) is the lowbit function
            sum += tree[i];
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 4, 5, 6};
        BinaryIndexedTree bit = new BinaryIndexedTree(nums);
        assertEquals(10, bit.sumRange(0, 2));
        assertEquals(18, bit.sumRange(1, 4));
        assertEquals(21, bit.sumRange(0, 5));
        bit.update(2, 7);
        assertEquals(15, bit.sumRange(0, 2));
        assertEquals(24, bit.sumRange(1, 4));
        assertEquals(28, bit.sumRange(0, 5));
    }
}

Reference

binary index tree


是什么

  • 二叉索引树,也称树状数组,又称Fenwick Tree,本质上还是一个数组,实现了O(logn)时间复杂的的范围查询和更新。可以理解为特定情况下比segment tree好用。

解决了什么问题(应用场景)

  • 正如segment tree的出现类似,为了解决**经常性的范围查询和更新**,而出现的一种数据结构。相比于使用前缀和(O(n)的更新和查询),会有一定的效率提升。

  • 优点在于时间上更快了,缺点就是有一点点难以理解。

关键点

lowbit

定义一个函数lowbit,他求的一个数是从最右边开始数直到遇到1时候走过的位数。在代码中可以通过位运算来实现

public int lowbit(int val) {
    return val*(-val);
}
  • 牛逼的东西要来了:

                                     lowbit
    
                    o                ├ 1000 = 8
            ┌───────┴───────┐        │
            o               o        ├ 100  = 4
        ┌───┴───┐       ┌───┴───┐    │
        o       o       o       o    ├ 10   = 2
      ┌─┴─┐   ┌─┴─┐   ┌─┴─┐   ┌─┴─┐  │
      o   o   o   o   o   o   o   o  ├ 1    = 1
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5  │
    

    我们可以看到这个不同层数的二叉结尾是有规律的。

    • 而且当一个节点n是右孩子的时候,n - lowbit(n)是他的父节点: 例如 1212 - lowbit(12) = 12 - 4 = 8 正好是 12 的父节点 8。而当一个节点是左孩子的时候,n - lowbit(n)是他的祖父节点: 例如节点 1010 - lowbit(10) = 10 - 2 = 8,是 10 的左祖父节点。
    • 当一个节点n是右孩子的时候,n + lowbit(n)是他的祖父节点:例如 6 + lowbit(6) = 6 + 2 = 8 则对应于 6 的右祖父节点;当一个节点n是左孩子的时候, n+lowbit(n)是他的父节点,例如节点44 + lowbit(4) = 4 + 4 = 84 的父节点。
    • 同时可以看到 n - lowbit(n) + 1 在完全二叉数上对应的节点,就是从数字 n 对应的节点开始,不断取节点的左子节点直到第一层的那个节点。例如 12 所在的结点,不断取左子节点,最终得到的是 9,而 9 = 12 - 4 + 1 = 12 - lowbit(12) + 1
    • 有了lowbit我们就可以在完全二叉树中快速定位。

建立索引

image-20230322163817560
                o
        ┌───────┴───────┐
        o               x
    ┌───┴───┐       ┌───┴───┐
    o       o       x       o
  ┌─┴─┐   ┌─┴─┐   ┌─┴─┐   ┌─┴─┐
  o   o   o   o   x   x   o   o
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
A:                2 1 3 1
BIT:                   (7)

可以看到 12 - lowbit(12) + 1 = 12-4+1=9,因此 BIT[12] = A[9] + A[10] + A[11] + A[12]。同理,如果要计算 BIT[8],则需要计算 A[1] + ... + A[8],因为 8 - lowbit(8) + 1 = 1

原理和实现

求和

  • 有了BIT之后,如果求sum(k),我们只需要将k和k的左祖父/父节点相加即可。复杂度是O(logn)。
  • 我们以 6 为例,BIT[6] 相当于 A[5] + A[6],但我们要计算 A[1] + ... + A[6],因此还要计算 A[1] + ... + A[4],而在 BIT 中,这正好对应于 BIT[4]。再以 14 为例,BIT[14] = A[13] + a[14],还差 A[1] + ... + A[12],于是找到 14 - lowbit(14) = 14 - 2 = 12,而由于 BIT[12] = BIT[9] + ... + BIT[12],因此还差 A[1] + ... + A[8],正好对应于 BIT[8],而又有 12 - lowbit(12) = 12 - 4 = 8

所以说 sum(k) 操作就是求节点 k 及它的父节点的和。

更新节点

  • 从BIT的节点定义公式可以直到,原数组某个数值更新,会影响其所有的右祖父/父节点
  • 这可以通过 k + lowbit(k) 来得到。例如 A[9] 发生了变化,根据定义,我们需要更新 BIT[9], BIT[10], BIT[12]。这个更新的过程可以通过lowbit(n)+n来实现,时间复杂度为O(nlogn)。

初始化

  • 借助update操作,调用update函数更新每个数值。复杂度为 O(nlogn)。
import static org.junit.Assert.assertEquals;

/**
 * Created by szhang on 2023/3/20
 */
public class BinaryIndexedTree {
    int[] nums;
    int[] tree;

    public BinaryIndexedTree(int[] nums) {
        this.nums = nums;
        this.tree = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            update(i, nums[i]);
        }
    }

    public void update(int i, int val) {
        int diff = val - nums[i];
        nums[i] = val;
        for (int j = i + 1; j <= nums.length; j += j&(-j)) {
            tree[j] += diff;
        }
    }

    public int sumRange(int i, int j) {
        return sum(j+1) - sum(i);
    }

    private int sum(int k) {
        int sum = 0;
        for (int i = k; i > 0; i -= i*(-i)) { // i*(-i) is the lowbit function
            sum += tree[i];
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 4, 5, 6};
        BinaryIndexedTree bit = new BinaryIndexedTree(nums);
        assertEquals(10, bit.sumRange(0, 2));
        assertEquals(18, bit.sumRange(1, 4));
        assertEquals(21, bit.sumRange(0, 5));
        bit.update(2, 7);
        assertEquals(15, bit.sumRange(0, 2));
        assertEquals(24, bit.sumRange(1, 4));
        assertEquals(28, bit.sumRange(0, 5));
    }
}

参考

二叉索引树