2569. Handling Sum Queries After Update LeetCode Solution

In this guide, you will get 2569. Handling Sum Queries After Update LeetCode Solution with the best time and space complexity. The solution to Handling Sum Queries After Update problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Handling Sum Queries After Update solution in C++
Handling Sum Queries After Update solution in Java
Handling Sum Queries After Update solution in Python
Additional Resources

2569. Handling Sum Queries After Update LeetCode Solution image

Problem Statement of Handling Sum Queries After Update

You are given two 0-indexed arrays nums1 and nums2 and a 2D array queries of queries. There are three types of queries:

For a query of type 1, queries[i] = [1, l, r]. Flip the values from 0 to 1 and from 1 to 0 in nums1 from index l to index r. Both l and r are 0-indexed.
For a query of type 2, queries[i] = [2, p, 0]. For every index 0 <= i < n, set nums2[i] = nums2[i] + nums1[i] * p.
For a query of type 3, queries[i] = [3, 0, 0]. Find the sum of the elements in nums2.

Return an array containing all the answers to the third type queries.

Example 1:

Input: nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]]
Output: [3]
Explanation: After the first query nums1 becomes [1,1,1]. After the second query, nums2 becomes [1,1,1], so the answer to the third query is 3. Thus, [3] is returned.

Example 2:

Input: nums1 = [1], nums2 = [5], queries = [[2,0,0],[3,0,0]]
Output: [5]
Explanation: After the first query, nums2 remains [5], so the answer to the second query is 5. Thus, [5] is returned.

Constraints:

1 <= nums1.length,nums2.length <= 105
nums1.length = nums2.length
1 <= queries.length <= 105
queries[i].length = 3
0 <= l <= r <= nums1.length – 1
0 <= p <= 106
0 <= nums1[i] <= 1
0 <= nums2[i] <= 109

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(4n) = O(n)

2569. Handling Sum Queries After Update LeetCode Solution in C++

class LazySegmentTree {
 public:
  explicit LazySegmentTree(const vector<int>& nums) {
    const int n = nums.size();
    tree.resize(4 * n);
    lazy.resize(4 * n);
    build(nums, 0, 0, n - 1);
  }

  //            i := index of the current node
  // [start, end] := range of the current node
  //       [l, r] := range of the query
  void updateRange(int i, int start, int end, int l, int r) {
    if (lazy[i])
      propogate(i, start, end);
    if (start > r || end < l)
      return;
    if (start >= l && end <= r) {
      flip(i, start, end);
      return;
    }
    const int mid = (start + end) / 2;
    updateRange(i * 2 + 1, start, mid, l, r);
    updateRange(i * 2 + 2, mid + 1, end, l, r);
    tree[i] = tree[2 * i + 1] + tree[2 * i + 2];
  }

  int getTreeSum() const {
    return tree[0];
  }

 private:
  vector<int> tree;
  vector<bool> lazy;

  void build(const vector<int>& nums, int i, int start, int end) {
    if (start == end) {
      tree[i] = nums[start];
      return;
    }
    const int mid = (start + end) / 2;
    build(nums, 2 * i + 1, start, mid);
    build(nums, 2 * i + 2, mid + 1, end);
    tree[i] = tree[2 * i + 1] + tree[2 * i + 2];
  }

  void propogate(int i, int start, int end) {
    flip(i, start, end);
    lazy[i] = false;
  }

  void flip(int i, int start, int end) {
    tree[i] = (end - start + 1) - tree[i];  // Flip 0/1.
    if (start < end) {
      lazy[2 * i + 1] = !lazy[2 * i + 1];
      lazy[2 * i + 2] = !lazy[2 * i + 2];
    }
  }
};

class Solution {
 public:
  vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2,
                                vector<vector<int>>& queries) {
    vector<long long> ans;
    LazySegmentTree tree(nums1);
    long sumNums2 = accumulate(nums2.begin(), nums2.end(), 0L);

    for (const vector<int>& query : queries) {
      const int type = query[0];
      const int l = query[1];
      const int r = query[2];
      if (type == 1) {
        tree.updateRange(0, 0, nums1.size() - 1, l, r);
      } else if (type == 2) {
        sumNums2 += static_cast<long>(l) * tree.getTreeSum();
      } else {  // type == 3
        ans.push_back(sumNums2);
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */