Data Structure: Binary Index Tree - cocoder39/coco39_LC GitHub Wiki

Notes 2020:

binary index tree: a implicit data structure implemented via a flat array

1. why idx -= (idx & -idx) for query and idx += (idx & -idx) for update

• QUERY: for prefix_sum, each node (eg, index i) represents range sum from [0:i]. For binary index tree, each node (eg, index i) represents range sum [j:i] where j may not be 0. EG, To query sum from [0:1101b] we need to sum up (binaryIndexTree[1101b], binaryIndexTree[1100b], binaryIndexTree[1000b]) where binaryIndexTree[1000b] is sum of range [1:8], binaryIndexTree[1100b] is sum of range [9:12], and binaryIndexTree[1101b] is [13]
• UPDATE: in order to update value at index 1b, we will need to update binaryIndexTree[1b], binaryIndexTree[10b], binaryIndexTree[100b] and so on because binaryIndexTree[10b] represents range sum [1:2] and binaryIndexTree[100b] represents range sum [1:4]. So if there is an update at index 1 we need to also update other related indexes

2. index 0 is skipped

reference:

• data structure explanation
• virtualization

======================================================================================================

Given an array a[]. Considering two methods: add(arr[i], n) which increases a[i] by n, and query(L, R) which returns the cumulative value of arr[L] + arr[L + 1] + .. arr[R].

Consider following queries:

add(arr[5], 7);
query();
add(arr[6], 8);
query();

it it easy to implement add() with O(1) complexity, but the complexity of query() is O(n). Binary Index Tree (BIS) is used for this scenario.

The main idea is storing the cumulative value range by range instead of one by one. Then update the related range instead of updating all cumulative value. It can optimize the query to O(log n)

The idea is based on the fact that all positive integers can be represented as sum of powers of 2. For example 19 can be represented as 16 + 2 + 1. Every node of BI Tree stores sum of n elements where n is a power of 2. For example, in the above first diagram for getSum(), sum of first 12 elements can be obtained by sum of last 4 elements (from 9 to 12) plus sum of 8 elements (from 1 to 8). The number of set bits in binary representation of a number n is O(Logn). Therefore, we traverse at-most O(Logn) nodes in both getSum() and update() operations. Time complexity of construction is O(nLogn) as it calls update() for all n elements.

(1) lowbit(x) returns the value represented by the right most bit 1 of x. when x = 5 = 0101b, lowbit(5) = 0001b = 1; when x = 12 = 1100b, lowbit(12) = 0100 = 8;

It is achieved by following code. Since -x = (binary complement of x) + 1. The first bit 0 in (binary complement of x) (or say first 1 in x) would become 1 after execute (binary complement of x) + 1. Thus x & -x can detect the first bit 1 in x

int lowbit(int x) {
    return x & -x;
}

(2) BIT structure

• C[i] is the cumulative value from A[i - (i&-i) + 1] to A[i].

• Once query(i), accumulate from C[i] towards lower left. A[0] is a dummy node, which is used to represent the end of query. eg. query() returns the cumulative value. eg. query[13] = query[1101b] = C[1101b] + C[1100b] + C[1000b]

int query(int idx){
    int sum = 0;
    while (idx > 0){
        sum += C[idx];
        idx -= (idx & -idx);
    }
    return sum;
}

• Once A[i] is changed, update C[] from C[i] towards upper right. eg, C[0001b] += val, C[0010b] += val, C[0100b] += val, C[1000b] += val

void add(int idx ,int val){
    while (idx <= maxIdx){
        C[idx] += val;
        idx += (idx & -idx);
    }
}