#2569

Hard

LeetCode Problem Workspace

Handling Sum Queries After Update

Solve the Handling Sum Queries After Update problem using arrays and segment trees with lazy propagation for efficiency.

array segment tree

Problem Statement

You are given two 0-indexed integer arrays nums1 and nums2 of the same length, and a 2D array queries containing multiple operations. Each query is represented by three integers, and there are three types of operations: flip all elements in nums1 within a specified range, add nums1 values multiplied by a given number to nums2, and calculate the total sum of nums2.

Return an array containing the results of all type 3 queries. For example, given nums1 = [1,0,1], nums2 = [0,0,0], and queries = [[1,1,1],[2,1,0],[3,0,0]], the output is [3] because after flipping and adding operations, nums2 sums to 3 at the third query. Apply the operations in order and collect the sum answers efficiently.

Examples

Example 1

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

Output: [3]

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]

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

Solution Approach

Use Lazy Segment Tree for nums1 Flips

Implement a segment tree with lazy propagation to efficiently flip ranges in nums1. Store counts of ones and propagate flip operations lazily to avoid repeated updates on every element, reducing time complexity from linear per query to logarithmic.

Increment nums2 Using Flipped Counts

When processing type 2 queries, use the segment tree to get the current count of ones in nums1, multiply by the query value, and add to nums2. This avoids iterating through nums1 and ensures range-dependent updates are applied efficiently.

Answer Type 3 Queries Quickly

Maintain a running sum of nums2 or use a segment tree to compute the total sum efficiently after updates. Each type 3 query reads this sum directly, ensuring queries are resolved in constant or logarithmic time instead of iterating through the entire array.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O((n+q) log n) due to segment tree operations for range flips and sum queries, where n is array length and q is number of queries. Space complexity is O(n) for storing the segment tree and lazy markers.

What Interviewers Usually Probe

Look for candidates using naive iteration versus segment tree optimization.
Expect awareness of lazy propagation to handle large ranges efficiently.
Check understanding of combining array operations with segment tree updates.

Common Pitfalls or Variants

Common pitfalls

Updating nums1 naively for every flip causes TLE on large inputs.
Adding to nums2 without referencing the current nums1 ones count leads to incorrect results.
Computing sum of nums2 from scratch each type 3 query is inefficient.

Follow-up variants

Compute prefix sums instead of using a segment tree for smaller constraints.
Handle multiple nums2 arrays updated simultaneously using the same nums1 flips.
Support dynamic length changes in nums1 and nums2 with additional insert/delete queries.

FAQ

What is the recommended data structure for Handling Sum Queries After Update?

Use a lazy segment tree to handle range flips in nums1 efficiently and to query counts for updating nums2.

Can I solve this problem with a simple for loop?

Naive loops will exceed time limits on large inputs; segment trees are needed to keep operations efficient.

How do I compute the sum of nums2 after multiple updates?

Maintain a running sum or a segment tree over nums2 to quickly retrieve sums for type 3 queries.

Why is lazy propagation necessary in this problem?

Flipping ranges repeatedly without lazy propagation results in repeated work and slow performance; lazy marks delay updates until needed.

Does this problem pattern appear in other array plus segment tree scenarios?

Yes, any problem involving range flips or additions followed by sum queries fits this exact array plus segment tree pattern.

terminal

Solution

Solution 1: Segment Tree

According to the problem description:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

class Node:
    def __init__(self):
        self.l = self.r = 0
        self.s = self.lazy = 0


class SegmentTree:
    def __init__(self, nums):
        self.nums = nums
        n = len(nums)
        self.tr = [Node() for _ in range(n << 2)]
        self.build(1, 1, n)

    def build(self, u, l, r):
        self.tr[u].l, self.tr[u].r = l, r
        if l == r:
            self.tr[u].s = self.nums[l - 1]
            return
        mid = (l + r) >> 1
        self.build(u << 1, l, mid)
        self.build(u << 1 | 1, mid + 1, r)
        self.pushup(u)

    def modify(self, u, l, r):
        if self.tr[u].l >= l and self.tr[u].r <= r:
            self.tr[u].lazy ^= 1
            self.tr[u].s = self.tr[u].r - self.tr[u].l + 1 - self.tr[u].s
            return
        self.pushdown(u)
        mid = (self.tr[u].l + self.tr[u].r) >> 1
        if l <= mid:
            self.modify(u << 1, l, r)
        if r > mid:
            self.modify(u << 1 | 1, l, r)
        self.pushup(u)

    def query(self, u, l, r):
        if self.tr[u].l >= l and self.tr[u].r <= r:
            return self.tr[u].s
        self.pushdown(u)
        mid = (self.tr[u].l + self.tr[u].r) >> 1
        res = 0
        if l <= mid:
            res += self.query(u << 1, l, r)
        if r > mid:
            res += self.query(u << 1 | 1, l, r)
        return res

    def pushup(self, u):
        self.tr[u].s = self.tr[u << 1].s + self.tr[u << 1 | 1].s

    def pushdown(self, u):
        if self.tr[u].lazy:
            mid = (self.tr[u].l + self.tr[u].r) >> 1
            self.tr[u << 1].s = mid - self.tr[u].l + 1 - self.tr[u << 1].s
            self.tr[u << 1].lazy ^= 1
            self.tr[u << 1 | 1].s = self.tr[u].r - mid - self.tr[u << 1 | 1].s
            self.tr[u << 1 | 1].lazy ^= 1
            self.tr[u].lazy ^= 1


class Solution:
    def handleQuery(
        self, nums1: List[int], nums2: List[int], queries: List[List[int]]
    ) -> List[int]:
        tree = SegmentTree(nums1)
        s = sum(nums2)
        ans = []
        for op, a, b in queries:
            if op == 1:
                tree.modify(1, a + 1, b + 1)
            elif op == 2:
                s += a * tree.query(1, 1, len(nums1))
            else:
                ans.append(s)
        return ans

Continue Practicing

#2659 make array empty #2426 number of pairs satisfying inequality #2407 longest increasing subsequence ii