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:

  1. Update the value of an element in nums.
  2. Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

  • NumArray(int[] nums) Initializes the object with the integer array nums.
  • void update(int index, int val) Updates the value of nums[index] to be val.
  • int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right 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 to update and sumRange.

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

  • 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;
        }
    }
    

All Problems

All Solutions