线段树
线段树合并&&分裂
可持久化线段树
线段树分治
Seg—beats
兔队线段树
历史最值&&历史版本和
Q：维护一种数据结构，支持对数列 \(\{a\},\{b\}\) 的如下操作
- 对 \(\{a\}\) 区间加，之后令 \(b_i\leftarrow \max(b_i,a_i)\)
- 历史最大值，求 \(\max(b_{l\cdots r})\)
采用打标记的方式处理修改操作，考虑标记下放的操作对 \(b\) 序列的影响。
我们先不合并标记，设当前节点上的所有标记按下放顺序形成了一个队列 \(q\)。
为了方便这里约定 \(s[i]\) 表示到 \(i\) 之前所有加标记的前缀和，\(add\) 为加标记，\(hadd\) 为所有加标记中的最大值，\(mx\) 为当前最大值，\(hmx\) 为历史最大值。
对于核心操作 pushdown，我们把自己（now）的标记队列为 \(q_1\)，父亲的标记队列为 \(q_2\)，合并后的标记队列为 \(q_3\)。
考虑对历史最值的贡献：
\[\begin{split}
hmx_3 &= mx_3 + \max_{i=1}^{|q_3|}s_3[i]\\
&=mx_3 + hadd_3
\end{split}
\]
考虑对历史最大加标记的贡献：
\[\begin{split}
hadd_3 &= \max_{i=1}^{|q_3|}s_3[i]\\
&= \max\{\max_{i=1}^{|q_1|}s_1[i],\max_{i=1}^{|q_2|}s_2[i]+s_1[|q_1|]\}\\
&= \max\{hadd_1,hadd_2+add_1\}
\end{split}
\]
历史和
Q：维护一种数据结构，支持对数列 \(\{a\},\{b\}\) 的如下操作
- 对 \(\{a\}\) 区间加，之后令 \(b_i\leftarrow b_i+a_i\)
- 历史和，求 \(\sum_{i=l}^r b_i\)
同样打标记处理，为了能更新，不妨把 \(b\) 序列的更新也作为一个标记 \(upd\)。
设 \(cnt\) 为队列中更新标记的个数， \(sum\) 为当前节点的区间和， \(hsum\) 为当前节点的历史和，\(add\) 为当前节点的加标记，\(hadd\) 为当前节点加标记的历史和，\(s[i]\) 为加标记的前缀和。
考虑标记对历史和的贡献：
\[\begin{split}
hsum &= \sum_{i = 1}^{|q|}[q[i] = upd](sum+s[i]*len)\\
&=sum*cnt + len*hadd
\end{split}
\]
考虑合并两个队列：
\[\begin{split}
hadd_{now} &= \sum_{i=1}^{|q_1|+|q_2|}[q_3[i] = upd]s_3[i]\\
&= \sum_{i = 1}^{|q_1|}[q_1[i] = upd]s_1[i] + \sum_{i = 1} ^{|q_2|}[q_2[i] = upd](s_1[|q_1|]+s_2[i])\\
&= hadd_1+add_1*cnt_2+hadd_2
\end{split}
\]