307.Range Sum Query - Mutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Method 1 Segment Tree

• """ The idea here is to build a segment tree. Each node stores the left and right endpoint of an interval and the sum of that interval. All of the leaves will store elements of the array and each internal node will store sum of leaves under it. Creating the tree takes O(n) time. Query and updates are both O(log n). """
• In Computer science, a segment tree is a tree data structure used for storing information about intervals, or segments. It allows querying which of the stored segments contain a given point. A segment tree for a set I of n intervals uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in O(log n + k), k being the number of retrieved intervals or segments.[1]

class Node(object):

    def __init__(self, start, end, total):
        self.left = None
        self.right = None
        self.total = total
        self.start = start
        self.end = end

class NumArray(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """

        # O(n) time
        def createTree(start, end):
            if start > end:
                return None
            # leaf node
            if start == end:
                n = Node(start, end, nums[start])
                return n

            mid = (start + end) / 2
            root = Node(start, end, 0)

            #recursively build the Segment tree
            root.left = createTree(start, mid)
            root.right = createTree(mid+1, end)

            #Total stores the sum of all leaves under root
            #i.e. those elements lying between (start, end)
            root.total = root.left.total + root.right.total

            return root
        self.root = createTree(0, len(nums)-1)

    def update(self, i, val): 

        # O(log n) time
        def updateTree(root):
            if root.start == root.end:
                root.total = val
                return 

            mid = (root.start + root.end) / 2
            #If the index is less than the mid, that leaf must be in the left subtree
            if i > mid:
                updateTree(root.right)
            else:
                updateTree(root.left)
             #Propogate the changes after recursive call returns
            root.total = root.left.total + root.right.total

        updateTree(self.root)


    def sumRange(self, i, j):

        def findRange(root, start, end):
            #If the range exactly matches the root, we already have the sum
            if root.start == start and root.end == end:
                return root.total

            mid = (root.start + root.end) / 2
            #If end of the range is less than the mid, the entire interval lies #in the left subtree
            if end <= mid:
                return findRange(root.left, start, end)
            #If start of the interval is greater than mid, the entire inteval lies
            #in the right subtree
            elif start >= mid + 1:
                return findRange(root.right, start, end)            
            #Otherwise, the interval is split. So we calculate the sum recursively,
            #by splitting the interval
            else:
                return findRange(root.left, start, mid) +  findRange(root.right, mid+1, end)

        return findRange(self.root, i , j)