You are given two 0-indexed arrays nums1 and nums2 and a 2D array queries of queries. There are three types of queries:
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.queries[i] = [2, p, 0]. For every index 0 <= i < n, set nums2[i] = nums2[i] + nums1[i] * p.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 <= 105nums1.length = nums2.length1 <= queries.length <= 105queries[i].length = 30 <= l <= r <= nums1.length - 10 <= p <= 1060 <= nums1[i] <= 10 <= nums2[i] <= 109Problem Overview: You maintain two arrays. Queries flip bits in nums1, add a multiple of the number of ones in nums1 to nums2, or ask for the total sum of nums2. The challenge is handling frequent range updates and keeping the count of ones available instantly for later queries.
Approach 1: Naive Iterative Approach (O(n) per update, O(q·n) overall)
The straightforward method directly applies each query. For a flip operation, iterate through the specified range in nums1 and toggle each bit. For the second query type, count the number of ones in nums1 by iterating through the array, then add p * ones to a running total of nums2. This approach relies purely on array traversal using basic operations on an array. It works for small inputs but becomes too slow when both the array size and number of queries grow large.
Approach 2: Segment Tree Optimization for Range Updates (O((n + q) log n) time, O(n) space)
The optimized approach stores the count of ones in nums1 using a segment tree. Each node tracks how many ones exist in its range. When a query flips a range, instead of updating each element individually, the tree performs a lazy range flip: the stored count becomes segment_length - current_ones. Lazy propagation postpones updates to children until necessary, keeping operations efficient.
For the second query type, the algorithm reads the total number of ones directly from the root of the tree in O(1). Multiply that value by p and add it to a running sum representing the total of nums2. Since the problem only asks for the sum of nums2, there is no need to update each element individually. The third query simply outputs this stored sum. This design converts expensive full-array operations into logarithmic updates and constant-time queries.
Recommended for interviews: Interviewers expect the Segment Tree with lazy propagation solution. The brute-force iteration shows you understand the mechanics of the queries, but it does not scale. Using a segment tree to maintain the number of ones while supporting fast range flips demonstrates strong knowledge of range query data structures.
This approach involves diving directly into the queries and processing them straightforwardly. We iterate through the queries and process each based on their type. This is simple to implement but not optimized for large input sizes, particularly for type 1 queries which require range flips.
The function handleQueriesNaive iterates through each query and performs the required operations based on its type. For type 1 queries, it flips the bits between indices l and r using a helper function flip. For type 2 queries, it updates nums2 by incrementing each element with the value of nums1[i] multiplied by p (l in the query array). For type 3 queries, it calculates and stores the sum of nums2 in the results array.
Time Complexity: O(n * m) in the worst case, where n is the length of nums1 and m is the number of queries, specifically when dealing with range flips and updates.
Space Complexity: O(q) for storing the results of type 3 queries, where q is the number of those queries.
Using a Segment Tree allows us to efficiently handle range updates, particularly suitable for type 1 queries that require flipping elements over a range. This optimization ensures that updates and queries are both handled in logarithmic time.
This solution uses a Segment Tree to manage range updates efficiently. The segment tree supports lazy propagation, which allows us to update ranges of nums1 in logarithmic time. We utilize the tree to keep track of the number of ones in any segment, which is used when applying type 2 queries.
C++
Time Complexity: O(log n) per update and query on the segment tree, much improved for large ranges.
Space Complexity: O(n) for the segment tree structure.
According to the problem description:
1 is to reverse all numbers in the index range [l,..r] of array nums1, that is, change 0 to 1 and 1 to 0.3 is to sum all numbers in array nums2.2 is to add the sum of all numbers in array nums2 with p times the sum of all numbers in array nums1, that is, sum(nums2) = sum(nums2) + p * sum(nums1).Therefore, we actually only need to maintain the segment sum of array nums1, which can be implemented through a segment tree.
We define each node of the segment tree as Node, each node contains the following attributes:
l: The left endpoint of the node, the index starts from 1.r: The right endpoint of the node, the index starts from 1.s: The segment sum of the node.lazy: The lazy tag of the node.The segment tree mainly has the following operations:
build(u, l, r): Build the segment tree.pushdown(u): Propagate the lazy tag.pushup(u): Update the information of the parent node with the information of the child nodes.modify(u, l, r): Modify the segment sum. In this problem, it is to reverse each number in the segment, so the segment sum s = r - l + 1 - s.query(u, l, r): Query the segment sum.First, calculate the sum of all numbers in array nums2, denoted as s.
When executing operation 1, we only need to call modify(1, l + 1, r + 1).
When executing operation 2, we update s = s + p times query(1, 1, n).
When executing operation 3, we just need to add s to the answer array.
The time complexity is O(n + m times log n), and the space complexity is O(n). Where n and m are the lengths of arrays nums1 and queries respectively.
| Approach | Complexity |
|---|---|
| Naive Iterative Approach | Time Complexity: O(n * m) in the worst case, where n is the length of nums1 and m is the number of queries, specifically when dealing with range flips and updates.
|
| Segment Tree Optimization for Range Updates | Time Complexity: O(log n) per update and query on the segment tree, much improved for large ranges. |
| Segment Tree | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Iterative Approach | O(q · n) | O(1) | Small arrays or when implementing a quick baseline solution |
| Segment Tree with Lazy Propagation | O((n + q) log n) | O(n) | Large input sizes with many range flips and queries |
Handling Sum Queries After Update || Leetcode-2569 || C++, Java & Python • Aryan Mittal • 1,681 views views
Watch 5 more video solutions →Practice Handling Sum Queries After Update with our built-in code editor and test cases.
Practice on FleetCode