LeetCode 2569 - Handling Sum Queries After Update

This problem gives us two arrays, nums1 and nums2, both of the same length n, along with a list of queries. Each query modifies one of the arrays or asks for information about them.

leetcodehardarraysegment-tree

LeetCode Problem 2569

Difficulty: 🔴 Hard
Topics: Array, Segment Tree

Solution

LeetCode 2569 - Handling Sum Queries After Update

Problem Understanding

This problem gives us two arrays, nums1 and nums2, both of the same length n, along with a list of queries. Each query modifies one of the arrays or asks for information about them.

The important detail is that nums1 only contains binary values, meaning every element is either 0 or 1. The three query types behave differently:

  • Type 1 flips all bits in a subarray of nums1. Every 0 becomes 1, and every 1 becomes 0.
  • Type 2 updates every element of nums2 by adding nums1[i] * p to it.
  • Type 3 asks for the total sum of all values currently in nums2.

The goal is to return the results for all type 3 queries.

A direct implementation may seem straightforward at first, but the constraints are extremely large:

  • Array size can be up to 10^5
  • Number of queries can also be up to 10^5

This means any approach that repeatedly scans entire arrays for updates will become too slow.

The key observation is that type 2 queries do not actually require modifying every element of nums2. Since:

nums2[i] += nums1[i] * p

the total increase to the sum of nums2 is simply:

(number of 1s in nums1) * p

Therefore, instead of storing all updates in nums2, we only need:

  • The current sum of nums2
  • The current count of 1s in nums1

The difficult part becomes efficiently supporting range bit flips while maintaining the number of 1s. That is exactly where a segment tree with lazy propagation becomes useful.

Important edge cases include:

  • Flipping the same range multiple times
  • Arrays of length 1
  • Queries where p = 0
  • Entire array flips
  • Large sequences of overlapping updates

The problem guarantees valid indices and properly formatted queries, so we do not need additional bounds checking.

Approaches

Brute Force Approach

A naive implementation would directly simulate every query.

For type 1 queries:

  • Iterate from l to r
  • Flip each bit individually

For type 2 queries:

  • Iterate through all indices
  • Update each nums2[i]

For type 3 queries:

  • Compute the sum of nums2

This approach is correct because it exactly follows the problem statement. However, it is far too slow.

Suppose we have 10^5 queries and each query processes 10^5 elements. The total complexity becomes:

O(n * q) = O(10^10)

which is infeasible.

Optimal Approach

The optimization comes from recognizing that we never truly need the individual values inside nums2.

For type 2 queries:

nums2[i] += nums1[i] * p

the total increase to the sum is:

p * count_of_ones_in_nums1

So instead of updating the entire array, we maintain only:

  • total_sum = sum(nums2)
  • ones_count = number of 1s in nums1

Now the main challenge becomes efficiently handling range flips in nums1.

A segment tree with lazy propagation solves this efficiently.

Each node stores:

  • The number of 1s in its segment

When flipping a range:

  • The number of 1s becomes:
segment_length - current_ones

Lazy propagation allows postponing updates until necessary, making each operation run in O(log n) time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n * q) O(1) Direct simulation of every query
Optimal O(q log n) O(n) Segment tree with lazy propagation

Algorithm Walkthrough

  1. Initialize the total sum of nums2.

Since type 3 queries only ask for the total sum, we do not need to preserve individual values in nums2. We compute:

total_sum = sum(nums2)
  1. Build a segment tree over nums1.

Each segment tree node stores the number of 1s in its segment.

For example:

nums1 = [1,0,1,1]

The root node stores 3, because there are three 1s. 3. Add lazy propagation support.

Range flips are expensive if handled element by element.

Instead, each node has a lazy flag indicating whether its segment should be flipped later.

When a segment is flipped:

ones = segment_length - ones

and the lazy flag is toggled. 4. Process each query.

For type 1:

  • Perform a range flip on the segment tree
  • Update affected counts automatically

For type 2:

  • Get the current number of 1s from the root node
  • Increase the total sum by:
ones_count * p

For type 3:

  • Append the current total sum to the answer list
  1. Return all recorded answers.

Why it works

The core invariant is that the segment tree root always stores the current total number of 1s in nums1.

Because type 2 queries only depend on how many positions contain 1, we can update the global sum directly without modifying nums2 element by element.

Lazy propagation guarantees that all range flips are correctly represented while avoiding unnecessary repeated updates. Therefore every query produces the correct result efficiently.

Python Solution

from typing import List

