FilesExpand file tree

 master

/

segment_tree.py

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

49 lines (42 loc) · 1.34 KB

 master

/

segment_tree.py

Top

File metadata and controls

• Code
• Blame

49 lines (42 loc) · 1.34 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

'''

Segment_tree creates a segment tree with a given array and function,

allowing queries to be done later in log(N) time

function takes 2 values and returns a same type value

'''

class SegmentTree:

def __init__(self,arr,function):

self.segment = [0 for x in range(3*len(arr)+3)]

self.arr = arr

self.fn = function

self.maketree(0,0,len(arr)-1)

def make_tree(self,i,l,r):

if l==r:

self.segment[i] = self.arr[l]

elif l<r:

self.make_tree(2*i+1,l,int((l+r)/2))

self.make_tree(2*i+2,int((l+r)/2)+1,r)

self.segment[i] = self.fn(self.segment[2*i+1],self.segment[2*i+2])

def __query(self,i,L,R,l,r):

if l>R or r<L or L>R or l>r:

return None

if L>=l and R<=r:

return self.segment[i]

val1 = self.__query(2*i+1,L,int((L+R)/2),l,r)

val2 = self.__query(2*i+2,int((L+R+2)/2),R,l,r)

print(L,R," returned ",val1,val2)

if val1 != None:

if val2 != None:

return self.fn(val1,val2)

return val1

return val2

def query(self,L,R):

return self.__query(0,0,len(self.arr)-1,L,R)

'''

Example -

mytree = SegmentTree([2,4,5,3,4],max)

mytree.query(2,4)

mytree.query(0,3) ...

mytree = SegmentTree([4,5,2,3,4,43,3],sum)

mytree.query(1,8)

...

'''