2569. 更新后处理求和查询

Hard

题目描述

给定两个下标从0开始的数组 nums1 和 nums2，以及一个二维数组 queries 表示查询。有三种类型的查询：

对于类型1的查询，queries[i] = [1, l, r]。将 nums1 从索引 l 到索引 r 的值进行翻转（0变1，1变0）。l 和 r 都是从0开始的索引。
对于类型2的查询，queries[i] = [2, p, 0]。对于每个索引 0 <= i < n，设置 nums2[i] = nums2[i] + nums1[i] * p。
对于类型3的查询，queries[i] = [3, 0, 0]。计算 nums2 中所有元素的和。

返回一个数组，包含所有第三种类型查询的答案。

示例 1：

输入：nums1 = [1,0,1], nums2 = [0,0,0], queries = [[1,1,1],[2,1,0],[3,0,0]]
输出：[3]
解释：第一个查询后 nums1 变成 [1,1,1]。第二个查询后，nums2 变成 [1,1,1]，所以第三个查询的答案是 3。因此返回 [3]。

示例 2：

输入：nums1 = [1], nums2 = [5], queries = [[2,0,0],[3,0,0]]
输出：[5]
解释：第一个查询后，nums2 仍然是 [5]，所以第二个查询的答案是 5。因此返回 [5]。

约束条件：

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

解题思路

这道题需要高效处理三种操作：区间翻转、全局更新和求和查询。关键是选择合适的数据结构来优化这些操作。

思路分析：

暴力解法：直接模拟所有操作，时间复杂度过高，无法通过大数据量测试。
优化分析：
- 类型1操作：需要对nums1进行区间翻转，频繁的区间操作提示使用线段树
- 类型2操作：需要计算nums1中1的个数，然后更新nums2的总和
- 类型3操作：返回nums2的总和
核心优化思想：
- 使用懒标记线段树处理nums1的区间翻转操作，时间复杂度O(log n)
- 维护nums2的总和而不是每个元素，避免逐一更新
- 对于类型2操作，只需要知道nums1中1的个数，通过线段树快速查询
算法流程：
- 建立懒标记线段树管理nums1的区间翻转
- 维护nums2的总和sum2
- 类型1：线段树区间翻转
- 类型2：查询nums1中1的个数，更新sum2 += count1 * p
- 类型3：返回当前sum2

这种方法将时间复杂度优化到O((m+n)log n)，其中m是查询数量，n是数组长度。

代码实现

class Solution {
public:
    struct SegmentTree {
        vector<int> tree, lazy;
        int n;
        
        SegmentTree(vector<int>& nums) {
            n = nums.size();
            tree.resize(4 * n);
            lazy.resize(4 * n);
            build(nums, 1, 0, n - 1);
        }
        
        void build(vector<int>& nums, int node, int start, int end) {
            if (start == end) {
                tree[node] = nums[start];
            } else {
                int mid = (start + end) / 2;
                build(nums, 2 * node, start, mid);
                build(nums, 2 * node + 1, mid + 1, end);
                tree[node] = tree[2 * node] + tree[2 * node + 1];
            }
        }
        
        void pushDown(int node, int start, int end) {
            if (lazy[node] % 2 == 1) {
                tree[node] = (end - start + 1) - tree[node];
                if (start != end) {
                    lazy[2 * node]++;
                    lazy[2 * node + 1]++;
                }
                lazy[node] = 0;
            }
        }
        
        void updateRange(int node, int start, int end, int l, int r) {
            pushDown(node, start, end);
            if (start > r || end < l) return;
            
            if (start >= l && end <= r) {
                lazy[node]++;
                pushDown(node, start, end);
                return;
            }
            
            int mid = (start + end) / 2;
            updateRange(2 * node, start, mid, l, r);
            updateRange(2 * node + 1, mid + 1, end, l, r);
            pushDown(2 * node, start, mid);
            pushDown(2 * node + 1, mid + 1, end);
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
        
        int queryRange(int node, int start, int end, int l, int r) {
            if (start > r || end < l) return 0;
            pushDown(node, start, end);
            
            if (start >= l && end <= r) {
                return tree[node];
            }
            
            int mid = (start + end) / 2;
            return queryRange(2 * node, start, mid, l, r) + 
                   queryRange(2 * node + 1, mid + 1, end, l, r);
        }
        
        void update(int l, int r) {
            updateRange(1, 0, n - 1, l, r);
        }
        
        int query() {
            return queryRange(1, 0, n - 1, 0, n - 1);
        }
    };
    
