Skip to main content
Talentd

Handling Sum Queries After Update - Solution & Explanation

HardArraySegment Tree20 min readAsked at: Trilogy
Practice this problem

Problem Statement

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

  1. 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.
  2. 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.
  3. 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

Approach Overview

Problem 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.

Approach 1: Naive Iterative Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Segment Tree Optimization for Range Updates

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.

Code

C++

C++

Complexity

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.

Try this approach in the editor →

Approach 3: Segment Tree

According to the problem description:

  • Operation 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.
  • Operation 3 is to sum all numbers in array nums2.
  • Operation 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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(q) for storing the results of type 3 queries, where q is the number of those queries.

Segment Tree Optimization for Range Updates

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.

Segment Tree—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Iterative ApproachO(q · n)O(1)Small arrays or when implementing a quick baseline solution
Segment Tree with Lazy PropagationO((n + q) log n)O(n)Large input sizes with many range flips and queries

Video Solution

Handling Sum Queries After Update || Leetcode-2569 || C++, Java & Python • Aryan Mittal • 1,754 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Handling Sum Queries After Update easy or hard?
Handling Sum Queries After Update is classified as a Hard problem on LeetCode. The difficulty comes from combining range updates, lazy propagation, and query optimization while avoiding repeated full-array operations.
Handling Sum Queries After Update Python/Java solution
Implement the optimized solution by building a segment tree that stores the count of ones for each range. Range flip operations use lazy propagation, and a variable tracks the running sum of nums2. The same logic translates cleanly to Python, Java, and C++ implementations.
What is the best approach for Handling Sum Queries After Update?
The most efficient solution uses a Segment Tree with lazy propagation to track the number of ones in nums1. Range flip operations update the tree in O(log n), and the total count of ones is always available at the root. This allows type‑2 queries to update the sum in constant time.
How to solve Handling Sum Queries After Update in O((n+q) log n)?
Build a segment tree over nums1 that stores the count of ones in each segment. Use lazy propagation to flip bits in a range efficiently by converting the stored count to segment_length minus current_ones. Maintain a running sum of nums2 and update it using the ones count whenever a type‑2 query appears.
Is Handling Sum Queries After Update asked at Google/Amazon/Meta?
Problems involving segment trees and lazy propagation frequently appear in interviews at companies like Google, Amazon, and Meta. This specific pattern—range updates combined with aggregate queries—is a classic advanced data structure interview topic.
What data structure is used in Handling Sum Queries After Update?
The key data structure is a Segment Tree with lazy propagation. It efficiently handles range bit flips while maintaining the count of ones needed to compute updates to the total sum of nums2.
What is the time complexity of Handling Sum Queries After Update?
The optimal approach runs in O((n + q) log n) time using a segment tree. Each range flip update takes O(log n), while reading the total number of ones and processing sum queries is O(1). Space complexity is O(n) for the tree structure.

Ready to solve this problem?

Practice Handling Sum Queries After Update with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays