一类伪在线的线段树操作

· · 个人记录

如果对线段树的操作是单点赋值（一个点仅有一个值，只会被赋值一次），区间查询，其中单点赋值的位置严格递增，那么该操作是伪在线的。

具体地，一个线段树节点会被询问到，当且仅当整个区间的都已赋值。可以节点中的信息暂存，当节点 满 了的时候再统一合并信息。

该情况一般出现于 DP 优化。例：

f_i=\max\limits_{j\in[l_i,r_i]}\{f_j+k_jx_i\}

带转移区间的斜率优化。

在线做的话只能每个节点用平衡树维护凸壳，是大常数 2\log。注意到我们只关心节点 满 之后的信息，所以每次归并求出有效凸壳即可做到小常数 1\log。

update：Query 的时候要在 \log 个凸壳上二分求最值，所以还是 2\log。但常数基本可以看做单log。