NOI 一轮复习：线段树

线段树是一种功能强大的二叉数据结构，可以维护半群上的信息（满足结合律）。

对于一般情况，我们使用堆式线段树来存储线段树；对于空间开不下的情况，我们使用动态开点来存储线段树。

延迟标记

这个东西不只被用在线段树上，但从线段树结构基本可以介绍出它的大部分应用。以下问题都可以直接使用多元标记来处理：

区间最大子段和：维护前缀后缀最大子段和、区间和和答案即可；
区间平方和：不难根据区间和计算出新的区间平方和；
区间加等差数列单点求和：每个点维护一个 $d$ ，代表其加上的是 $d\times i$ ，其中 $i$ 是下标，然后再维护一个区间加标记即可。

[CF446C] DZY Loves Fibonacci Numbers.

区间加斐波那契数列，区间求和。

将广义斐波那契数列的前两项作为标记打在线段树中，合并时直接加起来就可以。再加上斐波那契数列的求和公式： $\sum_{i=1}^{n}f_i=f_{n+2}-f_{2}$ ，和便可以直接计算。代码。

李超线段树

模板。考虑这样一个问题：加入给定定义域的一次函数，查询 $x\in[l,r]$ 时的最小值。

怎么做？考虑一种线段树，维护 $[l,r]$ 的节点只存储一个 $mid$ 处值最小的线段。修改操作如何实现呢？如果修改的线段不比当前线段优，那么下传修改线段；如果修改线段比当前线段优，那么下传当前线段。也就是说，要下传的一定是那个更劣的线段。这两条线段的交点在哪一部分，就往哪个儿子下传即可（当然，可能没有交点），而另一个儿子的部分，未下传线段优于下传线段，无需下传。

单次修改时间复杂度为 $O(\log^2 n)$ ，查询时直接记录路过的所有线段的答案即可，时间复杂度依然为 $O(\log n)$ 。

模板题在做的时候先树剖，每次修改拆成两条向上的链。

inline void pushup(int o, int l, int r) { // T[o].v 维护区间最小值
    T[o].v = min({T[o].v, T[o << 1].v, T[o << 1 | 1].v});
    T[o].v = min({T[o].v, calc(T[o].s, dis[idx[l]]), calc(T[o].s, dis[idx[r]])});
}
void update(int o, int l, int r, int x, int y, Seg k) { // 加入定义域为 [x, y] 的线段 k
    int mid = l + r >> 1; 
    if (x <= l && r <= y) {
        if (calc(k, dis[mid]) < calc(T[o].s, dis[idx[mid]])) swap(k, T[o].s); // 中点处 x 当前线段比 k 劣
        if (calc(k, dis[idx[l]]) < calc(T[o].s, dis[idx[l]])) update(o << 1, l, mid, x, y, k); 
        if (calc(k, dis[idx[r]]) < calc(T[o].s, dis[idx[r]])) update(o << 1 | 1, mid + 1, r, x, y, k); 
        return pushup(o, l, r); 
    }
    if (x <= mid) update(o << 1, l, mid, x, y, k); 
    if (mid < y) update(o << 1 | 1, mid + 1, r, x, y, k); 
    pushup(o, l, r); 
}
i64 query(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) return T[o].v; 
    int mid = l + r >> 1; 
    i64 res = min(calc(T[o].s, dis[idx[max(l, x)]]), calc(T[o].s, dis[idx[min(r, y)]])); 
    if (x <= mid) res = min(res, query(o << 1, l, mid, x, y)); 
    if (mid < y) res = min(res, query(o << 1 | 1, mid + 1, r, x, y)); 
    return res; 
}

例题

刷基础 1

[2023 钉耙编程 1] Easy problem I

Portal。如果一个数发生过 $a_i\leftarrow x-a_i$ ，那么以后就会一直这样。搞两棵线段树分别维护即可。代码。

[Luogu P5278] 算术天才⑨与等差数列

Portal.

发现条件非常严苛，因此可以考虑哈希之类的方法，这里不做赘述。

一段区间可以重排为等差数列，当且仅当满足（ $d=0$ 先特判掉）：

$\max -\min =d\times (len-1)$ ；
$\gcd_{i=l}^{r-1}(a_{i+1}-a_i)=d$ ；
序列中没有重复的元素。

用线段树维护即可。第三条可以使用 set、map 维护一个数最左边的出现位置，然后用线段树维护这个值的最小值，如果这个数小于 $l$ ，那么一定没有重复元素。代码。