基于线段树的数据结构

技术分享 7个月前 (08-13) 0 999+

关注

写在前面

本文对线段树问题进行了竞赛向的题型细分，根据操作特性和信息维护方式分为三类，旨在帮助选手快速识别问题模型并选择合适解法。分类基于个人理解，主要面向基础线段树问题的应用场景。

省流：有关线段树的进阶数据结构在此不做说明，可前往：https://oi-wiki.org/ds/seg/ 进一步了解。

基于线段树的数据结构

第一类线段树

第一类线段树也就是大家所熟知的线段树模板，其操作是线性的（如：加法操作是线性操作，满足交换律和结合律），操作之间没有依赖关系。

懒惰标记和下放操作的维护较为简单。

参考例题：luogu P3372

AC record ：code by min25

引流：模板问题不解析，可转：@justTrying 线段树讲解视频

（注：单点修改更加快速的方案是树状数组实现，此处不提供线段树实现）

实现

（此处仅展示线段树集成部分）

#define ls (u << 1)  #define rs (u << 1 | 1)  namespace SegmentTree {     class node {     public:         ll data, lazy = 0;     }tr[N << 2];     void build (ll u, ll l, ll r) {         if (l == r) {             tr[u].data = a[l];             return;         }         ll mid = l + (r - l) / 2;         build (ls, l, mid);         build (rs, mid + 1, r);         tr[u].data = tr[ls].data + tr[rs].data;     }     void pushdown (ll u, ll l, ll r) {         if (! tr[u].lazy) {             return;         }         ll mid = l + (r - l) / 2;          tr[ls].data += tr[u].lazy * (mid - l + 1);         tr[ls].lazy += tr[u].lazy;          tr[rs].data += tr[u].lazy * (r - mid);         tr[rs].lazy += tr[u].lazy;          tr[u].lazy = 0;     }     ll query (ll u, ll l, ll r, ll ql, ll qr) {         if (ql > r || qr < l) {             return 0;         }         if (ql <= l && qr >= r) {             return tr[u].data;         }         ll mid = l + (r - l) / 2;         pushdown (u, l, r);         ll suml = query (ls, l, mid, ql, qr);         ll sumr = query (rs, mid + 1, r, ql, qr);         return suml + sumr;     }     void update (ll u, ll l, ll r, ll ul, ll ur, ll val) {         if (ul > r || ur < l) {             return;         }         if (ul <= l && ur >= r) {             tr[u].data += val * (r - l + 1);             tr[u].lazy += val;             return;         }         ll mid = l + (r - l) / 2;         pushdown (u, l, r);         update (ls, l, mid, ul, ur, val);         update (rs, mid + 1, r, ul, ur, val);         tr[u].data = tr[ls].data + tr[rs].data;     } };  using namespace SegmentTree;

其他类问题

luogu P3870 （通过寻找无依赖的维护信息，原问题可转化成第一类线段树）code by min25

luogu P1438 （利用差分数组和等差数列修改的性质，原问题为第一类线段树）code by min25

luogu P1558 （同时维护多颗线段树，将复杂操作转换为多个第一类线段树问题）code by min25

普通第二类线段树

第二类线段树即非线性线段树，其操作（的组合）打破了线性性质，顺序影响结果（如：为确保维护信息的正确性，乘法和加法必须按固定顺序处理），操作之间存在依赖关系（顺序敏感）。

懒惰标记和下方操作的维护较为复杂。

参考例题： luogu P3373

AC record ：code by min25

解析

此处以维护区间加法和区间乘法为例（即例题）。

引流：此处仅拆解此问题的核心部分，更多的细节（及做法）可以见 luogu 题解区。

首先先要明确一个问题：正确地同时维护这两个信息需要依赖加乘操作的先后顺序。

我们假设：对于元素 (x) 的操作：① (x = x + y) ② (x = x times z) （这里稍微解释一下：虽然问题是区间操作，但是我们当下考虑区间修改对单点的影响，以便说明）

此处，按 ① (rightarrow) ② 的顺序操作：(x = (x + y) times z)

若按 ② (rightarrow) ① 的顺序操作：(x = (x times z) + y)

很显然如果不考虑加乘顺序，正确性就无法保证。

那么，在这个问题中，有性质：乘法操作对加法操作的懒惰标记有影响，而加法操作对乘法操作的懒惰标记无影响。

具体而言：先加后乘的操作 ① (rightarrow) ② 等价于 (x = x times z + y times z) ，通过单点乘法和加法懒标记的修改，将乘法操作对前期加法操作的依赖，转换成加法操作。（具体可见实现）

由此，我们把原先加乘的双向依赖转换成了加法对乘法的单项依赖，这时，只需要固定加乘顺序（先乘后加）即可保证程序的正确性。

实现

（此处仅展示线段树集成部分）

