Binary Indexed Tree (BIT) or Fenwick tree

Binary indexed tree (also known as Fenwick tree) is the dynamic variant of prefix sum array. It provides two O(log n) time operations: processing a range sum and updating a value. Fenwick tree is represented by a one-indexed array, which makes implementation easier.

Let p(k) denote the largest power of two that divides k. We store a binary indexed tree as an array tree such that

tree[k] = sumq (k − p(k) + 1, k)

For example, for p(6), tree[6] = sum(6 - 2 + 1, 6) = sum(5, 6) where p(6) = 2 due to the fact that largest power of 2 that is in range of 6 is 2

To calculate the value of sum(a, b) where a > 1, we can use the formula:

sumq (a, b) = sum (1, b) − sum (1, a − 1)

Both sum(1, b) and sum(1, a-1) can be calculated in O(log n) time, so the total time complexity is O(log n).

Implementation

Fenwick uses binary representation of array indices to pre-calculate sum for some ranges.

When array indices are represented as binary values, for all the values where LSB is 1 i.e. value is odd, the original value is copied to fenwick tree.

For all other values, the value after LSB 1 bit is extracted and sum is calculated up to that index. The process is illustrated in the following diagram.

The least significant one bit of a value k can be extracted using following bit operation

p(k) = k & − k

For example, for value 10100, the negative is represented as 2`s compliment of this number which is ~10100 + 1 = 01011 + 1 = 01100. Notice that, before the least significant 1 bit in negative value all the values are flipped if compared to original number. Now, performing & operation will extract the part after (including) least significant 1 bit. 10100 & 01100 = 00100.

fun main() {
    // click + to see full script
    val arr = intArrayOf(4, 1, 2, 7, 8, 1, 0, 4, 2, 3).toTypedArray()
    val tree = FenwickTree(arr)
    println("arr: ${arr.contentToString()}")
    println("tree: $tree")
    (6..8).also { range ->
        println("sum of $range = ${tree.sum(range)}")
    }
    println("sum up to index 3 = ${tree.sumUpToIndex(3)}")
    println("add 2 to value at index 1")
    tree.addValue(1, 2)
    println("sum up to index 3 = ${tree.sumUpToIndex(3)}")
    println("tree: $tree")
}

//sampleStart
class FenwickTree(fromArray: Array<Int>) {
    // click + to see full script
    private val tree = Array(fromArray.size.plus(1)) { 0 }

    init {
        /**
         * initially copy all values to fenwick tree, remember that
         * fenwick tree index is one based, so destination position is 1.
         */
        System.arraycopy(fromArray, 0, tree, 1, fromArray.size)

        for (i in 1 until tree.size) {
            val parent = i.plus(i.and(-i))
            if (parent < tree.size) {
                tree[parent] = tree[parent] + tree[i]
            }
        }
    }

    /**
     * Return sum of range
     */
    fun sum(range: IntRange): Int {
        // range sum(a,b) = sum(1, b) - sum(1, a - 1)
        return sumUpToIndex(range.last) - sumUpToIndex(range.first.dec())
    }

    /**
     * Return sum up to index
     */
    fun sumUpToIndex(index: Int): Int {
        var sum = 0
        var i = index
        while (i > 0) {
            sum += tree[i]
            i -= i.and(-i)
        }
        return sum
    }

    /**
     * Add value to index
     */
    fun addValue(index: Int, value: Int) {
        var currentIndex = index
        while (currentIndex <= tree.size.dec()) {
            tree[currentIndex] += value
            currentIndex += currentIndex.and(-currentIndex)
        }
    }

    override fun toString(): String {
        return tree.contentToString()
    }
}
//sampleEnd