How to think about “interval sum” problem | Java brush problem punch card

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

Topic describes

This is the 1310. Subarray xor query on LeetCode with medium difficulty.

Tag: “math”, “tree array”, “prefix and”

Queries [I] = [Li, Ri]; queries[I] = [Li, Ri];

For each query I, calculate the XOR value from Li to Ri (i.e. Arr [Li] XOR arr[Li+1] XOR… Xor arr[Ri]) as the result of this query.

And returns an array containing all the results of a given query.

Example 1:

Input: arr =,3,4,8 [1], the queries = [[0, 1], [1, 2], [0, 3], [3]] output:,7,14,8 [2] explanation: the binary representation of the elements in an array is: 1 = 0001 3 = 0011 4 = 0100 8 = 1000 The XOR value is as follows: [0,1] = 1 xor 3 = 2 [1,2] = 3 xor 4 = 7 [0,3] = 1 xor 3 xor 4 xor 8 = 14 [3,3] = 8Copy the code

Example 2:

Input: arr =,8,2,10 [4], the queries = [[2, 3], [1, 3], [0, 0], [0, 3]] output:,0,4,4 [8]Copy the code

Tip:

• 1 <= arr.length <= 3 * 
  $10^4$
• 1 <= arr[i] <=
  $10^9$
• 1 <= queries.length <= 3 *
  $10^4$
• queries[i].length == 2
• 0 <= queries[i][0] <= queries[i][1] < arr.length

Fundamental analysis

Set the length of array ARr and array queries to n and M respectively.

The data range of n and M is 10410^4104, so O(m∗n)O(m * n)O(m∗n) O(m∗n) violence is not considered.

The scope of the data requires “logarithmic complexity” or “linear complexity”.

In this case, “The same value is used in the xOR operation
$0$“.

For a particular array [a1, a2, a3,…, an] [a1, a2, a3,…, an] [a1, a2, a3,…, an), asking too arbitrary interval [l, r] [l, r] [l, r] exclusive or as a result, Can [1, r] [1, r] [1, r] and [1, l – 1] [1, l – 1] [1, l – 1] vision or the results it is concluded that:

In essence, we still use the inclusive exclusion principle of sets (interval results). But prefix and need to use “subtraction (inverse operation)” to do exclusion, and prefix xor use “the same value xor result is
$0$(The xor of the even number is
$0$) “feature to implement inclusive exclusion.

The “interval evaluation” problem was also summarized in [SOLver] 307. Ranges and retrievals – arrays can be modified.

There are different options for different problems (assuming 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)

Although the “segment tree” solved the most problems, the “segment tree” code was long and the constants were large, so the actual performance was not good. We only consider segment trees if we have to use them.

We use “tree array” and “prefix sum” to solve the problem.

Tree array

We use the “tree array” to record the “xor results” of some sections, and then summarize the “xor results” of sections according to the queries of the queries (perform xor operations) to get the final answer.

Code:

class Solution {
    int n;
    int[] c = new int[100009];
    int lowbit(int x) {
        return x & -x;
    }
    void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) c[i] ^= u;
    }
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans ^= c[i];
        return ans;
    }
    public int[] xorQueries(int[] arr, int[][] qs) {
        n = arr.length;
        int m = qs.length;
        for (int i = 1; i <= n; i++) add(i, arr[i - 1]);
        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            int l = qs[i][0] + 1, r = qs[i][1] + 1;
            ans[i] = query(r) ^ query(l - 1);
        }
        returnans; }}Copy the code

• Time complexity: letarrThe array length isn.qsThe length of the array ism. The complexity of creating a tree array is
  $O(n\log{n})$; The query complexity is
  $O(m\log{n})$. The overall complexity is
  $O((n + m) \log{n})$
• Space complexity: O(n)O(n)O(n)

The prefix xor

The query complexity of “tree array” is O(log⁡n)O(\log{n})O(logn).

Although “tree array” can also be created O(n)O(n)O(n), the use of “prefix xOR” is mainly to reduce the complexity of the query.

Code:

class Solution {
    public int[] xorQueries(int[] arr, int[][] qs) {
        int n = arr.length, m = qs.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] ^ arr[i - 1];
        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            int l = qs[i][0] + 1, r = qs[i][1] + 1;
            ans[i] = sum[r] ^ sum[l - 1];
        }
        returnans; }}Copy the code

• Time complexity: letarrThe array length isn.qsThe length of the array ism. The preprocessing of prefixes and arrays is
  $O(n)$; The query complexity is
  $O(m)$. The overall complexity is
  $O(n + m)$
• Space complexity: O(n)O(n)O(n)

The last

This is the No.1310 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode as of the start date, some of which have locks.

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.