22import math
33
44class SegmentTree :
5-
5+
66 def __init__ (self , N ):
77 self .N = N
88 self .st = [0 for i in range (0 ,4 * N )] # approximate the overall size of segment tree with array N
99 self .lazy = [0 for i in range (0 ,4 * N )] # create array to store lazy update
1010 self .flag = [0 for i in range (0 ,4 * N )] # flag for lazy update
11-
11+
1212 def left (self , idx ):
1313 return idx * 2
1414
@@ -34,7 +34,7 @@ def update(self, idx, l, r, a, b, val): # update(1, 1, N, a, b, v) for update va
3434 self .lazy [self .right (idx )] = self .lazy [idx ]
3535 self .flag [self .left (idx )] = True
3636 self .flag [self .right (idx )] = True
37-
37+
3838 if r < a or l > b :
3939 return True
4040 if l >= a and r <= b :
@@ -74,18 +74,18 @@ def showData(self):
7474 showList = []
7575 for i in range (1 ,N + 1 ):
7676 showList += [self .query (1 , 1 , self .N , i , i )]
77- print (showList )
78-
77+ print (showList )
78+
7979
8080if __name__ == '__main__' :
8181 A = [1 ,2 ,- 4 ,7 ,3 ,- 5 ,6 ,11 ,- 20 ,9 ,14 ,15 ,5 ,2 ,- 8 ]
8282 N = 15
8383 segt = SegmentTree (N )
8484 segt .build (1 ,1 ,N ,A )
85- print (segt .query (1 ,1 ,N ,4 ,6 ))
86- print (segt .query (1 ,1 ,N ,7 ,11 ))
87- print (segt .query (1 ,1 ,N ,7 ,12 ))
85+ print (segt .query (1 ,1 ,N ,4 ,6 ))
86+ print (segt .query (1 ,1 ,N ,7 ,11 ))
87+ print (segt .query (1 ,1 ,N ,7 ,12 ))
8888 segt .update (1 ,1 ,N ,1 ,3 ,111 )
89- print (segt .query (1 ,1 ,N ,1 ,15 ))
89+ print (segt .query (1 ,1 ,N ,1 ,15 ))
9090 segt .update (1 ,1 ,N ,7 ,8 ,235 )
9191 segt .showData ()
0 commit comments