    vector<long long> handleQuery(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        SegmentTree seg(nums1);
        long long sum2 = 0;
        for (int x : nums2) sum2 += x;
        
        vector<long long> result;
        
        for (auto& query : queries) {
            if (query[0] == 1) {
                seg.update(query[1], query[2]);
            } else if (query[0] == 2) {
                int count1 = seg.query();
                sum2 += (long long)count1 * query[1];
            } else {
                result.push_back(sum2);
            }
        }
        
        return result;
    }
};

class Solution:
    def handleQuery(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        class SegmentTree:
            def __init__(self, nums):
                self.n = len(nums)
                self.tree = [0] * (4 * self.n)
                self.lazy = [0] * (4 * self.n)
                self.build(nums, 1, 0, self.n - 1)
            
            def build(self, nums, node, start, end):
                if start == end:
                    self.tree[node] = nums[start]
                else:
                    mid = (start + end) // 2
                    self.build(nums, 2 * node, start, mid)
                    self.build(nums, 2 * node + 1, mid + 1, end)
                    self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
            
            def push_down(self, node, start, end):
                if self.lazy[node] % 2 == 1:
                    self.tree[node] = (end - start + 1) - self.tree[node]
                    if start != end:
                        self.lazy[2 * node] += 1
                        self.lazy[2 * node + 1] += 1
                    self.lazy[node] = 0
            
            def update_range(self, node, start, end, l, r):
                self.push_down(node, start, end)
                if start > r or end < l:
                    return
                
                if start >= l and end <= r:
                    self.lazy[node] += 1
                    self.push_down(node, start, end)
                    return
                
                mid = (start + end) // 2
                self.update_range(2 * node, start, mid, l, r)
                self.update_range(2 * node + 1, mid + 1, end, l, r)
                self.push_down(2 * node, start, mid)
                self.push_down(2 * node + 1, mid + 1, end)
                self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
            
            def query_range(self, node, start, end, l, r):
                if start > r or end < l:
                    return 0
                self.push_down(node, start, end)
                
                if start >= l and end <= r:
                    return self.tree[node]
                
                mid = (start + end) // 2
                return (self.query_range(2 * node, start, mid, l, r) + 
                       self.query_range(2 * node + 1, mid + 1, end, l, r))
            
            def update(self, l, r):
                self.update_range(1, 0, self.n - 1, l, r)
            
            def query(self):
                return self.query_range(1, 0, self.n - 1, 0, self.n - 1)
        
        seg = SegmentTree(nums1)
        sum2 = sum(nums2)
        result = []
        
        for query in queries:
            if query[0] == 1:
                seg.update(query[1], query[2])
            elif query[0] == 2:
                count1 = seg.query()
                sum2 += count1 * query[1]
            else:
                result.append(sum2)
        
        return result

public class Solution {
    public class SegmentTree {
        private int[] tree;
        private int[] lazy;
        private int n;
        
        public SegmentTree(int[] nums) {
            n = nums.Length;
            tree = new int[4 * n];
            lazy = new int[4 * n];
            Build(nums, 1, 0, n - 1);
        }
        
        private void Build(int[] nums, int node, int start, int end) {
            if (start == end) {
                tree[node] = nums[start];
            } else {
                int mid = (start + end) / 2;
                Build(nums, 2 * node, start, mid);
                Build(nums, 2 * node + 1, mid + 1, end);
                tree[node] = tree[2 * node] + tree[2 * node + 1];
            }
        }
        
        private void PushDown(int node, int start, int end) {
            if (lazy[node] % 2 == 1) {
                tree[node] = (end - start + 1) - tree[node];
                if (start != end) {
                    lazy[2 * node]++;
                    lazy[2 * node + 1]++;
                }
                lazy[node] = 0;
            }
        }
        
        private void UpdateRange(int node, int start, int end, int l, int r) {
            PushDown(node, start, end);
            if (start > r || end < l) return;
            
            if (start >= l && end <= r) {
                lazy[node]++;
                PushDown(node, start, end);
                return;
            }
            
            int mid = (start + end) / 2;
            UpdateRange(2 * node, start, mid, l, r);
            UpdateRange(2 * node + 1, mid + 1, end, l, r);
            PushDown(2 * node, start, mid);
            PushDown(2 * node + 1, mid + 1, end);
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
        
        private int QueryRange(int node, int start, int end, int l, int r) {
            if (start > r || end < l) return 0;
            PushDown(node, start, end);
            
            if (start >= l && end <= r) {
                return tree[node];
            }
            
            int mid = (start + end) / 2;
            return QueryRange(2 * node, start, mid, l, r) + 
                   QueryRange(2 * node + 1, mid + 1, end, l, r);
        }
        
        public void Update(int l, int r) {
            UpdateRange(1, 0, n - 1, l, r);
        }
        
        public int Query() {
            return QueryRange(1, 0, n - 1, 0, n - 1);
        }
    }
    
    public long[] HandleQuery(int[] nums1, int[] nums2, int[][] queries) {
        SegmentTree seg = new SegmentTree(nums1);
        long sum2 = 0;
        foreach (int x in nums2) sum2 += x;
        
        List<long> result = new List<long>();
        
        foreach (var query in queries) {
            if (query[0] == 1) {
                seg.Update(query[1], query[2]);
            } else if (query[0] == 2) {
                int count1 = seg.Query();
                sum2 += (long)count1 * query[1];
            } else {
                result.Add(sum2);
            }
        }
        
        return result.ToArray();
    }
}

var handleQuery = function(nums1, nums2, queries) {
    const n = nums1.length;
    const tree = new Array(4 * n).fill(0);
    const lazy = new Array(4 * n).fill(false);
    
    function build(node, start, end) {
        if (start === end) {
            tree[node] = nums1[start];
        } else {
            const mid = Math.floor((start + end) / 2);
            build(2 * node, start, mid);
            build(2 * node + 1, mid + 1, end);
            tree[node] = tree[2 * node] + tree[2 * node + 1];
        }
    }
    
    function pushLazy(node, start, end) {
        if (lazy[node]) {
            tree[node] = (end - start + 1) - tree[node];
            if (start !== end) {
                lazy[2 * node] = !lazy[2 * node];
                lazy[2 * node + 1] = !lazy[2 * node + 1];
            }
            lazy[node] = false;
        }
    }
    
    function update(node, start, end, l, r) {
        pushLazy(node, start, end);
        if (start > r || end < l) return;
        
        if (start >= l && end <= r) {
            lazy[node] = !lazy[node];
            pushLazy(node, start, end);
            return;
        }
        
        const mid = Math.floor((start + end) / 2);
        update(2 * node, start, mid, l, r);
        update(2 * node + 1, mid + 1, end, l, r);
        
        pushLazy(2 * node, start, mid);
        pushLazy(2 * node + 1, mid + 1, end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    
    function query() {
        pushLazy(1, 0, n - 1);
        return tree[1];
    }
    
    build(1, 0, n - 1);
    
    let sum2 = nums2.reduce((acc, val) => acc + val, 0);
    const result = [];
    
    for (const [type, a, b] of queries) {
        if (type === 1) {
            update(1, 0, n - 1, a, b);
        } else if (type === 2) {
            sum2 += query() * a;
        } else {
            result.push(sum2);
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

指标	复杂度
时间	-
空间	-

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析