Intuitive and Optimized approach Explained Every Step
when the retrival frequency is high array is actually better as it retrives the sum in O(1) but update always take O(n).\n\nOn the other hand Segment for both O
when the retrival frequency is high array is actually better as it retrives the sum in O(1) but update always take O(n).\n\nOn the other hand Segment for both Operation it takes O(nLongN)\n\n\n# Code\n```java []\n//Approach -1 \n\n// This will give you TLE\n\nclass NumArray {\n    private int[] nums;\n    private int[] prefixSums;\n\n    public NumArray(int[] nums) {\n        this.nums = nums;\n        this.prefixSums = new int[nums.length + 1];\n        for (int i = 0; i < nums.length; i++) {\n            prefixSums[i + 1] = prefixSums[i] + nums[i];\n        }\n    }\n\n    public void update(int index, int val) {\n        int oldVal = nums[index];\n        nums[index] = val;\n        int diff = val - oldVal;\n        for (int i = index + 1; i < prefixSums.length; i++) {\n            prefixSums[i] += diff;\n        }\n    }\n\n    public int sumRange(int left, int right) {\n        return prefixSums[right + 1] - prefixSums[left];\n    }\n}\n\n/**\n * Your NumArray object will be instantiated and called as such:\n * NumArray obj = new NumArray(nums);\n * obj.update(index,val);\n * int param_2 = obj.sumRange(left,right);\n */\n\n```\n```java []\n// Follow Up 315. Count of Smaller Numbers After Self\n\npublic class NumArray {\n\n    class SegmentTreeNode {\n        private int start, end;\n        private  SegmentTreeNode left, right;\n        private  int sum;\n\n        public SegmentTreeNode(int start, int end) {\n            this.start = start;\n            this.end = end;\n            this.left = null;\n            this.right = null;\n            this.sum = 0;\n        }\n    }\n\n    SegmentTreeNode root = null;\n\n    public NumArray(int[] nums) {\n        root = buildTree(nums, 0, nums.length-1);\n    }\n    // TC : O(n)\n    private SegmentTreeNode buildTree(int[] nums, int start, int end) {\n        if (start > end) {\n            return null;\n        } else {\n            SegmentTreeNode ret = new SegmentTreeNode(start, end);\n            if (start == end) {\n                ret.sum = nums[start]; // leaf nodes\n            } else {\n                int mid = start  + (end - start) / 2;\n                ret.left = buildTree(nums, start, mid);\n                ret.right = buildTree(nums, mid + 1, end);\n                ret.sum = ret.left.sum + ret.right.sum;\n            }\n            return ret;\n        }\n    }\n\n    // TC : O(logn)\n    void update(int i, int val) {\n        updateHelper(root, i, val);\n    }\n\n    void updateHelper(SegmentTreeNode root, int pos, int val) {\n        // found leaf node to be updated\n        if (root.start == root.end) {\n            root.sum = val;\n        } else {\n            // parent nodes across the path\n            int mid = root.start + (root.end - root.start) / 2;\n            if (pos <= mid) {\n\n                updateHelper(root.left, pos, val);\n            } else {\n                updateHelper(root.right, pos, val);\n            }\n            root.sum = root.left.sum + root.right.sum;\n        }\n    }\n\n    public int sumRange(int i, int j) {\n        return sumRangeHelper(root, i, j);\n    }\n\n    // TC : O(logn)\n    public int sumRangeHelper(SegmentTreeNode root, int start, int end) {\n        // if you found out the node that matches your search return its value\n        if (root.start == start && root.end == end ) {\n            return root.sum;\n        } else {\n\n            int mid = root.start + (root.end - root.start) / 2; // overflow conditions\n            if (end <= mid) {\n                // move left\n                return sumRangeHelper(root.left, start, end);\n            } else if (start >= mid+1) {\n                // move right\n                return sumRangeHelper(root.right, start, end);\n            }  else {\n                // consider both nodes\n                return  sumRangeHelper(root.left, start, mid) + sumRangeHelper(root.right, mid+1, end) ;\n            }\n        }\n    }\n}\n```\n```java []\n\n//Approach -2\n\nclass NumArray {\n    private int[] segmentTree; // Array to store segment tree\n    private int arrayLength; // Length of the input array\n\n    // Constructor to initialize the segment tree with the given array\n    public NumArray(int[] nums) {\n        this.arrayLength = nums.length; // Set the length of the input array\n        if (arrayLength > 0) { // If array is not empty\n            int height = (int) (Math.ceil(Math.log(arrayLength) / Math.log(2))); // Calculate height of the segment tree\n            int maxSize = 2 * (int) Math.pow(2, height) - 1; // Maximum size of the segment tree\n            segmentTree = new int[maxSize]; // Initialize the segment tree array\n            buildSegmentTree(nums, 0, arrayLength - 1, 0); // Build the segment tree\n        }\n    }\n\n    // Utility function to get the middle index of a range\n    private int getMiddle(int start, int end) {\n        return start + (end - start) / 2;\n    }\n\n    // Recursive function to build the segment tree\n    private void buildSegmentTree(int[] arr, int segmentStart, int segmentEnd, int currentIndex) {\n        // If the segment start is equal to the segment end, it\'s a leaf node\n        if (segmentStart == segmentEnd) {\n            segmentTree[currentIndex] = arr[segmentStart]; // Set the leaf node value\n            return;\n        }\n        int mid = getMiddle(segmentStart, segmentEnd); // Get the middle index\n        buildSegmentTree(arr, segmentStart, mid, currentIndex * 2 + 1); // Recursively build the left subtree\n        buildSegmentTree(arr, mid + 1, segmentEnd, currentIndex * 2 + 2); // Recursively build the right subtree\n        // Set the current node value as the sum of left and right children\n        segmentTree[currentIndex] = segmentTree[currentIndex * 2 + 1] + segmentTree[currentIndex * 2 + 2];\n    }\n\n    // Function to update an element in the segment tree\n    public void update(int index, int newValue) {\n        if (arrayLength == 0) return; // If the array is empty, do nothing\n        int difference = newValue - getElement(0, arrayLength - 1, index, 0); // Calculate the difference\n        updateSegmentTree(0, arrayLength - 1, index, difference, 0); // Update the segment tree\n    }\n\n    // Utility function to get the value of an element in the segment tree\n    private int getElement(int segmentStart, int segmentEnd, int queryIndex, int currentIndex) {\n        // If the segment start is equal to the segment end, it\'s a leaf node\n        if (segmentStart == segmentEnd) {\n            return segmentTree[currentIndex]; // Return the leaf node value\n        }\n        int mid = getMiddle(segmentStart, segmentEnd); // Get the middle index\n        // Recursively get the element value from the left or right subtree\n        if (queryIndex <= mid) {\n            return getElement(segmentStart, mid, queryIndex, 2 * currentIndex + 1);\n        } else {\n            return getElement(mid + 1, segmentEnd, queryIndex, 2 * currentIndex + 2);\n        }\n    }\n\n    // Recursive function to update the segment tree\n    private void updateSegmentTree(int segmentStart, int segmentEnd, int index, int difference, int currentIndex) {\n        // If the index is outside the segment range, return\n        if (index < segmentStart || index > segmentEnd) return;\n        segmentTree[currentIndex] += difference; // Update the current node value\n        // If the segment start is not equal to the segment end, update the children\n        if (segmentStart != segmentEnd) {\n            int mid = getMiddle(segmentStart, segmentEnd); // Get the middle index\n            updateSegmentTree(segmentStart, mid, index, difference, 2 * currentIndex + 1); // Update the left subtree\n            updateSegmentTree(mid + 1, segmentEnd, index, difference, 2 * currentIndex + 2); // Update the right subtree\n        }\n    }\n\n    // Function to get the sum of elements in the given range\n    public int sumRange(int left, int right) {\n        if (arrayLength == 0) return 0; // If the array is empty, return 0\n        return getSum(0, arrayLength - 1, left, right, 0); // Get the sum from the segment tree\n    }\n\n    // Recursive function to get the sum of elements in the given range\n    private int getSum(int segmentStart, int segmentEnd, int queryStart, int queryEnd, int currentIndex) {\n        // If the query range is within the segment range, return the current node value\n        if (queryStart <= segmentStart && queryEnd >= segmentEnd) {\n            return segmentTree[currentIndex];\n        }\n        // If the segment range is outside the query range, return 0\n        if (segmentEnd < queryStart || segmentStart > queryEnd) {\n            return 0;\n        }\n        int mid = getMiddle(segmentStart, segmentEnd); // Get the middle index\n        // Recursively get the sum from the left and right subtrees\n        return getSum(segmentStart, mid, queryStart, queryEnd, 2 * currentIndex + 1) +\n               getSum(mid + 1, segmentEnd, queryStart, queryEnd, 2 * currentIndex + 2);\n    }\n}\n\n/**\n * Your NumArray object will be instantiated and called as such:\n * NumArray obj = new NumArray(nums);\n * obj.update(index,val);\n * int param_2 = obj.sumRange(left,right);\n */\n\n\n```\n``` java []\nclass NumArray {\n    private SegmentTree root; // Root of the segment tree\n\n    public NumArray(int[] nums) {\n        if (nums.length > 0) {\n            root = buildSegmentTree(nums, 0, nums.length - 1); // Build the segment tree\n        }\n    }\n\n    // Class representing a segment tree node\n    class SegmentTree {\n        SegmentTree left, right;\n        int start, end, sum;\n\n        SegmentTree(int start, int end) {\n            this.start = start;\n            this.end = end;\n        }\n    }\n\n    // Function to build the segment tree\n    private SegmentTree buildSegmentTree(int[] nums, int start, int end) {\n        SegmentTree node = new SegmentTree(start, end);\n        if (start == end) {\n            node.sum = nums[start];\n        } else {\n            int mid = start + (end - start) / 2;\n            node.left = buildSegmentTree(nums, start, mid);\n            node.right = buildSegmentTree(nums, mid + 1, end);\n            node.sum = node.left.sum + node.right.sum;\n        }\n        return node;\n    }\n\n    // Function to update an element in the segment tree\n    public void update(int index, int val) {\n        update(root, index, val);\n    }\n\n    private void update(SegmentTree node, int index, int val) {\n        if (node.start == node.end) {\n            node.sum = val;\n        } else {\n            int mid = node.start + (node.end - node.start) / 2;\n            if (index <= mid) {\n                update(node.left, index, val);\n            } else {\n                update(node.right, index, val);\n            }\n            node.sum = node.left.sum + node.right.sum;\n        }\n    }\n\n    // Function to get the sum of elements in the given range\n    public int sumRange(int left, int right) {\n        return sumRange(root, left, right);\n    }\n\n    private int sumRange(SegmentTree node, int start, int end) {\n        if (node.start == start && node.end == end) {\n            return node.sum;\n        }\n        int mid = node.start + (node.end - node.start) / 2;\n        if (end <= mid) {\n            return sumRange(node.left, start, end);\n        } else if (start > mid) {\n            return sumRange(node.right, start, end);\n        } else {\n            return sumRange(node.left, start, mid) + sumRange(node.right, mid + 1, end);\n        }\n    }\n}\n\n```
['Segment Tree', 'Java']