class Solution:
    def handleQuery(
        self,
        nums1: List[int],
        nums2: List[int],
        queries: List[List[int]]
    ) -> List[int]:

        n = len(nums1)

        tree = [0] * (4 * n)
        lazy = [False] * (4 * n)

        def build(node: int, left: int, right: int) -> None:
            if left == right:
                tree[node] = nums1[left]
                return

            mid = (left + right) // 2

            build(node * 2, left, mid)
            build(node * 2 + 1, mid + 1, right)

            tree[node] = tree[node * 2] + tree[node * 2 + 1]

        def apply_flip(node: int, left: int, right: int) -> None:
            tree[node] = (right - left + 1) - tree[node]
            lazy[node] = not lazy[node]

        def push(node: int, left: int, right: int) -> None:
            if not lazy[node] or left == right:
                return

            mid = (left + right) // 2

            apply_flip(node * 2, left, mid)
            apply_flip(node * 2 + 1, mid + 1, right)

            lazy[node] = False

        def update(
            node: int,
            left: int,
            right: int,
            query_left: int,
            query_right: int
        ) -> None:

            if query_left <= left and right <= query_right:
                apply_flip(node, left, right)
                return

            push(node, left, right)

            mid = (left + right) // 2

            if query_left <= mid:
                update(
                    node * 2,
                    left,
                    mid,
                    query_left,
                    query_right
                )

            if query_right > mid:
                update(
                    node * 2 + 1,
                    mid + 1,
                    right,
                    query_left,
                    query_right
                )

            tree[node] = tree[node * 2] + tree[node * 2 + 1]

        build(1, 0, n - 1)

        total_sum = sum(nums2)

        answers = []

        for query_type, x, y in queries:

            if query_type == 1:
                update(1, 0, n - 1, x, y)

            elif query_type == 2:
                ones_count = tree[1]
                total_sum += ones_count * x

            else:
                answers.append(total_sum)

        return answers

The implementation starts by building a segment tree over nums1. Each node stores how many 1s exist in its segment.

The apply_flip function performs the key transformation:

tree[node] = segment_length - tree[node]

because flipping bits converts all 1s into 0s and vice versa.

The lazy array tracks deferred flips. When a node has a pending flip, the push function propagates that update to its children only when necessary.

The update function performs range flips in O(log n) time using lazy propagation.

During query processing:

  • Type 1 triggers a segment tree range update
  • Type 2 uses the root value tree[1], which always stores the total number of 1s
  • Type 3 records the current total sum

No explicit updates to nums2 are ever performed after initialization.

Go Solution

