Problem

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.

Examples

Example 1

1
2
3

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

1
2
3

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 <= 10^5
  • nums1.length = nums2.length
  • 1 <= queries.length <= 10^5
  • queries[i].length = 3
  • 0 <= l <= r <= nums1.length - 1
  • 0 <= p <= 10^6
  • 0 <= nums1[i] <= 1
  • 0 <= nums2[i] <= 10^9

Solution

Method 1 – Segment Tree with Lazy Propagation

Intuition

To efficiently handle range flip and sum queries on large arrays, we use a segment tree with lazy propagation. This allows us to flip ranges and count 1s in nums1 in logarithmic time, which is crucial for fast updates and queries.

Approach

  1. Build a segment tree to maintain the count of 1s in nums1 with lazy propagation for range flips.
  2. For type 1 queries, flip the range [l, r] in nums1 using the segment tree.
  3. For type 2 queries, add p * (number of 1s in nums1) to a running sum for nums2 (since only positions with 1 in nums1 are updated).
  4. For type 3 queries, output the current sum of nums2.
  5. Avoid updating the entire nums2 array for type 2 queries; instead, keep a running sum and update only when needed.

Code

 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

class Solution {
public:
    vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        int n = nums1.size();
        vector<long long> ans;
        vector<long long> seg(4 * n), lazy(4 * n);
        function<void(int,int,int)> build = [&](int node, int l, int r) {
            if (l == r) seg[node] = nums1[l];
            else {
                int m = (l + r) / 2;
                build(2*node, l, m);
                build(2*node+1, m+1, r);
                seg[node] = seg[2*node] + seg[2*node+1];
            }
        };
        function<void(int,int,int,int,int)> flip = [&](int node, int l, int r, int ql, int qr) {
            if (lazy[node]) {
                seg[node] = (r-l+1) - seg[node];
                if (l != r) lazy[2*node] ^= 1, lazy[2*node+1] ^= 1;
                lazy[node] = 0;
            }
            if (qr < l || r < ql) return;
            if (ql <= l && r <= qr) {
                seg[node] = (r-l+1) - seg[node];
                if (l != r) lazy[2*node] ^= 1, lazy[2*node+1] ^= 1;
                return;
            }
            int m = (l + r) / 2;
            flip(2*node, l, m, ql, qr);
            flip(2*node+1, m+1, r, ql, qr);
            seg[node] = seg[2*node] + seg[2*node+1];
        };
        function<long long(int,int,int,int,int)> query = [&](int node, int l, int r, int ql, int qr) {
            if (lazy[node]) {
                seg[node] = (r-l+1) - seg[node];
                if (l != r) lazy[2*node] ^= 1, lazy[2*node+1] ^= 1;
                lazy[node] = 0;
            }
            if (qr < l || r < ql) return 0LL;
            if (ql <= l && r <= qr) return seg[node];
            int m = (l + r) / 2;
            return query(2*node, l, m, ql, qr) + query(2*node+1, m+1, r, ql, qr);
        };
        build(1, 0, n-1);
        long long sum2 = 0;
        for (int x : nums2) sum2 += x;
        for (auto& q : queries) {
            if (q[0] == 1) flip(1, 0, n-1, q[1], q[2]);
            else if (q[0] == 2) {
                long long cnt = query(1, 0, n-1, 0, n-1);
                sum2 += cnt * q[1];
            } else ans.push_back(sum2);
        }
        return ans;
    }
};
 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

