time complexity - Binary Indexed Tree

Question

I am writing a binary indexed tree. As documentation, it requires nlogn time to pre process. But I am not able to understand why.

In my case I am constructing the tree from the Array, which should take 2n time, as first time traversing the array once to make it a Binary tree and then to update sum I am again traversing the tree in POST order fashion. so total 2n, not nlogn.

Can anybody explain why it needs nlogn time to pre-process the binary indexed tree.

public class BITree {

private class BTN {
    int data;
    int index;
    BTN left,right;

    public BTN(int data) {
        this.data = data;
    }
}
BTN head = null;


public BTN toBT(int[] arr,int start,int end){
    if(start <= end){
        int mid = start + (end - start)/2;
        BTN btn = new BTN(arr[mid]);
        btn.index = mid+1;
        btn.left = toBT(arr,start,mid-1);
        btn.right = toBT(arr,mid+1,end);
        return btn;
    }
    return null;
}

public  int sumAtIndex(BTN btn,int index){
    int sum = 0;
    if(index < btn.index)
        sum += sumAtIndex(btn.left,index);
    else if(index > btn.index) {
        sum += btn.data + sumAtIndex(btn.right, index);
    }
    if(btn.index == index)
        return btn.data + sum;
    return sum;
}

public int replaceSum(BTN btn){
    if(btn == null){
        return  0;
    }
    int l = replaceSum(btn.left);
    int r = replaceSum(btn.right);
    int sum = btn.data + l + r;
    btn.data += l;
    return sum;
}

void inOrder(BTN btn){
    if(btn != null) {
        inOrder(btn.left);
        System.out.print((btn.index+":"+btn.data)+",");
        inOrder(btn.right);
    }
}

public static void main(String[] args) {
    int[] arr = {5,1,6,4,2,3,3};
    BITree s2 = new BITree();
    BTN btn = s2.toBT(arr,0,arr.length-1);
    s2.replaceSum(btn);
    s2.inOrder(btn);
    System.out.println();
    System.out.println(s2.sumAtIndex(btn,3));
}


}

Answer 1

This question is a duplicate of :Is it possible to build a Fenwick tree in O(n)?

@Thilo , Thanks for pointing out the optimized way for preprocessing the the BIT. Which can be done in O(n) time.

https://en.wikipedia.org/wiki/Talk:Fenwick_tree

https://stackoverflow.com/a/31070683/3080158

@SanketMakani, Thanks for sharing the link, it explains the BIT very well.

here is the working code, with O(n) pre processing time.

package com.rabin;

import java.util.StringJoiner;

/**
 * 
 */
public class BITree {
    /**
     * O(logn)
     * @param arr
     * @param index
     * @param val
     */
    void update(int arr[],int index, int val)
    {
        index++;
        for(; index <= arr.length-1; index += index&-index)
            arr[index] += val;
    }

    /**
     * O(logn)
     * @param arr
     * @param noOfElements
     * @return
     */
    int query(int[] arr,int noOfElements)
    {
        int sum = 0;
        for(; noOfElements > 0; noOfElements -= noOfElements&-noOfElements)
            sum += arr[noOfElements-1];
        return sum;
    }

    /**
     * O(n)
     * @param arr
     */
    void toBIT(int[] arr){
        int n = arr.length;
        for(int i=1;i<=n;i++){
            int j = i+ (i & -i);
            if(j <= n)
                arr[j-1] += arr[i-1];
        }
    }

    static String arrayToString(int[] arr){
        StringJoiner sj = new StringJoiner(",","[","]");
        for(int i = 0; i< arr.length ;i++){
            sj.add(String.valueOf(arr[i]));
        }
        return sj.toString();
    }

    public static void main(String[] args) {
        int[] arr = {5,1,6,4,2,3,3};
        BITree bit = new BITree();

        System.out.println("Original Array:" +arrayToString(arr));
        bit.toBIT(arr);
        System.out.println("BIT Array:" +arrayToString(arr));
        System.out.println("Sum of first 5 nos : "+ bit.query(arr,5));
        bit.update(arr,0,8);
        System.out.println("Sum of first 5 nos after update : "+ bit.query(arr,5));

    }
}

