Teaching Kids Programming – Compute the Range Sum with Update: A Deep Dive into Segment Tree, SQRT Decomposition, Brute Force & Prefix Sum

Teaching Kids Programming: Videos on Data Structures and Algorithms

When working with arrays, one common task is to compute the sum of elements within a range, along with supporting dynamic updates to the array values. While a brute-force solution may work for small datasets, as the array grows, efficient techniques become crucial.

In this post, we’ll walk through four different approaches to solve the range sum with updates problem:

• Brute Force
• Prefix Sum
• Square Root Decomposition (SQRT)
• Segment Tree

Each method has its strengths and trade-offs in terms of time complexity, implementation difficulty, and real-world use cases.

Compute the Range Sum with Update Support

Given an array nums[], support the following operations:

• update(index, value): Update the element at index i to value.
• sumRange(left, right): Return the sum of elements between indices left and right, inclusive.

Brute Force Approach

Idea: Just iterate from left to right every time sumRange is called.

class NumArray:
    def __init__(self, nums):
        self.nums = nums

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

    def sumRange(self, left, right):
        return sum(self.nums[left:right+1])

Time Complexity:

• update: O(1)
• sumRange: O(n)

When to Use: For very small arrays where performance isn’t critical.

Prefix Sum (with Limitations)

Idea: Precompute a prefix sum array to get O(1) range sums.

prefix[i] = nums[0] + ... + nums[i-1]

Then:

sumRange(l, r) = prefix[r+1] - prefix[l]

Problem: If you update a value, all suffix prefix sums must be updated, making updates O(n).

class NumArray:
    def __init__(self, nums):
        self.nums = nums
        self.prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix[i+1] = self.prefix[i] + nums[i]

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

    def sumRange(self, left, right):
        return self.prefix[right+1] - self.prefix[left]

Time Complexity:

• update: O(n)
• sumRange: O(1)

When to Use: When updates are rare, but queries are frequent.

Square Root Decomposition (SQRT)

Idea: Divide the array into √n blocks. Precompute the sum of each block.

Operations:

• sumRange(l, r): Add up:
  • the partial block at the beginning
  • full blocks in between
  • the partial block at the end
• update(i, val): Update the value and the corresponding block sum.

import math

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

    def update(self, index, val):
        block_idx = index // self.block_size
        self.blocks[block_idx] += val - self.nums[index]
        self.nums[index] = val

    def sumRange(self, left, right):
        sum_ = 0
        while left <= right and left % self.block_size != 0:
            sum_ += self.nums[left]
            left += 1
        while left + self.block_size - 1 <= right:
            sum_ += self.blocks[left // self.block_size]
            left += self.block_size
        while left <= right:
            sum_ += self.nums[left]
            left += 1
        return sum_

Time Complexity:

• update: O(1)
• sumRange: O(√n)

When to Use: When you want a good balance between fast queries and updates without the complexity of a segment tree.

Segment Tree (The Power Tool)

Idea: Use a binary tree where each node represents a segment [l, r] and stores the sum of that segment. Updates and queries recurse down the tree efficiently.

class SegmentTreeNode:
    def __init__(self, l, r):
        self.left = self.right = None
        self.start = l
        self.end = r
        self.sum = 0

class NumArray:
    def __init__(self, nums):
        def build(l, r):
            node = SegmentTreeNode(l, r)
            if l == r:
                node.sum = nums[l]
            else:
                m = (l + r) // 2
                node.left = build(l, m)
                node.right = build(m+1, r)
                node.sum = node.left.sum + node.right.sum
            return node

        self.root = build(0, len(nums)-1)

    def update(self, index, val):
        def update_rec(node):
            if node.start == node.end:
                node.sum = val
                return
            m = (node.start + node.end) // 2
            if index <= m:
                update_rec(node.left)
            else:
                update_rec(node.right)
            node.sum = node.left.sum + node.right.sum

        update_rec(self.root)

    def sumRange(self, left, right):
        def sum_rec(node, l, r):
            if node.end < l or node.start > r:
                return 0
            if l <= node.start and node.end <= r:
                return node.sum
            return sum_rec(node.left, l, r) + sum_rec(node.right, l, r)

        return sum_rec(self.root, left, right)

Time Complexity:

• update: O(log n)
• sumRange: O(log n)

When to Use: When performance must scale for large arrays and frequent updates and queries.

Summary Table

Conclusion

For real-world applications with both frequent updates and queries, Segment Trees offer the best performance, albeit with more complex code. If you need something easier to write but still performant, SQRT Decomposition is a neat trick.

Understanding all four methods empowers you to choose the right tool for the job depending on the size of the data and performance requirements.

--EOF (The Ultimate Computing & Technology Blog) --