Welcome to Subscribe On Youtube
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
Code
-
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)); } // 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; } } // [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 { // segment tree 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; } } 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]; } };
-
class BinaryIndexedTree: def __init__(self, n): self.n = n self.c = [0] * (n + 1) @staticmethod def lowbit(x): return x & -x def update(self, x, delta): while x <= self.n: self.c[x] += delta x += BinaryIndexedTree.lowbit(x) def query(self, x): s = 0 while x > 0: s += self.c[x] x -= BinaryIndexedTree.lowbit(x) return s class NumArray: def __init__(self, nums: List[int]): self.tree = BinaryIndexedTree(len(nums)) for i, v in enumerate(nums, 1): self.tree.update(i, v) def update(self, index: int, val: int) -> None: prev = self.sumRange(index, index) self.tree.update(index + 1, val - prev) def sumRange(self, left: int, right: int) -> int: return self.tree.query(right + 1) - self.tree.query(left) # Your NumArray object will be instantiated and called as such: # obj = NumArray(nums) # obj.update(index,val) # param_2 = obj.sumRange(left,right) ############ # 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)