Definition:
A binary indexed tree or a Fenwick tree can be seen as a dynamic variant of a prefix sum array [1]. The goal of the data structure is to support two O(logn) time operations on an array: processing a range sum query and updating a value in the array.
Properties:
- Even the name of this data structure is called binary index tree, it’s usually represented as an array with one-indexed for ease of implementation, when it comes to implementing.
- In binary index tree, for query and update operation, we at most traverse log(n) nodes. So, running time is O(log n).
- The advantage of a binary indexed tree is that it allows us to efficiently update array values and calculate range sum queries from index i to index j in O(log n).
Application:
- range sum query for mutable array: to calculate sum based on a subarray of array.
- count smaller element to the right or left of current element with help of rank hashmap, given an input array with fixed size.
Note:
Why we need binary index tree [2]? If the array is immutable, we can efficiently have range sum query in O(1) time with help of extra prefix sum array (please see leetcode 303). However, when the value in the array is mutable, means there’re frequent update operations, which incurs one of updates or range sum query operation becomes O(n) (please see leetcode 307 for details about thought process.
In short, the purpose of BIT is to solve range sum queries with many updates.
Details about implementing Binary Index Tree:
- Each integer could be represented as a sum of powers of two (bit representation), using the below formula.
2. lowbit(x) is to find the largest power of 2 that divides into x. Symbolically, find largest 2**(n) such that x / 2**(n) = 0, remainder is 0. [3]
For example, x = 48 → 48/16(²⁴) =3… 0 → lowbit(48) = 16(²⁴)
For example, x = 5 → 5/²⁰ = 5…0 → lowbit(5) = 1(²⁰)
Using bit manipulation, lowbit(x) = x & (-x) = x & ~(x-1) because of formula : ~x = -x-1 => ~(x-1) = -x
For example, x = 5→0101 => lowbit(5) = 0101 & ~(0100) = 0101 &1011 = 0001 = 1
3. Store partial sum in each node traversing from the leaf to its root node. Similarly, get total sum by traversing the tree from leaf to to its root node. However, the two operations follow different path, which rule is determined by lowbit function.
3.The purpose of lowbit function is like distributed system to distribute the information we need into different node in order to speed up query and update operations.
The below problems related to Union-Find in leetcode:
Reference:
[1]. Chapter 9, The algorithm design manual, 2nd edition
[2].https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
[3].https://www.geeksforgeeks.org/highest-power-of-two-that-divides-a-given-number/?ref=rp
