临海市网站建设,服务好 售后好的网站建设,关于建设网站的书本,个人网站首页设计文章目录 Handling Sum Queries After Update 更新数组后处理求和查询问题描述#xff1a;分析代码线段树 Tag Handling Sum Queries After Update 更新数组后处理求和查询
问题描述#xff1a;
给你两个下标从 0 开始的数组 n u m s 1 和 n u m s 2 nums1 和 nums2 nums1… 文章目录 Handling Sum Queries After Update 更新数组后处理求和查询问题描述分析代码线段树 Tag Handling Sum Queries After Update 更新数组后处理求和查询
问题描述
给你两个下标从 0 开始的数组 n u m s 1 和 n u m s 2 nums1 和 nums2 nums1和nums2 和一个二维数组 q u e r i e s queries queries 表示一些操作。总共有 3 种类型的操作
操作类型 1 为 q u e r i e s [ i ] [ 1 , l , r ] queries[i] [1, l, r] queries[i][1,l,r] 。你需要将 n u m s 1 nums1 nums1 从下标 l 到下标 r 的所有 0 反转成 1 或将 1 反转成 0 。l 和 r 下标都从 0 开始。 操作类型 2 为 q u e r i e s [ i ] [ 2 , p , 0 ] queries[i] [2, p, 0] queries[i][2,p,0] 。对于 0 i n 0 i n 0in 中的所有下标令 n u m s 2 [ i ] n u m s 2 [ i ] n u m s 1 [ i ] ∗ p nums2[i] nums2[i] nums1[i] * p nums2[i]nums2[i]nums1[i]∗p 。 操作类型 3 为 q u e r i e s [ i ] [ 3 , 0 , 0 ] queries[i] [3, 0, 0] queries[i][3,0,0] 。求 nums2 中所有元素的和。 请你返回一个数组包含所有第三种操作类型的答案。 1 n u m s 1. l e n g t h , n u m s 2. l e n g t h 1 0 5 n u m s 1. l e n g t h n u m s 2. l e n g t h 1 q u e r i e s . l e n g t h 1 0 5 q u e r i e s [ i ] . l e n g t h 3 0 l r n u m s 1. l e n g t h − 1 0 p 1 0 6 0 n u m s 1 [ i ] 1 0 n u m s 2 [ i ] 1 0 9 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 1nums1.length,nums2.length105nums1.lengthnums2.length1queries.length105queries[i].length30lrnums1.length−10p1060nums1[i]10nums2[i]109
分析 这个问题给的2个数组nums1,nums2,同时还有query指令。 问题本身比较绕 n u m s 1 nums1 nums1是01数组而 n u m s 2 nums2 nums2可以看成是由 n u m s 1 nums1 nums1的一个函数映射。 而每次的 q u e r y query query指令为3的时候需要计算出 n u m s 2 nums2 nums2 的元素和。
如果是纯粹计算数组的元素和是配不上这个hard。 没错问题的query指令还有1和2它们会对nums1进行修改从而影响到nums2的元素进而会影响到结果。 最原始的方式就是暴力。 q u e r y 1 query1 query1的时候会将 n u m s 1 nums1 nums1中的区间 [ l , r ] [l,r] [l,r]的 01 01 01进行反转即0变1,1变0而产生的影响就是 [ l , r ] [l,r] [l,r]内的出现的1会导致处于该区间内的 n u m s 2 [ i ] nums2[i] nums2[i],增加 n u m s 1 [ i ] ∗ p nums1[i]*p nums1[i]∗p. q u e r y 1 query1 query1的时候对 n u m s 1 nums1 nums1修改的时间复杂度为 O ( k ) O(k) O(k),k为区间的范围 q u e r y 2 query2 query2对 n u m s 2 nums2 nums2的修改时间复杂度是 O ( N ) O(N) O(N)。 q u e r y 3 query3 query3要计算 s u m ( n u m s 2 ) sum(nums2) sum(nums2),时间复杂度 O ( N ) O(N) O(N).
那么整体的时间复杂度就是 O ( N 2 ) O(N^2) O(N2),到此暴力的模拟思路就可以完成了结果TLE。 其实nums2这个数组是一个中间数组虽然是统计nums2的和实际上并不需要得到nums2 的详细元素。 在该问题中nums2的和在指令执行的过程中一定是单调递增的而且在 q u e r y 1 query1 query1之后区间 [ l , r ] [l,r] [l,r]产生了 x 个 1 x个1 x个1那么这 x 个 1 x个1 x个1会影响到对应 n u m s 2 nums2 nums2对应这个区间的 n u m s 2 [ i ] nums2[i] nums2[i],效果就是这个区间的nums2的和增加了x*p 。
如果一开始nums1有x个1那么nums2初始和为 s u m 1 sum_1 sum1当进行了 q u e r y 1 query1 query1 的操作nums1的某个区间出现了 x 1 x_1 x1个1此时nums2的元素和就是 s u m 1 x 1 ∗ p sum_1x_1*p sum1x1∗p.
所以如果可以快速的统计 n u m s 1 nums1 nums1在每个 q u e r y 1 query1 query1的操作下区间产生的1的数量就可以快速的累加到nums2的元素和上这样就可以在 O ( 1 ) O(1) O(1)的时间复杂度下得到 q u e r y 3 query3 query3时的结果。
而能够达到这个效果的就是线段树。而且线段树在解决这类问题中更新和查询的时间复杂度都是 O ( l o g N ) O(logN) O(logN),所以整体的时间复杂度就是 O ( N l o g N ) O(NlogN) O(NlogN)
代码 线段树
public long[] handleQuery(int[] nums1, int[] nums2, int[][] queries) {int n nums1.length, m 0, i 0;cnt1 new int[n * 4];flip new boolean[n * 4];build(nums1, 1, 1, n);long sum 0L;for (var x : nums2){sum x;}for (var q : queries){if (q[0] 3) m;}long[] ans new long[m];for (var q : queries) {if (q[0] 1){update(1, 1, n, q[1] 1, q[2] 1); } else if (q[0] 2){sum (long) q[1] * cnt1[1]; } else{ans[i] sum;} }return ans;}// segment treeprivate int[] cnt1;private boolean[] flip;// 维护区间 1 的个数private void maintain(int o) {cnt1[o] cnt1[o * 2] cnt1[o * 2 1];}// 执行区间反转private void do_(int o, int l, int r) {cnt1[o] r - l 1 - cnt1[o];flip[o] !flip[o];}// 初始化线段树 o,l,r1,1,nprivate void build(int[] a, int o, int l, int r) {if (l r) {cnt1[o] a[l - 1];return;}int m (l r) / 2;build(a, o * 2, l, m);build(a, o * 2 1, m 1, r);maintain(o);}// 反转区间 [L,R] o,l,r1,1,nprivate void update(int o, int l, int r, int L, int R) {if (L l r R) {do_(o, l, r);return;}int m (l r) / 2;if (flip[o]) {do_(o * 2, l, m);do_(o * 2 1, m 1, r);flip[o] false;}if (m L){update(o * 2, l, m, L, R);} if (m R){update(o * 2 1, m 1, r, L, R); } maintain(o);}时间复杂度 O ( N l o g N ) O(NlogN) O(NlogN)
空间复杂度 O ( N ) O(N) O(N)
代码来源于 灵神大佬,略有调整线段树写的很简洁。
Tag
Array
Segment Tree
