Question

Formatted question description: https://leetcode.ca/all/307.html

 307. Range Sum Query - Mutable

 Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

 The update(i, val) function modifies nums by updating the element at index i to val.

 Example:

 Given nums = [1, 3, 5]

 sumRange(0, 2) -> 9
 update(1, 2)
 sumRange(0, 2) -> 8

 Note:
     The array is only modifiable by the update function.
     You may assume the number of calls to update and sumRange function is distributed evenly.

 @tag-array

Algorithm

Segment Tree: The line segment tree is a full binary tree with some additional information, such as the sum of the nodes of the subtree, or the maximum value, the minimum value, etc.

Java implementation https://algs4.cs.princeton.edu/99misc/SegmentTree.java.html

https://en.wikipedia.org/wiki/Segment_tree img

Code

Java

  • public class Range_Sum_Query_Mutable {
    
        public static void main(String[] args) {
            Range_Sum_Query_Mutable out = new Range_Sum_Query_Mutable();
            NumArray na = out.new NumArray(new int[]{1,3,5});
            System.out.println(na.sumRange(0, 2));
            na.update(1, 2);
            System.out.println(na.sumRange(0, 2));
        }
    
    
        // [2,4,5,7,8,9]
        // [0,35,6, 29,12,17,  2,4,5,7,8,9]
        // @note: index=0 is no value, since root has no sibling node
        class NumArray {
    
            int[] tree;
            int n;
    
            public NumArray(int[] nums) {
    
                if (nums != null && nums.length > 0) {
                    this.n = nums.length;
                    this.tree = new int[nums.length * 2];
                    buildTree(nums);
                }
            }
    
            private void buildTree(int[] nums) {
                // leaves are input array
                for (int i = this.n, j = 0; i < this.tree.length; i++, j++) {
                    this.tree[i] = nums[j];
                }
    
                // fill all middle layers up to root
                // @note: reverse order, bottom up method
                // @note: i>0, no = check
                for (int i = this.n - 1; i > 0; i--) {
                    this.tree[i] = this.tree[i * 2] + this.tree[i * 2 + 1];
                }
            }
    
            public void update(int i, int val) {
                int targetIndex = i + this.n;
                this.tree[targetIndex] = val;
    
                // bottom up update
                while (targetIndex > 0) {
                    int leftIndex = targetIndex;
                    int rightIndex = targetIndex;
    
                    // find its node pair
                    if (targetIndex % 2 == 0) {
                        rightIndex++;
                    } else {
                        leftIndex--;
                    }
    
                    this.tree[targetIndex / 2] = this.tree[leftIndex] + this.tree[rightIndex];
                    targetIndex /= 2;
                }
            }
    
            public int sumRange(int i, int j) {
                int indexi = i + this.n;
                int indexj = j + this.n;
    
                int sum = 0;
                while (indexi <= indexj) {
                    if (indexi % 2 == 1) {
                        sum += this.tree[indexi];
                        indexi++;
                    }
    
                    if (indexj % 2 == 0) {
                        sum += this.tree[indexj];
                        indexj--;
                    }
    
                    indexi /= 2;
                    indexj /= 2;
                }
    
                return sum;
            }
        }
    
        // in a real interview, this solution is good enough. seg-tree is just too much and missing the point of checking candidate coding capability
        class NumArray_block {
    
            private int len;
            private int[] block;
            private int[] nums;
    
            public NumArray_block(int[] nums) {
                this.nums = nums;
                double l = Math.sqrt(nums.length);
                len = (int) Math.ceil(nums.length/l); // @note: Math.ceil()
                block = new int [len];
                for (int i = 0; i < nums.length; i++) {
                    block[i / len] += nums[i];
                }
            }
    
            public int sumRange(int i, int j) {
                int sum = 0;
                int startBlock = i / len;
                int endBlock = j / len;
                if (startBlock == endBlock) {
                    for (int k = i; k <= j; k++) {
                        sum += nums[k];
                    }
                } else {
                    for (int k = i; k <= (startBlock + 1) * len - 1; k++) {
                        sum += nums[k];
                    }
                    for (int k = startBlock + 1; k <= endBlock - 1; k++) {
                        sum += block[k];
                    }
                    for (int k = endBlock * len; k <= j; k++) {
                        sum += nums[k];
                    }
                }
                return sum;
            }
    
            public void update(int i, int val) {
                int b_l = i / len;
                block[b_l] = block[b_l] - nums[i] + val;
                nums[i] = val;
            }
    
        }
    
        class NumArray_overtime {
            private int[] nums;
    
            public NumArray_overtime(int[] nums) {
                this.nums = nums;
            }
    
            public int sumRange(int i, int j) {
                int sum = 0;
                for (int l = i; l <= j; l++) {
                    sum += nums[l];
                }
                return sum;
            }
    
            public void update(int i, int val) {
                nums[i] = val;
            }
            // Time Limit Exceeded
        }
    
    /**
     * Your NumArray object will be instantiated and called as such:
     * NumArray obj = new NumArray(nums);
     * obj.update(i,val);
     * int param_2 = obj.sumRange(i,j);
     */
    }
    
    
  • // OJ: https://leetcode.com/problems/range-sum-query-mutable/
    // Time:
    //      NumArray: O(N)
    //      update: O(1)
    //      sumRange: O(N)
    // Space: O(N)
    class NumArray {
    private:
        vector<int> sums;
        vector<int> nums;
        int firstDirty;
    public:
        NumArray(vector<int> &nums) : sums(nums.size() + 1), nums(nums), firstDirty(0) {
        }
    
        void update(int i, int val) {
            nums[i] = val;
            firstDirty = min(firstDirty, i);
        }
    
        int sumRange(int i, int j) {
            if (firstDirty != nums.size()) {
                for (int i = firstDirty; i < nums.size(); ++i) {
                    sums[i + 1] = sums[i] + nums[i];
                }
                firstDirty = nums.size();
            }
            return sums[j + 1] - sums[i];
        }
    };
    
  • # Segment tree node
    class STNode(object):
      def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.left = None
        self.right = None
    
    
    class SegmentedTree(object):
      def __init__(self, nums, start, end):
        self.root = self.buildTree(nums, start, end)
    
      def buildTree(self, nums, start, end):
        if start > end:
          return None
    
        if start == end:
          node = STNode(start, end)
          node.total = nums[start]
          return node
    
        mid = start + (end - start) / 2
    
        root = STNode(start, end)
        root.left = self.buildTree(nums, start, mid)
        root.right = self.buildTree(nums, mid + 1, end)
        root.total = root.left.total + root.right.total
        return root
    
      def updateVal(self, i, val):
        def updateVal(root, i, val):
          if root.start == root.end:
            root.total = val
            return val
          mid = root.start + (root.end - root.start) / 2
          if i <= mid:
            updateVal(root.left, i, val)
          else:
            updateVal(root.right, i, val)
    
          root.total = root.left.total + root.right.total
          return root.total
    
        return updateVal(self.root, i, val)
    
      def sumRange(self, i, j):
        def rangeSum(root, start, end):
          if root.start == start and root.end == end:
            return root.total
    
          mid = root.start + (root.end - root.start) / 2
          if j <= mid:
            return rangeSum(root.left, start, end)
          elif i >= mid + 1:
            return rangeSum(root.right, start, end)
          else:
            return rangeSum(root.left, start, mid) + rangeSum(root.right, mid + 1, end)
    
        return rangeSum(self.root, i, j)
    
    
    class NumArray(object):
      def __init__(self, nums):
        """
        initialize your data structure here.
        :type nums: List[int]
        """
        self.stTree = SegmentedTree(nums, 0, len(nums) - 1)
    
      def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: int
        """
        return self.stTree.updateVal(i, val)
    
      def sumRange(self, i, j):
        """
        sum of elements nums[i..j], inclusive.
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.stTree.sumRange(i, j)
    
    # Your NumArray object will be instantiated and called as such:
    # numArray = NumArray(nums)
    # numArray.sumRange(0, 1)
    # numArray.update(1, 10)
    # numArray.sumRange(1, 2)
    
    

All Problems

All Solutions