type segTree struct {
    n int
    seg, lazy []int
}
func newSegTree(a []int) *segTree {
    n := len(a)
    st := &segTree{n, make([]int, 4*n), make([]int, 4*n)}
    var build func(int, int, int)
    build = func(node, l, r int) {
        if l == r {
            st.seg[node] = a[l]
        } else {
            m := (l + r) / 2
            build(2*node, l, m)
            build(2*node+1, m+1, r)
            st.seg[node] = st.seg[2*node] + st.seg[2*node+1]
        }
    }
    build(1, 0, n-1)
    return st
}
func (st *segTree) push(node, l, r int) {
    if st.lazy[node] != 0 {
        st.seg[node] = (r-l+1) - st.seg[node]
        if l != r {
            st.lazy[2*node] ^= 1
            st.lazy[2*node+1] ^= 1
        }
        st.lazy[node] = 0
    }
}
func (st *segTree) flip(node, l, r, ql, qr int) {
    st.push(node, l, r)
    if qr < l || r < ql { return }
    if ql <= l && r <= qr {
        st.seg[node] = (r-l+1) - st.seg[node]
        if l != r {
            st.lazy[2*node] ^= 1
            st.lazy[2*node+1] ^= 1
        }
        return
    }
    m := (l + r) / 2
    st.flip(2*node, l, m, ql, qr)
    st.flip(2*node+1, m+1, r, ql, qr)
    st.seg[node] = st.seg[2*node] + st.seg[2*node+1]
}
func (st *segTree) query(node, l, r, ql, qr int) int {
    st.push(node, l, r)
    if qr < l || r < ql { return 0 }
    if ql <= l && r <= qr { return st.seg[node] }
    m := (l + r) / 2
    return st.query(2*node, l, m, ql, qr) + st.query(2*node+1, m+1, r, ql, qr)
}
func handleQuery(nums1, nums2 []int, queries [][]int) []int64 {
    n := len(nums1)
    st := newSegTree(nums1)
    var sum2 int64
    for _, x := range nums2 { sum2 += int64(x) }
    var ans []int64
    for _, q := range queries {
        if q[0] == 1 {
            st.flip(1, 0, n-1, q[1], q[2])
        } else if q[0] == 2 {
            cnt := st.query(1, 0, n-1, 0, n-1)
            sum2 += int64(cnt) * int64(q[1])
        } else {
            ans = append(ans, sum2)
        }
    }
    return ans
}
 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

class Solution {
    public List<Long> handleQuery(int[] nums1, int[] nums2, int[][] queries) {
        int n = nums1.length;
        List<Long> ans = new ArrayList<>();
        long[] seg = new long[4 * n], lazy = new long[4 * n];
        build(nums1, seg, 1, 0, n-1);
        long sum2 = 0;
        for (int x : nums2) sum2 += x;
        for (int[] q : queries) {
            if (q[0] == 1) flip(seg, lazy, 1, 0, n-1, q[1], q[2]);
            else if (q[0] == 2) {
                long cnt = query(seg, lazy, 1, 0, n-1, 0, n-1);
                sum2 += cnt * q[1];
            } else ans.add(sum2);
        }
        return ans;
    }
    void build(int[] a, long[] seg, int node, int l, int r) {
        if (l == r) seg[node] = a[l];
        else {
            int m = (l + r) / 2;
            build(a, seg, 2*node, l, m);
            build(a, seg, 2*node+1, m+1, r);
            seg[node] = seg[2*node] + seg[2*node+1];
        }
    }
    void flip(long[] seg, long[] lazy, int node, int l, int r, int ql, int qr) {
        if (lazy[node] != 0) {
            seg[node] = (r-l+1) - seg[node];
            if (l != r) {
                lazy[2*node] ^= 1;
                lazy[2*node+1] ^= 1;
            }
            lazy[node] = 0;
        }
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            seg[node] = (r-l+1) - seg[node];
            if (l != r) {
                lazy[2*node] ^= 1;
                lazy[2*node+1] ^= 1;
            }
            return;
        }
        int m = (l + r) / 2;
        flip(seg, lazy, 2*node, l, m, ql, qr);
        flip(seg, lazy, 2*node+1, m+1, r, ql, qr);
        seg[node] = seg[2*node] + seg[2*node+1];
    }
    long query(long[] seg, long[] lazy, int node, int l, int r, int ql, int qr) {
        if (lazy[node] != 0) {
            seg[node] = (r-l+1) - seg[node];
            if (l != r) {
                lazy[2*node] ^= 1;
                lazy[2*node+1] ^= 1;
            }
            lazy[node] = 0;
        }
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return seg[node];
        int m = (l + r) / 2;
        return query(seg, lazy, 2*node, l, m, ql, qr) + query(seg, lazy, 2*node+1, m+1, r, ql, qr);
    }
}
 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