Answer 2

@RBanerjee nicely written code, It is good to implement the BIT with one additional index, which helps in code comprehension. Plus it also signifies one additional thing - the least significant 1 bit from the BIT index indicates as to how many elements does the particular index stores. For e.g. index = 2 (010) can signify index 2 in BIT holds the values of 2 elements, similarly 4 (100) for 4, 6 (110) stores 2 values (namely, index 5 and 6) and so on.

Additionally, in your update method you aren't updating the value per se. You are adding the given value. Which I do not think signifies the meaning of update. It is a very subjective discussion, but I think of it as an update and not an increment. So, if the index 5 originally holds value 2, and when I want to update it to -1, it means the value after the update at index 5 is -1 and not 1.

As an extra step, it is good to provide a way to query the ranges in the array. For e.g. what is the value between indices 2 and 5 (inclusive).

<!-- language: java -->


package DataStructureImplementation;

import java.util.StringJoiner;

public class BinaryIndexedTree {

    private final int[] bit;
    private final int[] nums;
    private final int n;

    public BinaryIndexedTree(int[] nums) {
        n = nums.length;
        bit = new int[n + 1];
        this.nums = nums;
        System.arraycopy(nums, 0, bit, 1, nums.length);
        build();
    }

    /**
     * Builds a binary indexed tree in O(n) time.
     */
    private void build() {
        int j;
        for (int i = 1; i <= n; ++i) {
            j = i + (i & -i);
            if (j <= n) bit[j] += bit[i];
        }
    }

    /**
     * Updates an indexed item in the original array to the given value.
     * Also updates the values in the 'BIT' in O(logn) time.
     * @param index - index of the item to update
     * @param value - value to update to
     */
    public void update(int index, int value) {
        int diff = value - nums[index];
        nums[index] = value;
        index++;

        while (index <= n) {
            bit[index] += diff;
            index += (index & -index);
        }
    }

    /**
     * Queries the sum of the first 'K' indices in the original array in O(logn) time.
     * @param k - the number of items to aggregate.
     * @return - the sum of first 'K' numbers in the original array.
     * @throws Exception - if 'K' is out of bounds.
     */
    public int query(int k) throws Exception {
        if (k < 0 || k > n) throw new Exception("Invalid query range : " + k);
        int sum = 0;

        while (k > 0) {
            sum += bit[k];
            k -= (k & -k);
        }

        return sum;
    }

    /**
     * Queries the sum of numbers from the original array between index1 and index2 (inclusive) in O(logn) time.
     * @param index1 - left index.
     * @param index2 - right index.
     * @return - the sum of numbers between the given ranges.
     * @throws Exception - if range is out of bounds.
     */
    public int queryRange(int index1, int index2) throws Exception {
        return query(index2 + 1) - query(index1);
    }

    /**
     * Helper method to print the array contents.
     * @param nums - the array to print.
     * @return - the contents of the array as string.
     */
    static String arrayToString(int[] nums){
        StringJoiner stringJoiner = new StringJoiner(",","[","]");

        for (int n : nums) {
            stringJoiner.add(String.valueOf(n));
        }

        return stringJoiner.toString();
    }

    public static void main(String[] args) throws Exception {
        int[] nums = {5,8,5,4,2,3};

        BinaryIndexedTree binaryIndexedTree = new BinaryIndexedTree(nums);
        System.out.println("Original Array : " + arrayToString(nums));
        System.out.println("BIT Array : " + arrayToString(binaryIndexedTree.bit));
        System.out.println("Sum of first 5 nos : " + binaryIndexedTree.query(5));
        binaryIndexedTree.update(4,-1);
        System.out.println("Original Array after update : " + arrayToString(nums));
        System.out.println("BIT Array after update : " + arrayToString(binaryIndexedTree.bit));
        System.out.println("Sum of first 5 nos after update : " + binaryIndexedTree.query(5));
        System.out.println("Sum of numbers in range 2-5 : " + binaryIndexedTree.queryRange(2, 5));
    }
}