Fenwick Tree / Binary Indexed Tree

geeksforgeeks Video

public class BinaryIndexedTree {

    int[] arr;
    int n;
    BinaryIndexedTree(int[] arr, int n) {
        this.arr = arr;
        this.n = n;
    }

    public int getSum(int[] BITree, int index) {
        int sum = 0; // Iniialize result

        // index in BITree[] is 1 more than the index in arr[]
        index = index + 1;

        // Traverse ancestors of BITree[index]
        while (index > 0) {
            // Add current element of BITree to sum
            sum += BITree[index];

            // Move index to parent node in getSum View
            index -= index & (-index);
        }
        return sum;
    }

    // Updates a node in Binary Index Tree (BITree) at given index
    // in BITree.  The given value 'val' is added to BITree[i] and
    // all of its ancestors in tree.
    public void updateBIT(int[] BITree, int n, int index, int val) {
        // index in BITree[] is 1 more than the index in arr[]
        index = index + 1;

        // Traverse all ancestors and add 'val'
        while (index <= n) {
           // Add 'val' to current node of BI Tree
           BITree[index] += val;

           // Update index to that of parent in update View
           index += index & (-index);
        }
    }

    // Constructs and returns a Binary Indexed Tree for given
    // array of size n.
    public int constructBITree(int[] arr, int n) {
        // Create and initialize BITree[] as 0
        int[] BITree = new int[n+1];
        for (int i=1; i<=n; i++) {
            BITree[i] = 0;
        }
        // Store the actual values in BITree[] using update()
        for (int i=0; i<n; i++) {
            updateBIT(BITree, n, i, arr[i]);
        }
        // Uncomment below lines to see contents of BITree[]
        //for (int i=1; i<=n; i++) {
        //      System.out.println(BITree[i]);
        //}

        return BITree;
    }

    public int getRangeSum(int[] BITree, int start, int end) {
        return getSum(BITree, end) - get(BITree, start);
    }
}