algoadvance

Leetcode 307. Range Sum Query

Problem Statement

You are given an integer array nums, and you are tasked with performing the following operations:

  1. Update: Update a specific element of the array at a given index.
  2. Sum Range: Return the sum of elements between indices left and right inclusive, where left and right are given.

Design an efficient data structure to implement the given operations.

Implement the NumArray class:

Clarifying Questions

  1. Can the array contain negative numbers?
    • Yes, nums can contain negative values.
  2. What are the constraints on the size of the array and the number of operations?
    • The length of nums will be in the range [1, 3 * 10^4].
    • The number of operations will be in the range [1, 3 * 10^4].

Strategy

To efficiently handle range sum and update queries, we can use a data structure known as Segment Tree. This structure allows us to perform both update and sum range queries in O(log n) time.

Here’s a high-level strategy using a Segment Tree:

  1. Building the Tree: Construct a segment tree from the given array. Each leaf node will represent an element of the array, and each internal node will represent the sum of its children.
  2. Updating the Tree: When updating an element, update the corresponding leaf node and propagate the change upwards to maintain the correct sum in each internal node.
  3. Querying the Tree: To get the sum of a range, combine the sums of segments that completely or partially overlap with the query range.

Code Implementation

#include <vector>

class NumArray {
public:
    NumArray(std::vector<int>& nums) : n(nums.size()), tree(2 * nums.size()) {
        // Build the tree
        buildTree(nums);
    }

    void update(int index, int val) {
        index += n; // Convert to leaf index
        tree[index] = val;

        // Update the parents
        while (index > 0) {
            int left = index;
            int right = index;
            if (index % 2 == 0) {
                right = index + 1;
            } else {
                left = index - 1;
            }
            // Parent updated to the sum of its children
            tree[index / 2] = tree[left] + tree[right];
            index /= 2;
        }
    }

    int sumRange(int left, int right) {
        left += n;
        right += n;
        int sum = 0;

        while (left <= right) {
            // If left is a right node, bring its value and move to parent's right node
            if (left % 2 == 1) {
                sum += tree[left];
                left++;
            }
            // If right is a left node, bring its value and move to parent's left node
            if (right % 2 == 0) {
                sum += tree[right];
                right--;
            }
            left /= 2;
            right /= 2;
        }
        return sum;
    }
    
private:
    std::vector<int> tree;
    int n;

    void buildTree(const std::vector<int>& nums) {
        // Initialize leaves
        for (int i = 0; i < n; ++i) {
            tree[n + i] = nums[i];
        }
        // Build the tree by summing children
        for (int i = n - 1; i > 0; --i) {
            tree[i] = tree[i * 2] + tree[i * 2 + 1];
        }
    }
};

Time Complexity

  1. Initialization: Building the segment tree takes O(n) time.
  2. Update Operation: Each update operation takes O(log n) time.
  3. Sum Range Query: Each sum range query takes O(log n) time.

By using a Segment Tree, we achieve efficient update and query times, making it suitable for handling large arrays and a high frequency of operations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI