-
Notifications
You must be signed in to change notification settings - Fork 8
Expand file tree
/
Copy pathFenwickTree.java
More file actions
90 lines (84 loc) · 2.84 KB
/
Copy pathFenwickTree.java
File metadata and controls
90 lines (84 loc) · 2.84 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/**
* Date 04/27/2015
* @author tusroy
*
* Write a program to implement fenwick or binary indexed tree
*
* A Fenwick tree or binary indexed tree is a data structure providing efficient methods
* for calculation and manipulation of the prefix sums of a table of values.
*
* Space complexity for fenwick tree is O(n)
* Time complexity to create fenwick tree is O(nlogn)
* Time complexity to update value is O(logn)
* Time complexity to get prefix sum is O(logn)
*
* References
* http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
* https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/
* http://en.wikipedia.org/wiki/Fenwick_tree
*/
public class FenwickTree {
/**
* Start from index+1 if you updating index in original array. Keep adding this value
* for next node till you reach outside range of tree
*/
public void updateBinaryIndexedTree(int binaryIndexedTree[], int val, int index){
while(index < binaryIndexedTree.length){
binaryIndexedTree[index] += val;
index = getNext(index);
}
}
/**
* Start from index+1 if you want prefix sum 0 to index. Keep adding value
* till you reach 0
*/
public int getSum(int binaryIndexedTree[], int index){
index = index + 1;
int sum = 0;
while(index > 0){
sum += binaryIndexedTree[index];
index = getParent(index);
}
return sum;
}
/**
* Creating tree is like updating Fenwick tree for every value in array
*/
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;
}
/**
* To get parent
* 1) 2's complement to get minus of index
* 2) AND this with index
* 3) Subtract that from index
*/
private int getParent(int index){
return index - (index & -index);
}
/**
* To get next
* 1) 2's complement of get minus of index
* 2) AND this with index
* 3) Add it to index
*/
private int getNext(int index){
return index + (index & -index);
}
public static void main(String args[]){
int input[] = {1,2,3,4,5,6,7};
FenwickTree ft = new FenwickTree();
int binaryIndexedTree[] = ft.createTree(input);
assert 1 == ft.getSum(binaryIndexedTree, 0);
assert 3 == ft.getSum(binaryIndexedTree, 1);
assert 6 == ft.getSum(binaryIndexedTree, 2);
assert 10 == ft.getSum(binaryIndexedTree, 3);
assert 15 == ft.getSum(binaryIndexedTree, 4);
assert 21 == ft.getSum(binaryIndexedTree, 5);
assert 28 == ft.getSum(binaryIndexedTree, 6);
}
}