func handleQuery(nums1 []int, nums2 []int, queries [][]int) []int64 {
	n := len(nums1)

	tree := make([]int, 4*n)
	lazy := make([]bool, 4*n)

	var build func(node, left, right int)

	build = func(node, left, right int) {
		if left == right {
			tree[node] = nums1[left]
			return
		}

		mid := (left + right) / 2

		build(node*2, left, mid)
		build(node*2+1, mid+1, right)

		tree[node] = tree[node*2] + tree[node*2+1]
	}

	applyFlip := func(node, left, right int) {
		tree[node] = (right - left + 1) - tree[node]
		lazy[node] = !lazy[node]
	}

	var push func(node, left, right int)

	push = func(node, left, right int) {
		if !lazy[node] || left == right {
			return
		}

		mid := (left + right) / 2

		applyFlip(node*2, left, mid)
		applyFlip(node*2+1, mid+1, right)

		lazy[node] = false
	}

	var update func(node, left, right, ql, qr int)

	update = func(node, left, right, ql, qr int) {
		if ql <= left && right <= qr {
			applyFlip(node, left, right)
			return
		}

		push(node, left, right)

		mid := (left + right) / 2

		if ql <= mid {
			update(node*2, left, mid, ql, qr)
		}

		if qr > mid {
			update(node*2+1, mid+1, right, ql, qr)
		}

		tree[node] = tree[node*2] + tree[node*2+1]
	}

	build(1, 0, n-1)

	var totalSum int64

	for _, value := range nums2 {
		totalSum += int64(value)
	}

	answer := []int64{}

	for _, query := range queries {
		queryType := query[0]

		if queryType == 1 {
			update(1, 0, n-1, query[1], query[2])

		} else if queryType == 2 {
			onesCount := tree[1]
			totalSum += int64(onesCount * query[1])

		} else {
			answer = append(answer, totalSum)
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python solution. One important difference is integer handling.

The sum of nums2 can become very large because:

  • nums2[i] can reach 10^9
  • There can be 10^5 elements
  • Additional updates may further increase the total

Therefore the solution uses int64 for the final sum and returned answers.

Go slices are dynamically sized, so the answer list is built using repeated append operations.

Worked Examples

Example 1

nums1 = [1,0,1]
nums2 = [0,0,0]
queries = [[1,1,1],[2,1,0],[3,0,0]]

Initial state:

Variable Value
nums1 [1,0,1]
total_sum 0
ones_count 2

Query 1: [1,1,1]

Flip indices 1 to 1.

nums1 becomes [1,1,1]

Updated state:

Variable Value
ones_count 3
total_sum 0

Query 2: [2,1,0]

Add:

ones_count * p = 3 * 1 = 3

Updated state:

Variable Value
total_sum 3

Conceptually:

nums2 becomes [1,1,1]

Query 3: [3,0,0]

Output current sum:

3

Final answer:

[3]

Example 2

nums1 = [1]
nums2 = [5]
queries = [[2,0,0],[3,0,0]]

Initial state:

Variable Value
ones_count 1
total_sum 5

Query 1: [2,0,0]

Increase:

1 * 0 = 0

No change.

Variable Value
total_sum 5

Query 2: [3,0,0]

Output:

5

Final answer:

[5]

Complexity Analysis

Measure Complexity Explanation
Time O(q log n) Each range flip runs in logarithmic time
Space O(n) Segment tree and lazy arrays require linear space

The segment tree contains approximately 4n nodes, which is standard for recursive segment tree implementations.

Each type 1 query performs a range update using lazy propagation, requiring O(log n) time.

Type 2 and type 3 queries are both O(1) because the root node always stores the current number of 1s.

Test Cases

sol = Solution()

# Example 1
assert sol.handleQuery(
    [1, 0, 1],
    [0, 0, 0],
    [[1, 1, 1], [2, 1, 0], [3, 0, 0]]
) == [3]  # basic flip and sum update

# Example 2
assert sol.handleQuery(
    [1],
    [5],
    [[2, 0, 0], [3, 0, 0]]
) == [5]  # multiplying by zero

# Single element flip
assert sol.handleQuery(
    [0],
    [10],
    [[1, 0, 0], [2, 5, 0], [3, 0, 0]]
) == [15]  # flip 0 to 1 then add

# Multiple overlapping flips
assert sol.handleQuery(
    [1, 1, 0, 0],
    [0, 0, 0, 0],
    [
        [1, 1, 3],
        [1, 0, 2],
        [2, 2, 0],
        [3, 0, 0]
    ]
) == [4]  # validates lazy propagation correctness

# Entire array flip
assert sol.handleQuery(
    [1, 0, 1, 0],
    [1, 1, 1, 1],
    [
        [1, 0, 3],
        [2, 3, 0],
        [3, 0, 0]
    ]
) == [10]  # full range update

# Multiple type 3 queries
assert sol.handleQuery(
    [1, 1],
    [2, 2],
    [
        [3, 0, 0],
        [2, 1, 0],
        [3, 0, 0]
    ]
) == [4, 6]  # repeated reporting

# No flips at all
assert sol.handleQuery(
    [0, 0, 0],
    [1, 2, 3],
    [
        [2, 10, 0],
        [3, 0, 0]
    ]
) == [6]  # zero ones means no increase

# Repeated flips cancel out
assert sol.handleQuery(
    [1, 0],
    [0, 0],
    [
        [1, 0, 1],
        [1, 0, 1],
        [2, 4, 0],
        [3, 0, 0]
    ]
) == [4]  # double flip restores original state
Test Why
Basic example Verifies standard query flow
Multiply by zero Ensures no accidental updates
Single element array Smallest valid input
Overlapping flips Tests lazy propagation correctness
Entire array flip Validates root segment updates
Multiple outputs Ensures answers accumulate correctly
No ones in nums1 Confirms type 2 can add zero
Repeated flips Ensures toggles cancel properly

Edge Cases

Single Element Arrays

When n = 1, the segment tree contains only one meaningful node. Recursive implementations sometimes fail on minimal ranges due to incorrect midpoint handling or unnecessary child propagation.

This implementation safely handles that case because the recursion stops immediately when:

left == right

and lazy propagation does not attempt to push updates further.

Repeated Flips on the Same Range

Flipping the same range twice should restore the original values. This can easily introduce bugs if lazy flags are overwritten instead of toggled.

The implementation correctly handles this with:

lazy[node] = not lazy[node]

which preserves the parity of flips.

Large Sum Values

The total sum of nums2 can become extremely large after many updates. Using standard 32 bit integers may overflow.

The Go solution explicitly uses int64, and Python naturally supports arbitrarily large integers. This guarantees correctness even for maximum constraints.