更新数组后处理求和查询【LC2569】
给你两个下标从 0 开始的数组
nums1和nums2，和一个二维数组queries表示一些操作。总共有 3 种类型的操作：
- 操作类型 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中所有元素的和。请你返回一个数组，包含所有第三种操作类型的答案。
欠下的债还是要还的，终于把线段树板子搞好了
- 思路
class Solution { public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) { List<Long> res = new ArrayList<>(); int n = nums1.length; long sum2 = 0L; for (int i = 0; i < n; i++){ sum2 += nums2[i]; } SegmentTree seg = new SegmentTree(nums1); for (int[] q : queries){ if (q[0] == 1){ seg.updateAll(1, q[1] + 1, q[2] + 1); }else if (q[0] == 2){ sum2 += 1L * q[1] * seg.query(1, 1, nums2.length);// 处理越界 }else{ res.add(sum2); } } return res.stream().mapToLong(x -> x).toArray(); } } class Node { int l, r; int sum;// 和 题目所要求的值 int lazy;// 延迟修改的值 } class SegmentTree { private Node[] tr;// 线段树 private int[] nums;// 原数组 public SegmentTree(int[] nums) { int n = nums.length; this.nums = nums; tr = new Node[n << 2]; for (int i = 0; i < tr.length; ++i) { tr[i] = new Node(); } build(1, 1, n);// 建树 } private void build(int u, int l, int r) {// l,r表示当前区间 u表示当前节点编号（1,n） tr[u].l = l; tr[u].r = r; if (l == r) {// 若到达叶子节点 tr[u].sum = nums[l - 1];// 存储值 return; } // 左右递归 int mid = (l + r) >> 1; build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r); pushup(u);// 更新信息 } // 区间查询 public int query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) { // 在区间内，直接返回 return tr[u].sum; } pushdown(u); int res = 0; int mid = (tr[u].l + tr[u].r) >> 1; if (l <= mid) { res += query(u << 1, l, mid); } if (r > mid) { res += query(u << 1 | 1, mid + 1, r); } return res; } // 区间修改: public void updateAll(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r) { tr[u].lazy ^= 1; tr[u].sum = tr[u].r - tr[u].l + 1 - tr[u].sum ; return; } // 在回溯之前向下传递修改标记 pushdown(u); int mid = (tr[u].l + tr[u].r) >> 1; if (l <= mid) { updateAll(u << 1, l, r); } if (r > mid) { updateAll(u << 1 | 1, l, r); } pushup(u);// 更新本节点信息 } // pushUp函数更新节点信息, 本题是求和 private void pushup(int u) { tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum; } // 懒加载 private void pushdown(int u) { if (tr[u].lazy == 1) {// 如果懒标记不为0，就将其下传，修改左右儿子维护的值 f(u << 1); f(u << 1 | 1); tr[u].lazy = 0;// 向下传之后将该节点的懒标记清0 } } // 父节点修改时，维护子节点的更新 private void f(int u){ tr[u].sum = tr[u].r - tr[u].l + 1 - tr[u].sum; tr[u].lazy ^= 1;// 修改两次即为不修改 } }
