首页 > 笔记 > 线段树高阶总结

线段树高阶总结

第二篇总结。。。

先讲一些小技巧

1.用位运算代替乘除2

具体见 位运算技巧

2.用define节省代码量

调用时就可以用lson,rson代替了

具体见下方代码

3.build时直接读入

具体见代码

基本操作

复习一下

(例子为区间加)

0.上推 下推

1.建立线段树

2.查询区间

3.更新区间

例题

poj3486

下一个操作:区间乘

就是对于一个数列,可以在区间上乘以一个数

原来的数列是

a1+a2+a3+a4

那么我们给每个数乘上x

a1x+a2x+a3x+a4x

可以得到

x(a1+a2+a3+a4)

就相当于原来的区间和乘x

假如原来已经有乘法标记了,那就变成这样

xy(a1+a2+a3+a4)

(原来的为y,现在的为x)

直接乘上x即可

假如原来有加法标记了

(a1+y)x+(a2+y)x+(a2+y)x+(a2+y)x

=xyn+x(a1+a2+a3+a4)

n为区间数的数量

所以程序如下

bzoj 1798

现在来点更高阶的

方差luogu1417

题意:对于一个数量,求区间的方差与平均数

images

题解:

我们把方差公式展开

images

所以只需要维护一个区间平方和和区间和

当我们更新一个区间加时

images

所以我们只需要维护一个mark就可以了

代码:

最后一道,写完都虚了。。。

hdu4578

这道题坑在有三种询问:set , add , mul。所以lazy标记要有三个,如果三个标记同时出现的处理方法——当更新set操作时,就把add标记和mul标记全部取消;当更新mul操作时,如果当前节点add标记存在,就把add标记改为:add * mul。这样的话就可以在PushDown()操作中先执行set,然后mul,最后add。

麻烦在有三种询问:和 , 平方和 , 立方和。对于set和mul操作来说,这三种询问都比较好弄。

对于add操作,和的话就比较好弄,按照正常方法就可以;

平方和这样来推:(a + c)2 = a2 + c2 + 2ac  , 即seg2[rt] = seg2[rt] + (r – l + 1) * c * c + 2 * seg1[rt] * c;

立方和这样推:(a + c)3 = a3 + c3 + 3a(a2 + ac) , 即seg3[rt] = seg3[rt] + (r – l + 1) * c * c * c + 3 * c * (seg2[rt] + seg1[rt] * c);

几个注意点:add标记取消的时候是置0,mul标记取消的时候是置1;在PushDown()中也也要注意取消标记,如set操作中取消add和mul,mul操作中更新add; 在add操作中要注意seg3 , seg2 , seg1的先后顺序,一定是先seg3 , 然后seg2 , 最后seg1; int容易爆,还是用long long要保险一点; 最后就是膜运算较多,不要漏掉东西。

The end.


4 COMMENTS

  1. 真·DaD3zZ2016-12-28 上午11:39

    实名反对之前盗用我ID发评论的人
    如果你想要优化线段树的常数的话:http://blog.csdn.net/lcrtest/article/details/50817904?locationNum=2&fps=1

  2. totziens2017-01-06 上午11:15

    这个换行的大括号是怎么回事
    谁写的啊

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×