# Partial Sum Using Fenwick Tree

Let A be an array of n real numbers. Design an algorithm to perform any sequence of the following operations: • Add(i,y) – Add the value y to the ith number. • Partial-sum(i) – Return the sum of the first i numbers Each operation must take O(logn).

Fenwick Tree or Binary Indexed Tree is a tree containing n+1 nodes. Each node's parent is right most 1 flipped i.e

• 8 -> 1000 so parent is 0000 (0)

• 7 -> 0111 so parent is 0110 (6)

• 10 -> 1010 so parent is 1000 (8)

• 5 -> 0101 so parent is 0100 (4) Sum can be obtained by (0..5) -> tree[6] + tree[4] + tree[0] i.e index+1 and then go upwards to parents

To get the parent:

• 2's complement (Flip all bits and add 1)

• AND it with original number

• Subtract it from original number

7 (111) ---(step 1)---> 000+1=001 ---(AND 111)-->001 --(Subtract from 111)--->110

``package algorithmdesignmanualbook.partialsumimport algorithmdesignmanualbook.printimport java.util.*import kotlin.experimental.andimport kotlin.experimental.inv/** * Let A be an array of n real numbers. Design an algorithm to perform any sequence of the following operations: * • Add(i,y) – Add the value y to the ith number. * • Partial-sum(i) – Return the sum of the first i numbers * Each operation must take O(logn). * * Fenwick Tree or Binary Indexed Tree is a tree containing n+1 nodes. * Each node's parent is right most 1 flipped i.e * * 8 -> 1000 so parent is 0000 (0) * * 7 -> 0111 so parent is 0110 (6) * * 10 -> 1010 so parent is 1000 (8) * * 5 -> 0101 so parent is 0100 (4) * Sum can be obtained by (0..5) -> tree[6] + tree[4] + tree[0] i.e index+1 and then go upwards to parents * * To get the parent: * * 2's complement (Flip all bits and add 1) * * AND it with original number * * Subtract it from original number * * 7 (111) ---(step 1)---> 000+1=001 ---(AND 111)-->001 --(Subtract from 111)--->110 * */class PartialSumUsingFenwickTree(private val values: Array<Int>) {    val tree = Array(values.size + 1) { 0 }    init {        construcFenwickTree()    }    fun removeLastSetBit(byte: Byte): Byte {        return (byte - byte.and(byte.inv().plus(0b1).toByte())).toByte()    }    private fun construcFenwickTree() {        values.forEachIndexed { index, value ->            update(index, value)        }    }    private fun update(index: Int, value: Int) {        var bTreeIndex = index + 1        while (bTreeIndex <= values.size) {            tree[bTreeIndex] += value            bTreeIndex += bTreeIndex.and(-bTreeIndex)        }    }    fun getSum(index: Int): Int {        var sum = 0        var bIndex = index + 1        while (bIndex > 0) {            sum += tree[bIndex]            bIndex -= bIndex.and(-bIndex)        }        return sum    }}fun main() {    val solution = PartialSumUsingFenwickTree(arrayOf(1, 2, 3, 4, 5, 6))    solution.removeLastSetBit(0b111).print { it.toString(2) }    solution.tree.print {        Arrays.toString(it)    }    solution.getSum(2).print()}``

Updated on 2021-02-06