Python: Segment Trees step by step recursive solution.
Segment Trees are useful to answer mutable range queries. \n\nPreprocessing(buildTree): O(n)\nUpdate : O(logn)\nQuery : O(logn)\n\nWe start by defining the node
Segment Trees are useful to answer mutable range queries. \n\n**Preprocessing(buildTree)**: O(n)\n**Update** : O(logn)\n**Query** : O(logn)\n\nWe start by defining the node of the segment tree.\n\n```\n#[lx,rx] denote the range of the interval of the node.\n# left and right denote the left and right children of the node\n#sum denotes the sum for the interval represented by the node. Initialized to zero.\nclass TreeNode:\n    def __init__(self,lx,rx):\n        self.lx = lx  \n        self.rx = rx\n        self.left = None \n        self.right = None\n        self.sum = 0 \n```\n\n### **Step 1: Defining the recursive buildTree() method**: \n\nThe buildTree(arr,i,j) method takes an array and two elements i,j such that *0<=i<=j<=len(arr)* and **returns**\n**TreeNode** representing the root of segment tree. The root denotes the segment [i,j]\n\n```\ndef buildTree(arr,i,j)->TreeNode:\n    if i==j:\n        root = TreeNode(i,j)\n        root.sum = arr[i]\n        return root\n    \n    else:\n        root = TreeNode(i,j)\n        mid = i+(j-i)//2\n        root.left = buildTree(arr,i,mid)\n        root.right = buildTree(arr,mid+1,j)\n        root.sum = root.left.sum+root.right.sum\n        return root\n```\n\n### **Step 2: Defining a recursive update() method**\nThe update(root,index,value) method, takes the root of the tree and recursively updates the left and right subtree based on the middle element in the interval of the root.\n\n```\ndef updateTree(root,index,value):\n    if root.lx == index and root.rx==index:\n        root.sum = value\n        \n    else:\n        mid = root.lx + (root.rx-root.lx)//2\n        if index<=mid:\n            root.left = updateTree(root.left,index,value)\n            root.sum = root.left.sum+root.right.sum\n        else:\n            root.right = updateTree(root.right,index,value)\n            root.sum = root.left.sum+root.right.sum\n    \n    return root\n```\n\n### **Step 3: Range Queries**\nGiven a range [i,j] we want to return the sum of the interval [i,j]\n\nRange Queries are the simplest part of the bunch. We check for three kinds of overlaps:\n\n**Case 1(Complete Overlap)**: Root interval [lx,rx] completely lies inside interval [i,j]. In this case we **return root.sum.**\n\n**Case 2(No Overlap)**: Root interval [lx,rx] and [i,j] are disjoint sets. Return 0 in this case.\n\n**Case 3(Partial Overlap)**: [lx,rx] and [i,j] have partial overlap. Note that, here [i,j] lying completely inside of [lx,rx] is also considered partial overlap.\n\n```\ndef checkOverlap(nodeInterval,queryInterval):\n        ix,iy = nodeInterval\n        jx,jy = queryInterval\n        \n        if ix>=jx and iy<=jy:\n            return 0 #complete overlap\n        \n        elif iy<jx or ix>jy:\n            return 1 #no overlap\n        \n        else:\n            return 2 #partial overlap\n        \n\n\ndef sumRange(root,i,j):\n    k = checkOverlap((root.lx,root.rx),(i,j))    \n    if k==0:\n        return root.sum\n    \n    elif k==1:\n        return 0\n    \n    else:\n        return sumRange(root.left,i,j)+sumRange(root.right,i,j)\n```\n\n### **Putting it all together**\n\nNumArray class encapsulates the functionality of the above methods and a final API is presented.\n```\nclass NumArray:\n\n    def __init__(self, nums):\n        self.root = buildTree(nums,0,len(nums)-1)\n\n    def update(self, index: int, val: int) -> None:\n        self.root = updateTree(self.root,index,val)\n\n    def sumRange(self, left: int, right: int) -> int:\n        return sumRange(self.root,left,right)\n```\n\n
['Tree', 'Recursion', 'Python']