线段树

简介

线段树可以在 $O(\log n)$ 的时间内进行单点或者区间操作，带懒标记的线段树还能在操作 apply 和统计 operator+ 时使用不同的策略。最常见的情况是使用线段树维护一些区间性质，例如区间最大值或者是区间和。但是我们也可以通过在节点中存储多个信息来统计一些更复杂的性质。

通用模板见这里。

使用线段树时，一般还需要考虑一些容易出错的问题：

• 节点信息的默认值应该是什么；
• 标记如何向标记叠加；
• 标记如何向信息叠加；
• 信息如何向信息叠加；
• 非叶节点是否遵循同样的叠加规则。

最后一点非常重要，因为一开始在考虑 apply 操作时可能忘记非叶节点并不能代表维护的单点的性质，它们实际上是多个节点进行统计之后得到的信息。

例子

区间加 + 查询最小值

WARNING

注意 Info 的初值，这里必须是 INF，因为查询是在默认值的基础上不断往上叠加得到的，所以默认值必须足够大。这也就要求在初始化线段树时把每个点都显式确定为 $0$。

struct Tag {
    int val = 0;
    void apply(const Tag& rhs) {
        val += rhs.val;
    }
};
struct Info {
    int val = INF;
    void apply(const Tag& rhs, size_t len) {
        val += rhs.val;
    }
};
Info operator+(const Info &a, const Info &b) {
    return {min(a.val, b.val)};
}

区间点积

题目：ABC357F - Two Sequence Queries

给你两个序列 $\{a_i\}$ 和 $\{b_i\}$，需要处理三种询问：

1. 给 $[l,r]$ 上每一个 $a_i$ 加上 $x$；
2. 给 $[l,r]$ 上每一个 $b_i$ 加上 $x$；
3. 询问 $\sum _{i=l}^r(a_i\times b_i)$ 的值，对 $998244353$ 取模。

观察每次 1/2 类操作后区间 $\sum (a_i\times b_i)$ 的变化，可以考虑维护三个量：区间的 $\sum a_i$、$\sum b_i$ 以及 $\sum a_i\times b_i$。

struct Tag {
    mll a = 0, b = 0;
    void apply(const Tag& rhs) {
        a += rhs.a;
        b += rhs.b;
    }
};
struct Info {
    mll a_sum = 0, b_sum = 0, val = 0;
    void apply(const Tag& rhs, size_t len) {
        val += rhs.b * a_sum;
        b_sum += rhs.b * len;
        val += rhs.a * b_sum;
        a_sum += rhs.a * len;
    }
};
Info operator+(const Info &a, const Info &b) {
    return {
        .a_sum = a.a_sum + b.a_sum,
        .b_sum = a.b_sum + b.b_sum,
        .val = a.val + b.val,
    };
}

最大子段和

题目：洛谷P4513 小白逛公园

一开始，小白就根据公园的风景给每个公园打了分。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第 $a$ 个和第 $b$ 个公园之间（包括 $a,b$ 两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。

那么，就请你来帮小白选择公园吧。

对于 $100\%$ 的数据，$1\le n\le 5\times 10^5$，$1\le m\le 10^5$，所有打分都是绝对值不超过 $1000$ 的整数。

询问任意一个区间中的最大子区间和。考虑用线段树维护 4 个信息：

1. 左端点位于区间左端点、并且右端点位于区间右端点的最大子段和（也就是区间本身的和）；
2. 右端点位于区间右端点的最大子段和；
3. 左端点位于区间左端点的最大子段和；
4. 最大子段和。

于是有如下转移：

Info operator+(const Info &a, const Info &b) {
    return {
        a.sum + b.sum,
        max(-INFLL, max(a.left, a.sum + b.left)),
        max(-INFLL, max(b.right, b.sum + a.right)),
        max(-INFLL, max(max(a.ans, b.ans), a.right + b.left)),
    };
}

这个思路实际上可以推广到一系列需要查询区间的子区间的问题上。

区间最小值的个数

TIPS

这个方法也可以用来求区间零的个数。

题目：CF1996G - Penacony

给你一个环和一些点对，要求至少标记环上每个点对之间的两条弧之一。求一共至少标记多少条边。

考虑用线段树记录区间零的个数，即维护区间最小值和最小值的个数：

struct Tag {
    int val = 0;
    void apply(const Tag& rhs) {
        val += rhs.val;
    }
};
struct Info {
    int minval = INF, cnt = 0;
    void apply(const Tag& rhs, size_t len) {
        minval += rhs.val;
    }
};
Info operator+(const Info &a, const Info &b) {
    return {
        .minval = min(a.minval, b.minval),
        .cnt = a.minval == b.minval ?
                   a.cnt + b.cnt
               : a.minval < b.minval ?
                   a.cnt
               :
                   b.cnt,
    };
}

仍然要注意 minval 的默认值问题。

势能线段树

势能线段树可以用来处理单点取 $\min$、区间求和的问题。

需要维护以下信息：

1. val：当前区间的元素和；
2. mx：当前区间的最大值；
3. se：当前区间的次大值；
4. cnt：当前区间有几个最大值。

模板如下：

WARNING

在创建线段树时，应当手动把每个叶子的 mx 设为 INF（就像区间求最小值线段树一样），且 se 的初值应当设为一个比可能的 Tag 值更小的值，否则在 range_apply 时会无限递归。

模板代码太长，请见 Git 仓库。

线段树分治

线段树分治用来离线解决一些查询问题，题目的主要特征是某些操作只在特定的时间段有效。方法是对时间建立（不带懒标记的）线段树，然后把操作转化成线段树上的区间修改，然后遍历一遍线段树得到所有查询的结果。只需要在进入某个节点时应用它上面的操作，退出时撤销掉这些操作。

模板代码太长，请见 Git 仓库。