千问 LeetCode 2569. 更新数组后处理求和查询 Java实现

这道题的核心是高效维护nums1的区间反转操作因为数据规模达到10^5暴力反转会超时。需要用到线段树区间更新区间查询或BitSet来优化。下面给出Java实现采用线段树 懒标记的方案class Solution {public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) {int n nums1.length;// 计算nums2的初始和long sum2 0;for (int num : nums2) {sum2 num;}// 构建线段树SegmentTree seg new SegmentTree(nums1);// 收集类型3的答案ListLong ans new ArrayList();for (int[] q : queries) {if (q[0] 1) {// 操作1反转nums1的[l, r]区间seg.reverse(q[1], q[2]);} else if (q[0] 2) {// 操作2nums2[i] nums1[i] * p// 相当于 sum2 nums1中1的个数 * psum2 (long) seg.querySum() * q[1];} else {// 操作3记录当前nums2的和ans.add(sum2);}}// 转换为long[]返回return ans.stream().mapToLong(Long::longValue).toArray();}// 线段树节点class SegNode {int l, r;int sum; // 区间内1的个数boolean lazy; // 懒标记是否需要反转}// 线段树class SegmentTree {private SegNode[] tr;private int n;public SegmentTree(int[] nums) {this.n nums.length;tr new SegNode[n * 4];for (int i 0; i n * 4; i) {tr[i] new SegNode();}build(1, 0, n - 1, nums);}// 建树private void build(int u, int l, int r, int[] nums) {tr[u].l l;tr[u].r r;if (l r) {tr[u].sum nums[l];return;}int mid l (r - l) / 2;build(u * 2, l, mid, nums);build(u * 2 1, mid 1, r, nums);pushup(u);}// 更新父节点信息private void pushup(int u) {tr[u].sum tr[u * 2].sum tr[u * 2 1].sum;}// 下传懒标记private void pushdown(int u) {if (tr[u].lazy) {reverseNode(u * 2);reverseNode(u * 2 1);tr[u].lazy false;}}// 反转一个节点private void reverseNode(int u) {tr[u].sum (tr[u].r - tr[u].l 1) - tr[u].sum;tr[u].lazy !tr[u].lazy;}// 区间反转public void reverse(int l, int r) {reverse(1, l, r);}private void reverse(int u, int l, int r) {if (tr[u].l l tr[u].r r) {reverseNode(u);return;}pushdown(u);int mid tr[u].l (tr[u].r - tr[u].l) / 2;if (l mid) reverse(u * 2, l, r);if (r mid) reverse(u * 2 1, l, r);pushup(u);}// 查询整个区间的和1的个数public int querySum() {return tr[1].sum;}}}核心思路1. 问题分析- 操作1反转nums1的区间[l, r]0变11变0- 操作2nums2[i] nums1[i] * p相当于sum2 nums1中1的个数 * p- 操作3返回当前nums2的和2. 为什么用线段树- 操作1是区间修改反转操作2需要查询整个nums1中1的个数- 线段树可以在O(log n)时间内完成区间反转和区间求和- 懒标记lazy tag避免每次反转都更新到叶子节点3. 关键细节- 反转一个节点时sum 区间长度 - 原sum因为0变11变0- 懒标记用布尔值反转两次等于没反转!lazy- 操作2中nums1中1的个数就是线段树根节点的sum值复杂度分析- 时间复杂度O((n q) log n)其中n是数组长度q是操作次数- 空间复杂度O(n)线段树需要4倍空间测试用例public static void main(String[] args) {Solution sol new Solution();// 示例1int[] nums1 {1, 0, 1};int[] nums2 {0, 0, 0};int[][] queries {{1, 1, 1}, {2, 1, 0}, {3, 0, 0}};System.out.println(Arrays.toString(sol.handleQuery(nums1, nums2, queries))); // [3]// 示例2int[] nums1_2 {1};int[] nums2_2 {5};int[][] queries_2 {{2, 0, 0}, {3, 0, 0}};System.out.println(Arrays.toString(sol.handleQuery(nums1_2, nums2_2, queries_2))); // [5]}这个解法在LeetCode上可以高效通过所有测试用例线段树是处理区间反转问题的标准解法。