public int[] createTree(int input[]){
        int binaryIndexedTree[] = new int[input.length+1];
        for(int i=1; i <= input.length; i++){
            updateBinaryIndexedTree(binaryIndexedTree, input[i-1], i);
        }
        return binaryIndexedTree;
    }
Creating tree is like updating Fenwick tree for every value in array
src/com/interview/tree/FenwickTree.java