\n An array \n Use the given array and queries to efficiently handle the requirements of \n This problem requires efficiently calculating range sums and processing updates, so we can use a Segment Tree<\/strong>. \n A Segment Tree has the following properties:\n<\/p>\n To implement a Segment Tree, follow these steps:<\/p>\n \n The Segment Tree is a powerful tool for efficiently handling the range sum of arrays. Try practicing the following problems:<\/p>\narr<\/code> containing n<\/code> integers is given,
\n and you need to write a function to handle the following queries:\n <\/p>\n\n
update(index, value)<\/code> : Updates the index<\/code>th value in the array arr<\/code> to value<\/code>.<\/li>\nrangeSum(left, right)<\/code> : Calculates the sum from the left<\/code>th to the right<\/code>th (0-indexing) in the array arr<\/code>.<\/li>\n<\/ul>\nupdate<\/code> and rangeSum<\/code>.
\n The size of the array is up to 10^5 and the number of queries is also up to 10^5.\n <\/p>\n<\/div>\nSolution Method<\/h2>\n
\n A Segment Tree is a binary tree-based data structure that stores the given array in intervals (for range sum queries).\n<\/p>\nDefinition of Segment Tree<\/h3>\n
\n
O(log n)<\/code>, meaning that both query and update operations take O(log n)<\/code> time.<\/li>\n<\/ul>\nSteps to Implement a Segment Tree<\/h3>\n
\n
JavaScript Code Implementation<\/h3>\n
\nclass SegmentTree {\n constructor(arr) {\n this.n = arr.length;\n this.tree = new Array(this.n * 4);\n this.build(arr, 0, 0, this.n - 1);\n }\n\n build(arr, node, start, end) {\n if (start === end) {\n \/\/ Store integer value at leaf node\n this.tree[node] = arr[start];\n } else {\n const mid = Math.floor((start + end) \/ 2);\n \/\/ Define left child\n this.build(arr, node * 2 + 1, start, mid);\n \/\/ Define right child\n this.build(arr, node * 2 + 2, mid + 1, end);\n \/\/ Define parent node as the sum of both children\n this.tree[node] = this.tree[node * 2 + 1] + this.tree[node * 2 + 2];\n }\n }\n\n rangeSum(left, right) {\n return this.sum(0, 0, this.n - 1, left, right);\n }\n\n sum(node, start, end, left, right) {\n if (right < start || end < left) {\n \/\/ Return 0 if requested range does not overlap\n return 0;\n }\n if (left <= start && end <= right) {\n \/\/ Return node if requested range is fully included\n return this.tree[node];\n }\n const mid = Math.floor((start + end) \/ 2);\n const leftSum = this.sum(node * 2 + 1, start, mid, left, right);\n const rightSum = this.sum(node * 2 + 2, mid + 1, end, left, right);\n return leftSum + rightSum;\n }\n\n update(index, value) {\n this.updateValue(0, 0, this.n - 1, index, value);\n }\n\n updateValue(node, start, end, index, value) {\n if (start === end) {\n \/\/ Update leaf node\n this.tree[node] = value;\n } else {\n const mid = Math.floor((start + end) \/ 2);\n if (index <= mid) {\n this.updateValue(node * 2 + 1, start, mid, index, value);\n } else {\n this.updateValue(node * 2 + 2, mid + 1, end, index, value);\n }\n \/\/ Update parent node\n this.tree[node] = this.tree[node * 2 + 1] + this.tree[node * 2 + 2];\n }\n }\n}\n\n\/\/ Example usage\nconst arr = [1, 3, 5, 7, 9, 11];\nconst segmentTree = new SegmentTree(arr);\nconsole.log(segmentTree.rangeSum(1, 3)); \/\/ 15\nsegmentTree.update(1, 10);\nconsole.log(segmentTree.rangeSum(1, 3)); \/\/ 22\n<\/code><\/pre>\n<\/div>\nConclusion<\/h2>\n
\n This data structure allows for updates and range sum calculations with a time complexity of O(log n)<\/code>.
\n When faced with complex problems in practice, using a Segment Tree can provide many advantages.\n<\/p>\nAdditional Practice Problems<\/h2>\n