FilesExpand file tree

 master

/

fenwick_tree.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

54 lines (44 loc) · 1.81 KB

 master

/

fenwick_tree.py

Copy path

Top

File metadata and controls

• Code
• Blame

54 lines (44 loc) · 1.81 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

#################################################################################################################################

#Implementation of Binary Indexed Tree OR Fenwick Tree

#Time Complexities:

# Construction of Tree: O (n.log (n))

# Updating an element: O (log (n))

# Prefix Query (sum of elements 0 to i) or Range Minimum Query (sum of elements x to y): O (log (n))

#Space Complexity: O (n)

#################################################################################################################################

class FenTree (object):

def __init__ (self, array):

self.array, self.tree = [0] * len (array), [0] * (len (array) + 1);

for i in range (len (array)):

self.update (i, array [i]);

def get_parent (self, child):

return (child - (child & -child));

def get_next (self, index):

return (index + (index & -index));

def update (self, index, item):

current, self.array [index] = self.array [index], item;

item -= current;

index += 1;

while (index <= len (self.array)):

self.tree [index] += item;

index = self.get_next (index);

def prefix_sum (self, index):

index += 1;

total = 0;

while (index > 0):

total += self.tree [index];

index = self.get_parent (index);

return (total);

def range_sum (self, x, y):

return (self.prefix_sum (max (x, y)) - self.prefix_sum (min (x, y) - 1));

def describe (self):

print ('ARRAY =>\t', self.array);

print ('Binary Indexed Tree =>\t', self.tree);

if (__name__ == '__main__'):

tree = FenTree ([3,2,-1,6,5,4]);

# tree = FenTree ([int (i) for i in input ('Enter the array (space-separated integers): ').split ()]);

tree.describe ();

tree.update (4, 8); #replaces 5 with 8 in the list given to the fenwick tree

tree.describe ();

print (tree.range_sum (1, 5)); #returns 2-1+6+5+4

print (tree.prefix_sum (5)); #returns 3+2-1+6+5+4