class Solution {
    fun handleQuery(nums1: IntArray, nums2: IntArray, queries: Array<IntArray>): List<Long> {
        val n = nums1.size
        val seg = LongArray(4 * n)
        val lazy = LongArray(4 * n)
        fun build(node: Int, l: Int, r: Int) {
            if (l == r) seg[node] = nums1[l].toLong()
            else {
                val m = (l + r) / 2
                build(2*node, l, m)
                build(2*node+1, m+1, r)
                seg[node] = seg[2*node] + seg[2*node+1]
            }
        }
        fun push(node: Int, l: Int, r: Int) {
            if (lazy[node] != 0L) {
                seg[node] = (r-l+1) - seg[node]
                if (l != r) {
                    lazy[2*node] = lazy[2*node] xor 1L
                    lazy[2*node+1] = lazy[2*node+1] xor 1L
                }
                lazy[node] = 0L
            }
        }
        fun flip(node: Int, l: Int, r: Int, ql: Int, qr: Int) {
            push(node, l, r)
            if (qr < l || r < ql) return
            if (ql <= l && r <= qr) {
                seg[node] = (r-l+1) - seg[node]
                if (l != r) {
                    lazy[2*node] = lazy[2*node] xor 1L
                    lazy[2*node+1] = lazy[2*node+1] xor 1L
                }
                return
            }
            val m = (l + r) / 2
            flip(2*node, l, m, ql, qr)
            flip(2*node+1, m+1, r, ql, qr)
            seg[node] = seg[2*node] + seg[2*node+1]
        }
        fun query(node: Int, l: Int, r: Int, ql: Int, qr: Int): Long {
            push(node, l, r)
            if (qr < l || r < ql) return 0L
            if (ql <= l && r <= qr) return seg[node]
            val m = (l + r) / 2
            return query(2*node, l, m, ql, qr) + query(2*node+1, m+1, r, ql, qr)
        }
        build(1, 0, n-1)
        var sum2 = nums2.fold(0L) { acc, x -> acc + x }
        val ans = mutableListOf<Long>()
        for (q in queries) {
            when (q[0]) {
                1 -> flip(1, 0, n-1, q[1], q[2])
                2 -> {
                    val cnt = query(1, 0, n-1, 0, n-1)
                    sum2 += cnt * q[1]
                }
                3 -> ans.add(sum2)
            }
        }
        return ans
    }
}
 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

class Solution:
    def handleQuery(self, nums1: list[int], nums2: list[int], queries: list[list[int]]) -> list[int]:
        n = len(nums1)
        class SegTree:
            def __init__(self, a: list[int]):
                self.n = len(a)
                self.seg = [0] * (4 * self.n)
                self.lazy = [0] * (4 * self.n)
                self.build(1, 0, self.n-1, a)
            def build(self, node: int, l: int, r: int, a: list[int]):
                if l == r:
                    self.seg[node] = a[l]
                else:
                    m = (l + r) // 2
                    self.build(2*node, l, m, a)
                    self.build(2*node+1, m+1, r, a)
                    self.seg[node] = self.seg[2*node] + self.seg[2*node+1]
            def push(self, node: int, l: int, r: int):
                if self.lazy[node]:
                    self.seg[node] = (r-l+1) - self.seg[node]
                    if l != r:
                        self.lazy[2*node] ^= 1
                        self.lazy[2*node+1] ^= 1
                    self.lazy[node] = 0
            def flip(self, node: int, l: int, r: int, ql: int, qr: int):
                self.push(node, l, r)
                if qr < l or r < ql:
                    return
                if ql <= l and r <= qr:
                    self.seg[node] = (r-l+1) - self.seg[node]
                    if l != r:
                        self.lazy[2*node] ^= 1
                        self.lazy[2*node+1] ^= 1
                    return
                m = (l + r) // 2
                self.flip(2*node, l, m, ql, qr)
                self.flip(2*node+1, m+1, r, ql, qr)
                self.seg[node] = self.seg[2*node] + self.seg[2*node+1]
            def query(self, node: int, l: int, r: int, ql: int, qr: int) -> int:
                self.push(node, l, r)
                if qr < l or r < ql:
                    return 0
                if ql <= l and r <= qr:
                    return self.seg[node]
                m = (l + r) // 2
                return self.query(2*node, l, m, ql, qr) + self.query(2*node+1, m+1, r, ql, qr)
        st = SegTree(nums1)
        sum2 = sum(nums2)
        ans = []
        for q in queries:
            if q[0] == 1:
                st.flip(1, 0, n-1, q[1], q[2])
            elif q[0] == 2:
                cnt = st.query(1, 0, n-1, 0, n-1)
                sum2 += cnt * q[1]
            else:
                ans.append(sum2)
        return ans
 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
77

