当前位置:首页 > 数据结构 > 线段树 > 正文
SSOJ2615区间赋值区间求和
583+

题目大意:有n个数,不断地对其中的某段数字进行赋值,不断地询问某一段数字的和,如何快速解决?

题目描述

给你n个整数,请问第x个到第y个的和是多少?

与上一题不同,在询问前后,这n个数中的某个区间的数可能会同时变成z。

输入

第一行:n和m,表示n个数,m个询问

第二行:n个整数

接下来m行,每行3或4个整数o、x、y(、z):o表示求和还是更改数字,如果o=1,表示第x个数到第y个数都变成z;如果o=2,表示求第x个到第y个的和。

输出

对于每次询问和,输出区间的和。

样例输入

5 3
1 2 -3 6 5
2 2 4
1 2 5 1
2 1 3

样例输出

5
3

提示

1<=x、y<=n;1<=o<=2;n个数,每个数的绝对值不超过1000;5<=n、m<=200000

(10个点数据范围:5, 10, 100, 500, 1000, 5000, 10000, 50000, 100000, 150000, 200000)

解题思路

上一题区间增减,为了避免一大棵树更新,我们使用了一个标记,记录儿子结点还没加上的数字,使得父亲结点一下的子树不必更新。由于这个标记可以叠加,而且不分顺序,使用起来非常方便。本题不是增减,而是赋值,不能叠加,但可以覆盖,有先后顺序,不能完全按照上一题的方法处理了。

为了可以整段赋值,儿子结点暂不更新,我们同样打标记,f[i]记录结点i的儿子结点还没赋的值,d[i]记录区间的和。如果下一次这个区间重新赋值为k,那么d[i]可以直接计算得到,f[i]=k直接覆盖之前的标记即可;如果是i的儿子所在区间(结点j)需要赋值,也就是j这个区间需要赋值两次,虽然后一次会把前一次覆盖,但后面求和的时候很难处理多个标记,我们还是要先处理父亲结点i的标记,让i结点的左右儿子都赋值为f[i],再对儿子结点j进行赋值操作。此过程叫做标记下放,将父亲结点的标记打到儿子结点上,同时更新儿子结点的值,记录父亲结点的标记为无,这样父亲结点的左右儿子都更新了,但儿子的儿子还没更新。在求和的时候,如果用到儿子结点,但父亲结点含有标记,也需要先标记下放,让儿子结点的值得到更新,避免用到未更新的数据。

程序实现

暴力70分:

更多

About

坚决不Copy代码!

本文标签:,,

SSOJ2615区间赋值区间求和:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter