Teaching Kids Programming – Square Root Decomposition to Query Range Sum of Mutable List

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Update the value of an element in nums.
Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.
Implement the NumArray class:

# Initializes the object with the integer array nums.
NumArray(int[] nums) 
# Updates the value of nums[index] to be val.
void update(int index, int val) 
#Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).
int sumRange(int left, int 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

Naive Solution: Mutable List Range Query – O(1) Update – O(N) Sum Range

The most intuitive way is to store the numbers as it is – and perform the sum range using bruteforce algorithm. This takes O(N) time to compute the range sum – but O(1) to update.

class NumArray:
    def __init__(self, nums: List[int]):
        self.nums = nums

    def sumRange(self, i, j):
        return sum(self.nums[i:j+1])

    def update(self, idx, val):
        self.nums[idx] = val

O(1) update and O(N) sum range.

Mutable List Range Query with Prefix Sum: O(N) Update – O(1) Sum Range

We can use prefix sum to obtain O(1) constant time for sumRange operation – however, to update a number requires O(N) time to update the prefix sum:

class NumArray:
    def __init__(self, nums: List[int]):
        self.nums = nums
        self.prefix = [0] + list(accumulate(self.nums))

    def sumRange(self, i, j):
        return self.prefix[j + 1] - self.prefix[i]

    def update(self, idx, val):
        for i in range(idx + 1, len(self.prefix)):
            self.prefix[i] += val - self.nums[idx]
        self.nums[idx] = val

O(N) update and O(1) sum range. The prefix sum is initialized using the accumulate function. We prepend a zero to avoid the prefix[to-1] having the negative index.

Mutable List Range Query with Sqrt Decomposition: O(1) Update – Sum Range

We can allocate blocks with size that stores the sub-sum of elements. Then, we can use to map the index i to block where b is the block size.

To update an element, we can just update the number and update the sum for that block. To compute the range sum – we at most need to add block sums. For individuals (left-overs that are not covered by entire blocks) – we can just add them – which should be less than 2 blocks. Overall time complexity will be which is still .

To sum up the range – we can add the block sum (and skip numbers if current block is covered entirely in the range – or add the individual otherwise.

class NumArray:
    def __init__(self, nums: List[int]):
        self.nums = nums
        self.n = math.ceil(sqrt(len(nums)))
        self.blocks = [0] * (len(nums) // self.n + 1)
        for i in range(len(nums)):
            self.blocks[i//self.n] += nums[i]        

    def update(self, idx: int, val: int) -> None:
        self.blocks[idx // self.n] += val - self.nums[idx]
        self.nums[idx] = val        

    def sumRange(self, left: int, right: int) -> int:
        ans = 0
        x = left
        while x <= right:
            if x % self.n == 0 and x + self.n <= right:
                ans += self.blocks[x // self.n]
                x += self.n     # skip to next block
            else:
                ans += self.nums[x]
                x += 1
        return ans

O(1) update and sum range.

This problem can also be solved by Segment Tree or Fenwick Tree – which has in both update and sum operations.

+--------------------+------------------------+----------------------+
|        Name        | Update Time Complexity | Query Time Compexity |
+====================+========================+======================+
|   Naive 1          |          O(1)          |         O(n)         |
+--------------------+------------------------+----------------------+
|   Naive 2          |          O(n)          |         O(1)         |
+--------------------+------------------------+----------------------+
|    Segment Tree    |         log(n)         |        log(n)        |
+--------------------+------------------------+----------------------+
|    Fenwick Tree    |         log(n)         |        log(n)        |
+--------------------+------------------------+----------------------+
| Sqrt Decomposition |          O(1)          |        sqrt(n)       |
+--------------------+------------------------+----------------------+

–EOF (The Ultimate Computing & Technology Blog) —