namespace SegmentTree {     class node {     public:         ll v, tag1, tag2;         // tag1 - add, tag2 - mul     }tr[N << 2];     void build (ll u, ll l, ll r) {         if (l == r) {             tr[u].v = a[l];             return;         }         ll mid = l + (r - l) / 2;         build (ls, l, mid);         build (rs, mid + 1, r);         tr[u].v = (tr[ls].v + tr[rs].v) % m;         tr[u].tag2 = 1;     }     void pushdown (ll u, ll l, ll r) {         if (! tr[u].tag1 && tr[u].tag2 == 1) {             return;         }         ll mid = l + (r - l) / 2;         tr[ls].v = (tr[ls].v * tr[u].tag2 + tr[u].tag1 * (mid - l + 1)) % m;         tr[ls].tag1 = (tr[ls].tag1 * tr[u].tag2 + tr[u].tag1) % m;         tr[ls].tag2 = (tr[ls].tag2 * tr[u].tag2) % m;          tr[rs].v = (tr[rs].v * tr[u].tag2 + tr[u].tag1 * (r - mid)) % m;         tr[rs].tag1 = (tr[rs].tag1 * tr[u].tag2 + tr[u].tag1) % m;         tr[rs].tag2 = (tr[rs].tag2 * tr[u].tag2) % m;          tr[u].tag1 = 0;         tr[u].tag2 = 1;     }     void add (ll u, ll l, ll r, ll al, ll ar, ll k) {         if (l > ar || r < al) {             return;         }         if (l >= al && r <= ar) {             tr[u].v = (tr[u].v + (r - l + 1) * k) % m;             tr[u].tag1 = (tr[u].tag1 + k) % m;             return;         }         ll mid = l + (r - l) / 2;         pushdown (u, l, r);         add (ls, l, mid, al, ar, k);         add (rs, mid + 1, r, al, ar, k);         tr[u].v = (tr[ls].v + tr[rs].v) % m;     }     void mul (ll u, ll l, ll r, ll ml, ll mr, ll k) {         if (l > mr || r < ml) {             return;         }         if (l >= ml && r <= mr) {             tr[u].v = (tr[u].v * k) % m;             tr[u].tag1 = (tr[u].tag1 * k) % m;             tr[u].tag2 = (tr[u].tag2 * k) % m;             return;         }         ll mid = l + (r - l) / 2;         pushdown (u, l, r);         mul (ls, l, mid, ml, mr, k);         mul (rs, mid + 1, r, ml, mr, k);         tr[u].v = (tr[ls].v + tr[rs].v) % m;     }     ll query (ll u, ll l, ll r, ll ql, ll qr) {         if (l > qr || r < ql) {             return 0;         }         if (l >= ql && r <= qr) {             return tr[u].v % m;         }         ll mid = l + (r - l) / 2;         pushdown (u, l, r);         return (query (ls, l, mid, ql, qr) + query (rs, mid + 1, r, ql, qr)) % m;     } }; using namespace SegmentTree;

其他类问题

luogu P1471 （方差维护，需处理区间加法的同时维护平方和）

扩展第二类线段树

这里将介绍第二类线段树的典型操作：覆盖（(tt cover)）。

例题：luogu P1253

AC record ：code by min25

解析

此处以针对例题解析。

我们需要明确：正确地同时维护区间赋值和区间加法需要依赖操作的先后顺序。

考虑对元素 x 的操作：① 赋值操作：(x=y) ② 加法操作：(x = x + z)

按 ① → ② 的顺序：(x = y + z)

若按 ② → ① 的顺序：(x = y)（加法被覆盖）

显然，赋值操作的优先级高于加法，即赋值会清空之前的加法标记。

性质：赋值操作对加法标记有影响（直接覆盖并清空加法标记）；加法操作对赋值标记无影响（若存在赋值标记，则加法直接在赋值基础上累加）。

由此我们固定操作顺序为先赋值后加法，即：遇到赋值操作时，清空加法标记；遇到加法操作时，若存在赋值标记，则直接修改赋值标记，否则正常累加。

这样，我们通过让赋值操作完全覆盖加法操作，将双向依赖转换为赋值对加法的单向依赖，从而保证正确性。

实现

（此处仅展示线段树集成部分）

namespace SegmentTree {     class node {     public:         ll v, tag1, tag2;         // tag1 - change tag2 - add     }tr[N << 2];     void build (ll u, ll l, ll r) {         if (l == r) {             tr[u].v = a[l];             return;         }         ll mid = l + (r - l) / 2;         build (ls, l, mid);         build (rs, mid + 1, r);         tr[u].v = max (tr[ls].v, tr[rs].v);         tr[u].tag1 = esp;     }     void pushdown (ll u, ll l, ll r) {         if (tr[u].tag1 != esp) {             tr[ls].v = tr[u].tag1;             tr[ls].tag1 = tr[u].tag1;             tr[ls].tag2 = 0;              tr[rs].v = tr[u].tag1;             tr[rs].tag1 = tr[u].tag1;             tr[rs].tag2 = 0;              tr[u].tag1 = esp;         } else if (tr[u].tag2) {             tr[ls].v += tr[u].tag2;             if (tr[ls].tag1 != esp) {                 tr[ls].tag1 += tr[u].tag2;             } else {                 tr[ls].tag2 += tr[u].tag2;             }              tr[rs].v += tr[u].tag2;             if (tr[rs].tag1 != esp) {                 tr[rs].tag1 += tr[u].tag2;             } else {                 tr[rs].tag2 += tr[u].tag2;             }              tr[u].tag2 = 0;         }     }     void update (ll u, ll l, ll r, ll ul, ll ur, ll x) {         if (r < ul || l > ur) {             return;         }         if (l >= ul && r <= ur) {             tr[u].v = tr[u].tag1 = x;             tr[u].tag2 = 0;             return;         }         ll mid = l + (r - l) / 2;         pushdown (u, l, r);         update (ls, l, mid, ul, ur, x);         update (rs, mid + 1, r, ul, ur, x);         tr[u].v = max (tr[ls].v, tr[rs].v);     }     void add (ll u, ll l, ll r, ll al, ll ar, ll k) {         if (r < al || l > ar) {             return;         }         if (l >= al && r <= ar) {             tr[u].v += k;             if (tr[u].tag1 != esp) {                 tr[u].tag1 += k;             } else {                 tr[u].tag2 += k;             }             return;         }         ll mid = l + (r - l) / 2;         pushdown (u, l, r);         add (ls, l, mid, al, ar, k);         add (rs, mid + 1, r, al, ar, k);         tr[u].v = max (tr[ls].v, tr[rs].v);     }     ll query (ll u, ll l, ll r, ll ql, ll qr) {         if (l > qr || r < ql) {             return esp;         }         if (l >= ql && r <= qr) {             return tr[u].v;         }         ll mid = l + (r - l) / 2;         pushdown (u, l, r);         return max (query (ls, l, mid, ql, qr), query (rs, mid + 1, r, ql, qr));     } }; using namespace SegmentTree;

第三类线段树

我们将具有如下特征的问题，称为第三类线段树问题：

非平凡区间合并：维护的信息（如最大子段和、最长交替序列等）需要特殊合并规则，不能简单通过左右子区间信息线性组合得到。
依赖交界状态：合并时需额外记录前缀/后缀特征（如端点值、单调性等），且合并结果受左右子区间交界处状态的影响。
多信息协同：通常需同时维护多个辅助数据（如区间和、前缀最大值等）以支持复杂查询。

例题：luogu P6492

AC record ：code by min25

解析

此处以针对例题解析。

引流：此处仅拆解此问题的核心部分，更多的细节（及做法）可以见 luogu 题解区。

该问题要求维护一个动态变化的 (tt LR) 序列，每次单点修改后，快速查询最长交替子串（即不包含连续相同字符的最长子串）。

稍加思考可知，这题的核心问题是处理小区间合并为的区间的上传操作。

很显然，最长交替子串不能通过简单的左右子区间答案相加得到，而需判断左右子区间的交界字符是否相异。

具体而言，合并左右子区间时，我们应分情况处理：

若左右字符相异，则可能产生新的交替子串，长度为左子区间的最长后缀 (+) 右子区间的最长前缀。同时，若左子区间的最长前缀覆盖整个左区间，则可延申至右子区间的最长前缀（后缀延申同理）。

若左右字符相同，则无法拼接，直接取左右子区间的最大值。

实现

（此处仅展示线段树集成部分）

namespace SegmentTree {     class node {     public:         ll lcol, rcol;         ll lv, rv, v;     }tr[N << 2];     void pushup (ll u, ll l, ll r) {         ll mid = l + (r - l) / 2;         ll lenl = (mid - l + 1), lenr = (r - mid);         tr[u].lcol = tr[ls].lcol;         tr[u].rcol = tr[rs].rcol;          tr[u].lv = tr[ls].lv;         tr[u].rv = tr[rs].rv;         tr[u].v = max (tr[ls].v, tr[rs].v);         if (tr[ls].rcol != tr[rs].lcol) {             tr[u].v = max (tr[u].v, tr[ls].rv + tr[rs].lv);             if (tr[ls].v == lenl) {                 tr[u].lv = lenl + tr[rs].lv;             }             if (tr[rs].v == lenr) {                 tr[u].rv = lenr + tr[ls].rv;             }         }     }     void build (ll u, ll l, ll r) {         if (l == r) {             tr[u].lv = tr[u].rv = tr[u].v = 1;             return;         }         ll mid = l + (r - l) / 2;         build (ls, l, mid);         build (rs, mid + 1, r);         pushup (u, l, r);     }     void update (ll u, ll l, ll r, ll ux) {         if (l > ux || r < ux) {             return;         }         if (l == r && l == ux) {             tr[u].lcol ^= 1;             tr[u].rcol ^= 1;             return;         }         ll mid = l + (r - l) / 2;         update (ls, l, mid, ux);         update (rs, mid + 1, r, ux);         pushup (u, l, r);     }     ll query () {         return tr[1].v;     } }; using namespace SegmentTree;