struct Solution;
impl Solution {
    pub fn handle_query(nums1: Vec<i32>, nums2: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i64> {
        struct SegTree {
            n: usize,
            seg: Vec<i64>,
            lazy: Vec<i64>,
        }
        impl SegTree {
            fn new(a: &[i32]) -> Self {
                let n = a.len();
                let mut seg = vec![0; 4*n];
                let mut lazy = vec![0; 4*n];
                fn build(node: usize, l: usize, r: usize, seg: &mut [i64], a: &[i32]) {
                    if l == r {
                        seg[node] = a[l] as i64;
                    } else {
                        let m = (l + r) / 2;
                        build(2*node, l, m, seg, a);
                        build(2*node+1, m+1, r, seg, a);
                        seg[node] = seg[2*node] + seg[2*node+1];
                    }
                }
                build(1, 0, n-1, &mut seg, a);
                Self { n, seg, lazy }
            }
            fn push(&mut self, node: usize, l: usize, r: usize) {
                if self.lazy[node] != 0 {
                    self.seg[node] = (r-l+1) as i64 - self.seg[node];
                    if l != r {
                        self.lazy[2*node] ^= 1;
                        self.lazy[2*node+1] ^= 1;
                    }
                    self.lazy[node] = 0;
                }
            }
            fn flip(&mut self, node: usize, l: usize, r: usize, ql: usize, qr: usize) {
                self.push(node, l, r);
                if qr < l || r < ql { return; }
                if ql <= l && r <= qr {
                    self.seg[node] = (r-l+1) as i64 - self.seg[node];
                    if l != r {
                        self.lazy[2*node] ^= 1;
                        self.lazy[2*node+1] ^= 1;
                    }
                    return;
                }
                let m = (l + r) / 2;
                self.flip(2*node, l, m, ql, qr);
                self.flip(2*node+1, m+1, r, ql, qr);
                self.seg[node] = self.seg[2*node] + self.seg[2*node+1];
            }
            fn query(&mut self, node: usize, l: usize, r: usize, ql: usize, qr: usize) -> i64 {
                self.push(node, l, r);
                if qr < l || r < ql { return 0; }
                if ql <= l && r <= qr { return self.seg[node]; }
                let m = (l + r) / 2;
                self.query(2*node, l, m, ql, qr) + self.query(2*node+1, m+1, r, ql, qr)
            }
        }
        let n = nums1.len();
        let mut st = SegTree::new(&nums1);
        let mut sum2: i64 = nums2.iter().map(|&x| x as i64).sum();
        let mut ans = vec![];
        for q in queries {
            if q[0] == 1 {
                st.flip(1, 0, n-1, q[1] as usize, q[2] as usize);
            } else if q[0] == 2 {
                let cnt = st.query(1, 0, n-1, 0, n-1);
                sum2 += cnt * q[1] as i64;
            } else {
                ans.push(sum2);
            }
        }
        ans
    }
}
 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

class Solution {
    handleQuery(nums1: number[], nums2: number[], queries: number[][]): number[] {
        const n = nums1.length;
        const seg = new Array(4 * n).fill(0);
        const lazy = new Array(4 * n).fill(0);
        function build(node: number, l: number, r: number) {
            if (l === r) seg[node] = nums1[l];
            else {
                const m = (l + r) >> 1;
                build(2*node, l, m);
                build(2*node+1, m+1, r);
                seg[node] = seg[2*node] + seg[2*node+1];
            }
        }
        function push(node: number, l: number, r: number) {
            if (lazy[node]) {
                seg[node] = (r-l+1) - seg[node];
                if (l !== r) {
                    lazy[2*node] ^= 1;
                    lazy[2*node+1] ^= 1;
                }
                lazy[node] = 0;
            }
        }
        function flip(node: number, l: number, r: number, ql: number, qr: number) {
            push(node, l, r);
            if (qr < l || r < ql) return;
            if (ql <= l && r <= qr) {
                seg[node] = (r-l+1) - seg[node];
                if (l !== r) {
                    lazy[2*node] ^= 1;
                    lazy[2*node+1] ^= 1;
                }
                return;
            }
            const m = (l + r) >> 1;
            flip(2*node, l, m, ql, qr);
            flip(2*node+1, m+1, r, ql, qr);
            seg[node] = seg[2*node] + seg[2*node+1];
        }
        function query(node: number, l: number, r: number, ql: number, qr: number): number {
            push(node, l, r);
            if (qr < l || r < ql) return 0;
            if (ql <= l && r <= qr) return seg[node];
            const m = (l + r) >> 1;
            return query(2*node, l, m, ql, qr) + query(2*node+1, m+1, r, ql, qr);
        }
        build(1, 0, n-1);
        let sum2 = nums2.reduce((a, b) => a + b, 0);
        const ans: number[] = [];
        for (const q of queries) {
            if (q[0] === 1) flip(1, 0, n-1, q[1], q[2]);
            else if (q[0] === 2) {
                const cnt = query(1, 0, n-1, 0, n-1);
                sum2 += cnt * q[1];
            } else ans.push(sum2);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(q log n) for q queries and n elements, since each update/query on the segment tree is O(log n).
  • 🧺 Space complexity: O(n) for the segment tree and auxiliary arrays.