Make writing a habit together! This is the fourth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Topic describes

Given an array nums, you complete two types of queries.

  1. One type of query requires that the values corresponding to the numS subscripts of the array be updated
  2. Another type of query requires returning the sum of numS elements (inclusive) between indexes left and right in the array NUMS, where left <= right

Implement NumArray class:

  • NumArray(int[] nums) Initializes an object with the integer array nums
  • Void update(int index, int val) nums[index]
  • SumRange (int left, int right) sumRange(int left, int right) sumRange(int left, int right) sumRange(int left, int right) The nums [right])

Example 1: input: [” NumArray “, “sumRange”, “update”, “sumRange”] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]] output: [NULL, 9, NULL, 8] NumArray NumArray = new NumArray([1, 3, 5]); numArray.sumRange(0, 2); // Return 1 + 3 + 5 = 9 numarray. update(1, 2); / / nums =,2,5 [1]

Train of thought

This is about data structures. Let’s start with the most straightforward idea of what the problem would be if we just used array.

  • Initialization, time order n.
  • Update operation, O(1)
  • SumRange, time order n.

Initialization is nothing to talk about, updates are already O(1), and there is room for optimization is sumRange. The solution of three leaf elder sister introduces the method of tree array and line segment tree, which requires good data structure foundation. Here we introduce a naive method of segmentation. We split the original array into n segments, each of which is fixed to boxSize. Of course, the last segment may have an odd header, so the size is between 0 and s. After doing this, we do a pre-processing to sum each segment and save the sums in the goldbach array. Then we’ll look at the update and sumRange operations separately.

The update operation

When updating the sums of num[I], also update the sums of num[I] and goldbach [I /boxSize]. When updating the sums (I /boxSize), you don’t need to resum the sums, just add the difference between the new value and the old value of the I position to the original sum. So change the order and update the sums (num[I]) first. You can keep the time complexity of the update operation at O(1)

sumRange

Select left and right from left;

  • The same period

There’s nothing to say, just add up from left to right, and notice that includes right, it’s a front closed and back closed interval. The time in this case is O(boxSize)

  • Different segments

At this point, sum can be divided into three parts:

  • SumLeft: The sum from left to the end of the left interval
  • SumMid: indicates the sum of all intervals between left and right
  • SumRight: the sum from the start to the right range

For example, the following figure shows the split of the sum 2-8 when boxSize=4

The time complexity of this case is O(boxSize + len/boxSize + boxSize), which is O(boxSize + len/boxSize).

How do I determine the value of boxSize

Based on the above maximum time complexity O(boxSize + len/boxSize), find the value of boxSize that minimizes this expression. Let a= SQRT (boxSize), b= SQRT (len/boxSize) boxSize + len/boxSize = a^2 + b^2 >= aab = 2*len So when boxSize = SQRT (len), the expression minimizes

Java version code

class NumArray { private int[] nums; private int[] sums; private int boxSize; public NumArray(int[] nums) { this.nums = nums; int len = nums.length; boxSize = (int)Math.sqrt(len); sums = new int[len/boxSize+1]; for (int i = 0; i < len; i++) { sums[i/boxSize] += nums[i]; } } public void update(int index, int val) { sums[index/boxSize] += val - nums[index]; nums[index] = val; } public int sumRange(int left, int right) { int b1 = left / boxSize; int b2 = right / boxSize; if (b1 == b2) { int sum = 0; for (int i = left; i <= right; i++) { sum += nums[i]; } return sum; } int sumLeft = 0; for (int i = left; i < (b1+1)*boxSize; i++) { sumLeft += nums[i]; } int sumMid = 0; for (int i = b1+1; i < b2; i++) { sumMid += sums[i]; } int sumRight = 0; for (int i = b2*boxSize; i <= right; i++) { sumRight += nums[i]; } return sumLeft + sumMid + sumRight; } } /** * 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); * /Copy the code