线段树
1.线段树 1
区间加、区间求和
2.线段树 2
区间加、区间乘、区间求和
再开一个乘法标记就行。
注意区间乘的时候该区间的加法tag也要乘
push_down的时候同样加法tag也要乘
!再注意乘法标记初值和push_down后都应该设为1
3.[JSOI2008]最大数
区间max(min)
其实只要改改query函数就够了
被while循环坑了一手。
4.[TJOI2009]开关
tre还是维护区间和
考虑维护一个tag表示当前区间被修改了几次
发现其实只与奇偶性有关，偶数次修改相当于没修改，所以下传标记时只需儿子的标记异或当前的标记
注意当前标记为0时不需下传
5.无聊的数列
将操作转换为对差分数组操作即可用线段树维护
6.扶苏的问题
维护两个tag分别表示修改操作和加法操作
下传时先传修改tag并且清空加法tag。
代码 初值开的大一点。
7.小白逛公园
每个点需要维护最大前缀和、最大后缀和、最大子段和
合并时分类讨论即可。
需要注意的是查询时也要类似合并进行操作，因为并不能像之前的题一样直接合并查询
8.方差
再维护一个区间平方和。
权值线段树
其实就是对原序列的各个数出现的次数统计后存入权值数组
对权值数组进行一些线段树操作。