This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 307 on LeetCode. Fields and retrievals – arrays can be modified with medium difficulty.

Tag: “interval sum”, “tree array”

Given an array nums, you are asked to perform two types of queries. One type of query asks you to update the value of the array subscript, and the other type of query asks you to return the sum of the elements in a range of the array.

Implement NumArray class:

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

Example:

Input: [" NumArray sumRange ", ""," update ", "sumRange"] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]] output: [8] 9, null, null, explanation:  NumArray numArray = new NumArray([1, 3, 5]); numArray.sumRange(0, 2); Sum ([1,3,5]) = numarray.update (1, 2); // nums = [1,2,5] numarray.sumrange (0, 2); Sum ([1,2,5]) = 8Copy the code

Tip:

  • 1 <= nums.length <= 3 *
    1 0 4 10^4
  • -100 <= nums[i] <= 100
  • 0 <= index < nums.length
  • -100 <= val <= 100
  • 0 <= left <= right < nums.length
  • Call the update and sumRange methods up to 3 * 10410^4104 times

Their thinking

This is a classic problem, and it usually leads to a whole class of questions.

We have different options for different problems (assuming we have an array) :

  1. Array invariant, find interval sum: “prefix sum”, “tree array”, “line segment tree”

  2. Modify a number several times to find the interval sum: “tree array”, “line segment tree”

  3. Modify an interval several times as a whole, and find the sum of the interval: “line segment tree”, “tree array” (see the data range of the modified interval)

  4. Change an interval into the same number many times, and find the interval sum: “line tree”, “tree array” (see the data range of the modified interval)

In this case, “segment tree” is the most problems, so should we write “segment tree” no matter what?

The answer is not, and quite the opposite, that we only consider segment trees if we have to write “segment trees” for class 4 problems.

Because the line tree code is long and the constants are large, the actual performance is not very good. We only consider segment trees when we have to use them.

To sum up, we should consider the following priorities:

  1. Simple interval sum, using “prefix sum”
  2. Turn an interval into the same number many times, using a line tree.
  3. In other cases, use tree array.

Tree array

If you modify a number many times, find the sum of intervals.

We use “tree array” to solve.

The “tree array” itself is a very simple data structure, but it is difficult to understand why it can be “queried” and “updated” in this way (especially why it can be updated in this way), and often needs to be understood from the perspective of “binary decomposition”.

So I’m going to provide the code for “tree array” directly, and you can just memorize it as a template.

Code:

class NumArray {
    int[] tree;
    int lowbit(int x) {
        return x & -x;
    }
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];
        return ans;
    }
    void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) tree[i] += u;
    }

    int[] nums;
    int n;
    public NumArray(int[] _nums) {
        nums = _nums;
        n = nums.length;
        tree = new int[n + 1];
        for (int i = 0; i < n; i++) add(i + 1, nums[i]);
    }
    
    public void update(int i, int val) {
        add(i + 1, val - nums[i]);
        nums[i] = val;
    }
    
    public int sumRange(int l, int r) {
        return query(r + 1) - query(l); }}Copy the code
  • Time complexity:addThe operation andqueryThe complexity of phi is zero
    O ( log ⁡ n ) O(\log{n})     , so the complexity of constructing the array is
    O ( n log ⁡ n ) O(n\log{n})     . The overall complexity is
    O ( n log ⁡ n ) O(n\log{n})
  • Space complexity: O(n)O(n)O(n)

Tree array template

Code:

// Write the three methods first
{
    int[] tree;
    int lowbit(int x) {
        return x & -x;
    }
    // Query the prefix and method
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];
        return ans;
    }
    // Increment the value u in the tree array x
    void add(int x, int u) {
        for (inti = x; i <= n; i += lowbit(i)) tree[i] += u; }}// Initialize the "tree array" with the default array starting at 1
{
    for (int i = 0; i < n; i++) add(i + 1, nums[i]);
}

// Use "tree array" :
{   
    void update(int i, int val) {
        Var -nums [I] = val -nums [I]
        add(i + 1, val - nums[i]); 
        nums[i] = val;
    }
    
    int sumRange(int l, int r) {
        return query(r + 1) - query(l); }}Copy the code

The last

This is the no.307 of our “Brush through LeetCode” series, which started on 2021/01/01. As of the start date, there are 1916 topics in LeetCode, some of which have locks. We will finish all the topics without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.