千问 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的答案
List<Long> 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) {
// 操作2：nums2[i] += nums1[i] * p
// 相当于 sum2 += nums1中1的个数 * p
sum2 += (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变1，1变0）
- 操作2：nums2[i] += nums1[i] * p，相当于sum2 += nums1中1的个数 * p
- 操作3：返回当前nums2的和

2. 为什么用线段树：
- 操作1是区间修改（反转），操作2需要查询整个nums1中1的个数
- 线段树可以在O(log n)时间内完成区间反转和区间求和
- 懒标记（lazy tag）避免每次反转都更新到叶子节点

3. 关键细节：
- 反转一个节点时：sum = 区间长度 - 原sum（因为0变1，1变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();

// 示例1
int[] 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]

// 示例2
int[] 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上可以高效通过所有测试用例，线段树是处理区间反转问题的标准解法。