# Segment Tree

Segment tree is used to pre-store the solutions for a series of intervals to improve run time while querying.

If a problem has intervals and if we have to use segment tree, we are supposed to implement the following functions

- Building segment tree
- Updating a node in the segment tree
- Querying the segment tree

class Solution:
    def __init__(self):
        self.tree = []
        
    def buildSegmentTree(self, node, low, up, nums):
        if (low == up):
            self.tree[node] = nums[low]
        elif (low > up):
            return
        else:
            mid = (low + up)//2
            self.buildSegmentTree(2*node+1, low, mid, nums)
            self.buildSegmentTree(2*node + 2, mid+1, up, nums)
            self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
    
    def query(self, node, i, j, low, up):
        if (j < low or i > up):
            return 0
        if (i == low and j == up):
            return self.tree[node]
        else:
            mid = (low+up)//2
            if (i>mid):
                return self.query(2*node+2, i, j, mid+1, up)
            if (j<=mid):
                return self.query(2*node+1, i, j, low, mid)
            
            return self.query(2*node+1, i, mid, low, mid) + self.query(2*node+2, mid+1, j, mid+1, up)
    
    def update(self, node, low, up, ind, val):
        if (low == up):
            self.tree[node] = val
            return
        mid = (low+up)//2
        if (ind > mid):
            self.update(2*node+2, mid+1, up, ind, val)
        else:
            self.update(2*node+1 ,low, mid, ind, val)
        self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
        
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        self.tree = [-math.inf] * (2 * len(nums) + 1)
        self.buildSegmentTree(0, 0, len(nums)-1, nums)
        print(self.tree)
        print(self.query(0, 0, 5, 0, len(nums)-1))
        self.update(0, 0, len(nums)-1, 2, 8)
        print(self.tree)