Advertisement
Sunilsai

Segment Tree Range Sum

May 11th, 2022
29
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.82 KB | None | 0 0
  1. class SegmentTree:
  2.    
  3.     def __init__(self, nums):
  4.         self.nums = nums
  5.         self.SegTree = [-1]*(len(self.nums)*4)
  6.         def BuildSegTree(Ind, Start, End):
  7.             if(Start == End):
  8.                 self.SegTree[Ind] = self.nums[Start]
  9.                 return
  10.             Mid = (Start + End)//2
  11.             BuildSegTree((Ind*2)+1, Start, Mid)
  12.             BuildSegTree((Ind*2)+2, Mid+1, End)
  13.             self.SegTree[Ind] = self.SegTree[(Ind*2)+1] + self.SegTree[(Ind*2)+2]
  14.         BuildSegTree(0, 0, len(self.nums)-1)
  15.        
  16.     def RangeSum(self, Left, Right):
  17.         def CalculateSum(Root, Start, End, Left, Right):
  18.             if(Start >= Left and End <= Right):
  19.                 return self.SegTree[Root]
  20.             elif(End < Left or Right < Start):
  21.                 return 0
  22.             Mid = (Start + End)//2
  23.             Sum1 = CalculateSum((Root*2)+1, Start, Mid, Left, Right)
  24.             Sum2 = CalculateSum((Root*2)+2, Mid+1, End, Left, Right)
  25.             return Sum1 + Sum2
  26.                
  27.         return CalculateSum(0, 0, len(self.nums)-1, Left, Right)
  28.        
  29.     def UpdatePoint(self, Ind, Val):
  30.         def SegPointUpdate(Root, Start, End, Ind, Val):
  31.             if(Start == End):
  32.                 self.SegTree[Root] = Val
  33.                 return
  34.             Mid = (Start + End)//2
  35.             if(Ind <= Mid):
  36.                 SegPointUpdate((Root*2)+1, Start, Mid, Ind, Val)
  37.             else:
  38.                 SegPointUpdate((Root*2)+2, Mid+1, End, Ind, Val)
  39.             self.SegTree[Root] = self.SegTree[(Root*2)+1] + self.SegTree[(Root*2)+2]
  40.         SegPointUpdate(0, 0, len(self.nums)-1, Ind, Val)
  41.        
  42.        
  43.        
  44. nums = [10, 20, 30, 40]
  45. Obj = SegmentTree(nums)
  46. print(Obj.SegTree)
  47. print(Obj.RangeSum(0,2))
  48. print(Obj.RangeSum(0,3))
  49. Obj.UpdatePoint(1,30)
  50. print(Obj.SegTree)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement