Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/307.html
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 indicesleft
andright
inclusive whereleft <= right
.
Implement the NumArray
class:
NumArray(int[] nums)
Initializes the object with the integer arraynums
.void update(int index, int val)
Updates the value ofnums[index]
to beval
.int sumRange(int left, int right)
Returns the sum of the elements ofnums
between indicesleft
andright
inclusive (i.e.nums[left] + nums[left + 1] + ... + nums[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
Constraints:
1 <= nums.length <= 3 * 104
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
- At most
3 * 104
calls will be made toupdate
andsumRange
.
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); */ } ############ class BinaryIndexedTree { private int n; private int[] c; public BinaryIndexedTree(int n) { this.n = n; c = new int[n + 1]; } public void update(int x, int delta) { while (x <= n) { c[x] += delta; x += lowbit(x); } } public int query(int x) { int s = 0; while (x > 0) { s += c[x]; x -= lowbit(x); } return s; } public static int lowbit(int x) { return x & -x; } } class NumArray { private BinaryIndexedTree tree; public NumArray(int[] nums) { int n = nums.length; tree = new BinaryIndexedTree(n); for (int i = 0; i < n; ++i) { tree.update(i + 1, nums[i]); } } public void update(int index, int val) { int prev = sumRange(index, index); tree.update(index + 1, val - prev); } public int sumRange(int left, int right) { return tree.query(right + 1) - tree.query(left); } } /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * obj.update(index,val); * int param_2 = obj.sumRange(left,right); */
-
// 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)
-
type BinaryIndexedTree struct { n int c []int } func newBinaryIndexedTree(n int) *BinaryIndexedTree { c := make([]int, n+1) return &BinaryIndexedTree{n, c} } func (this *BinaryIndexedTree) lowbit(x int) int { return x & -x } func (this *BinaryIndexedTree) update(x, delta int) { for x <= this.n { this.c[x] += delta x += this.lowbit(x) } } func (this *BinaryIndexedTree) query(x int) int { s := 0 for x > 0 { s += this.c[x] x -= this.lowbit(x) } return s } type NumArray struct { tree *BinaryIndexedTree } func Constructor(nums []int) NumArray { tree := newBinaryIndexedTree(len(nums)) for i, v := range nums { tree.update(i+1, v) } return NumArray{tree} } func (this *NumArray) Update(index int, val int) { prev := this.SumRange(index, index) this.tree.update(index+1, val-prev) } func (this *NumArray) SumRange(left int, right int) int { return this.tree.query(right+1) - this.tree.query(left) } /** * Your NumArray object will be instantiated and called as such: * obj := Constructor(nums); * obj.Update(index,val); * param_2 := obj.SumRange(left,right); */
-
public class NumArray { private int[] sums; private int numsCount; private int sumsCount; public NumArray(int[] nums) { numsCount = nums.Length; sumsCount = 1; var x = numsCount; while (x > 1) { x /= 2; sumsCount *= 2; } sumsCount = sumsCount * 2 - 1 + numsCount; sums = new int[sumsCount + 1]; for (var i = sumsCount; i > 0; --i) { if (i - sumsCount + numsCount - 1 >= 0) { sums[i] = nums[i - sumsCount + numsCount - 1]; } else { var l = i * 2; var r = l + 1; if (l <= sumsCount) { sums[i] += sums[l]; if (r <= sumsCount) { sums[i] += sums[r]; } } } } //System.Console.WriteLine(Newtonsoft.Json.JsonConvert.SerializeObject(sums)); } public void Update(int i, int val) { var j = sumsCount - numsCount + i + 1; sums[j] = val; for (j /= 2; j > 0; j /= 2) { var l = j * 2; var r = l + 1; sums[j] = sums[l]; if (r <= sumsCount) { sums[j] += sums[r]; } } //System.Console.WriteLine(Newtonsoft.Json.JsonConvert.SerializeObject(sums)); } public int SumRange(int i, int j) { return SumFromStart(j) - SumFromStart(i - 1); } private int SumFromStart(int i) { if (i < 0) return 0; var j = sumsCount - numsCount + i + 1; var sum = sums[j]; for (; j / 2 > 0; j /= 2) { if (j % 2 != 0) { sum += sums[j - 1]; } } return sum; } }