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

这道题的核心是高效维护 nums1 的区间反转操作因为数据规模达到 10^5暴力反转会超时。下面给出 TypeScript 实现采用线段树 懒标记的方案。function handleQuery(nums1: number[], nums2: number[], queries: number[][]): number[] {const n nums1.length;// 计算 nums2 的初始和let sum2 0;for (const num of nums2) {sum2 num;}// 构建线段树const seg new SegmentTree(nums1);// 收集类型 3 的答案const ans: number[] [];for (const q of 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 seg.querySum() * q[1];} else {// 操作3记录当前 nums2 的和ans.push(sum2);}}return ans;}// 线段树节点class SegNode {l: number 0;r: number 0;sum: number 0; // 区间内 1 的个数lazy: boolean false; // 懒标记是否需要反转}// 线段树class SegmentTree {private tr: SegNode[];private n: number;constructor(nums: number[]) {this.n nums.length;this.tr [];for (let i 0; i this.n * 4; i) {this.tr.push(new SegNode());}this.build(1, 0, this.n - 1, nums);}// 建树private build(u: number, l: number, r: number, nums: number[]): void {this.tr[u].l l;this.tr[u].r r;if (l r) {this.tr[u].sum nums[l];return;}const mid l Math.floor((r - l) / 2);this.build(u * 2, l, mid, nums);this.build(u * 2 1, mid 1, r, nums);this.pushup(u);}// 更新父节点信息private pushup(u: number): void {this.tr[u].sum this.tr[u * 2].sum this.tr[u * 2 1].sum;}// 下传懒标记private pushdown(u: number): void {if (this.tr[u].lazy) {this.reverseNode(u * 2);this.reverseNode(u * 2 1);this.tr[u].lazy false;}}// 反转一个节点private reverseNode(u: number): void {this.tr[u].sum (this.tr[u].r - this.tr[u].l 1) - this.tr[u].sum;this.tr[u].lazy !this.tr[u].lazy;}// 区间反转对外接口reverse(l: number, r: number): void {this.reverseRange(1, l, r);}private reverseRange(u: number, l: number, r: number): void {if (this.tr[u].l l this.tr[u].r r) {this.reverseNode(u);return;}this.pushdown(u);const mid this.tr[u].l Math.floor((this.tr[u].r - this.tr[u].l) / 2);if (l mid) this.reverseRange(u * 2, l, r);if (r mid) this.reverseRange(u * 2 1, l, r);this.pushup(u);}// 查询整个区间的和1 的个数querySum(): number {return this.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 倍空间测试用例// 示例1const nums1 [1, 0, 1];const nums2 [0, 0, 0];const queries [[1, 1, 1], [2, 1, 0], [3, 0, 0]];console.log(handleQuery(nums1, nums2, queries)); // [3]// 示例2const nums1_2 [1];const nums2_2 [5];const queries_2 [[2, 0, 0], [3, 0, 0]];console.log(handleQuery(nums1_2, nums2_2, queries_2)); // [5]这个解法在 LeetCode 上可以高效通过所有测试用例线段树是处理区间反转问题的标准解法。