线段树模板的一点不理解,问一下

P3372 【模板】线段树 1

萌田薰子 @ 2023-04-07 23:47:51

好久没打线段树了回来摸了一下,发现个不理解的地方

由于最近变得更懒了,于是在执行操作1:将某区间每一个数加上k 的地方,不下放懒标记,结果WA了九个,加上下放才对

但是按理来说求和操作才有输出,我只在求和操作的时候下放不行吗


by 萌田薰子 @ 2023-04-08 00:53:54

@Loic_ 我跑出来是3,手推出来也是3,不太清楚问题出在哪=-=

1和2加了后总和为2,之后1再加1总和为3,大概这样

能麻烦您深入讲一下吗x


by Loic_ @ 2023-04-08 00:55:48

@萌田薰子 ??我注释了 add 里面的 pushdown 跑出来是 1 啊。。


by 萌田薰子 @ 2023-04-08 00:59:22

@Loic_ 哦忘记注释了,我的问题

晚上脑瓜子有点昏,我去研究一下


by Loic_ @ 2023-04-08 01:02:34

@萌田薰子 就是第二个修改操作,add 最后一句由下至上更新区间和的时候,区间 [1,1][2,2] 的和还是没有受第一个修改操作影响的状态,因此更新到上面 [1,2] 和是错的。
还有问题的话早上再回。


by 萌田薰子 @ 2023-04-08 01:13:10

@Loic_ 理解了!

往下查询完后回来会更新上一层,所以要保证每两相邻层,直到本次遍历到的最后一层都是处于同一种状态,就是更新过的状态

wwww非常感谢[玫瑰][咖啡]


by Xy_top @ 2023-04-08 07:33:23

@萌田薰子 pushdown 只是打个标记,并没有实际的加上,要用的时候还是要加上的


上一页 |