Range Sum Query - Mutable

Given an integer array nums, handle multiple queries of the following types:

  1. Update the value of an element in nums.
  2. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

  • NumArray(int[] nums) Initializes the object with the integer array nums.
  • void update(int index, int val) Updates the value of nums[index] to be val.
  • int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

 

Example 1:

Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]

Explanation
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

 

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -100 <= nums[i] <= 100
  • 0 <= index < nums.length
  • -100 <= val <= 100
  • 0 <= left <= right < nums.length
  • At most 3 * 104 calls will be made to update and sumRange.
SOLUTION:
class Node:
    def __init__(self, start, end, total = 0):
        self.start = start
        self.end = end
        self.left = None
        self.right = None
        self.total = 0

class NumArray:
    def __init__(self, nums):
        n = len(nums)
        self.root = self.createTree(0, n - 1, nums)
        
    def createTree(self, start, end, nums):
        if start > end:
            return None
        root = Node(start, end)
        if start == end:
            root.total = nums[start]
            return root
        mid = (start + end) // 2
        root.left = self.createTree(start, mid, nums)
        root.right = self.createTree(mid + 1, end, nums)
        root.total = root.left.total + root.right.total
        return root
    
    def updateVal(self, root, i, val):
        if not root:
            return
        if root.start == root.end:
            root.total = val
            return
        mid = (root.start + root.end) // 2
        if i <= mid:
            self.updateVal(root.left, i, val)
        elif i >= mid + 1:
            self.updateVal(root.right, i, val)
        root.total = root.left.total + root.right.total
    
    def update(self, index, val):
        self.updateVal(self.root, index, val)
    
    def getSum(self, root, start, end):
        if not root:
            return 0
        if root.start == start and root.end == end:
            return root.total
        mid = (root.start + root.end) // 2
        if end <= mid:
            return self.getSum(root.left, start, end)
        elif start >= mid + 1:
            return self.getSum(root.right, start, end)
        else:
            return self.getSum(root.left, start, mid) + self.getSum(root.right, mid + 1, end)
    
    def sumRange(self, left, right):
        return self.getSum(self.root, left, right)

Comments

Post a Comment

Popular posts from this blog

Lazy Deletion in Heap: A Wrapper for Python heapq

Lazy Deletion in Heap: A Wrapper for Python heapq Lazy Deletion in Heap: A Wrapper for Python heapq In many programming scenarios, we often encounter situations where we need to maintain a heap data structure and perform operations such as insertion, deletion, and retrieval of the minimum element efficiently. Python provides a built-in module called heapq that offers heap operations. However, the standard heapq module does not provide direct support for lazy deletion, which can be useful in certain cases. In this article, we will explore a wrapper class, Heap , that extends the functionality of the Python heapq library to support lazy deletion in a heap. The Heap Class The Heap class is a wrapper that encapsulates the heapq module to enable lazy deletion in a heap. Let's go through its main methods and their functionalities: __init__(self) : Initializes the Heap instance by creating an empty heap and a defaultdict to track the deleted elements ...
Read more

Sliding Window GCD

Sliding Window GCD Sliding Window GCD Problem Description You are given an array of integers nums of length N . There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return an array of length N - k + 1 representing the GCD of each subarray of length k from left to right. Solution Approach The solution to this problem involves implementing a special queue data structure using two stacks. This special queue allows the push , pop , and GCD operations in O(1) amortized time complexity. The implementation of this queue is based on the combination of two existing techniques: implementing a queue using stacks and implementing a stack that stores GCD values. By using this special queue, we can efficiently calculate the GCD for each sliding window in O(N) time complexity. This technique is useful to understand the impl...
Read more

Degree of an Array

Given a non-empty array of non-negative integers nums , the degree of this array is defined as the maximum frequency of any one of its elements. Your task is to find the smallest possible length of a (contiguous) subarray of nums , that has the same degree as nums .   Example 1: Input: nums = [1,2,2,3,1] Output: 2 Explanation: The input array has a degree of 2 because both elements 1 and 2 appear twice. Of the subarrays that have the same degree: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] The shortest length is 2. So return 2. Example 2: Input: nums = [1,2,2,3,1,4,2] Output: 6 Explanation: The degree is 3 because the element 2 is repeated 3 times. So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.   Constraints: nums.length will be between 1 and 50,000. nums[i] will be an integer between 0 and 49,999. SOLUTION: from collections import defaultdict class Solution : def findShortestSubArr...
Read more