✅⬆️[JAVA/CPP/PYTHON] | 100% | 0 MS | EXPLAINED | SEGMENT TREE | MEME 🔥🔥🔥
UPVOTE PLEASE\n\nFor this problem we can have three possible solutions:\n\nThis code implements a segment tree which can be used to efficiently perform range qu
**UPVOTE PLEASE**\n\nFor this problem we can have three possible solutions:\n\nThis code implements a segment tree which can be used to efficiently perform range queries and updates on an array of numbers.\n\nThe NumArray class has three methods:\n\n__init__ - This is the constructor method which takes an input array nums and initializes the segment tree. It first calculates the length of the input array and creates an empty list self.seg_tree with a length of 4 times the input array length. It then calls the build function to construct the segment tree.\n\nupdate - This method takes an index index and a value val and updates the original input array with the new value. It achieves this by calling the seg_update function which recursively traverses the segment tree and updates the relevant nodes.\n\nsumRange - This method takes two indices left and right and returns the sum of values between these two indices in the original input array. It does this by calling the query function which recursively traverses the segment tree and returns the sum of values in the relevant nodes.\n\nThe build function is used to construct the segment tree. It takes three arguments - i, j, and indx. i and j define the range of indices for which the segment tree is being constructed, and indx is the index of the current node in the segment tree. The function recursively calls itself to construct the left and right subtrees and sets the value of the current node to the sum of values in the left and right subtrees.\n\nThe seg_update function is used to update the segment tree. It takes three arguments - index, val, and indx. index is the index of the value being updated, val is the new value, and indx is the index of the current node in the segment tree. The function recursively traverses the segment tree until it reaches the node corresponding to the index being updated and sets its value to the new value. It then updates the values of all the ancestor nodes in the segment tree.\n\nThe query function is used to perform range queries on the segment tree. It takes three arguments - left, right, and indx. left and right define the range of indices for which the sum is being calculated, and indx is the index of the current node in the segment tree. The function recursively traverses the segment tree until it reaches the nodes corresponding to the range being queried and returns the sum of values in those nodes.\n\nNaive Solution: Store the nums array and on each update just update the nums array directly. On each query, take the sum from left to right.\nCaching: Maintain a prefix sum, and on each query directly return prefix[right+1] - prefix[left]. On each update, adjust the whole prefix sum array according to the update made.\nSegment-Tree: Prepare a segment tree, On each query, traverse the segment tree of logarithmic height and return ans. On each update, traverse the same segment tree of logarithmic height and update\n\n\n<iframe src="https://leetcode.com/playground/3HKurxFV/shared" frameBorder="0" width="1080" height="1080"></iframe>\n\nThis code implements a Segment Tree data structure to efficiently perform range queries and updates on an array of integers.\n\nThe constructor takes in an array of integers and builds a Segment Tree to store the sum of the elements in various sub-ranges of the array. The buildTree function recursively builds the tree by dividing the range into two halves and calculating the sum of the child nodes to update the parent node.\n\nThe updateUtil function updates a single element in the array and propagates the change to the parent nodes by recursively updating the sum of the child nodes.\n\nThe rangeUtil function returns the sum of the elements in a given range of the array by recursively checking for total overlap, no overlap, or partial overlap with the child nodes.\n\nOverall, this implementation of the Segment Tree data structure allows for efficient updates and queries on the array of integers.\n\n# dry run \nInitialize the NumArray with the input [1, 3, 5].\nThis will create a segment tree with the following nodes:\nNode 1: [0, 2] with value 9\nNode 2: [0, 1] with value 4\nNode 3: [2, 2] with value 5\nCall sumRange(0, 2).\nThis will traverse the segment tree from the root node and return the value of node 1, which is 9.\nReturn 9 as output.\nCall update(1, 2).\nThis will update the value of index 1 in the NumArray to 2.\nThis will also update the segment tree as follows:\nNode 1: [0, 2] with value 7\nNode 2: [0, 1] with value 3\nNode 3: [2, 2] with value 5\nCall sumRange(0, 2).\nThis will traverse the segment tree from the root node and return the value of node 1, which is 8.\nReturn 8 as output.\n\n# The time complexity (TC)\nTC of initializing the NumArray using a segment tree is O(nlogn), where n is the size of the input array. The time complexity of both the sumRange and update operations using a segment tree is O(logn). Therefore, the overall time complexity of this solution is O(nlogn) for initialization and O(logn) for each query.\n\nThe space complexity (SC) of this solution is O(n) to store the input array and O(nlogn) to store the segment tree. Therefore, the overall space complexity is O(nlogn).\n(It is a 2 dimentional list but the inner dimension is always constant to 3.)\nHope it helps!\n\n\n\n![image](https://assets.leetcode.com/users/images/4ac4b4bb-1830-43f6-8d70-bdc33ba625a3_1659242357.2950683.png)\n
['Python', 'C++', 'Java']