重学线段树

UnionRE · 2026-09-23 12:49:03 · 算法·理论

前言

这是一篇短文。旨在让萌新快速了解更多的线段树！

文中并没有提到吉司机线段树、KTT 等。

• 吉司机线段树没讲是因为我不会证明复杂度。
• KTT 我不会。

  Chapter 0 Nodey or Leafy

线段树是 Leafy 的。

看起来线段树每个节点保存了 [l,r] 的运算和，但是其实他的信息是 leafy 的。因为所有信息本质存储在叶子。

代表区间的节点上的运算和只是为了做到快速查询。

Chapter 1 文艺线段树 / WBLT

暴力原型

对，大概就是这样。就是拆出一堆区间，然后将这些 reverse 接上去。

另外区间自己还有 reverse 标记。（\operatorname{swap}(ls, rs) 操作）

写得很丑。我这里纯纯暴。

另外正常 WBLT 不要直接用我写的 update 啊，这样多个老哥，应该还是类似 query 的方式同时更新多个节点的祖先的 l,r。 :::warning[\texttt {score = 56}]

#include<bits/stdc++.h>
const int maxn = 1e5 + 10;
const double alpha = 0.75;
using namespace std;
struct node{
    int lc, rc, fa, siz, l, r, leafy;
    bool type, rev;
}t[maxn * 4];
#define ls t[id].lc
#define rs t[id].rc
void up(int id){
    t[id].siz = t[ls].siz + t[rs].siz + 1;
    if(ls + rs)t[id].l = min(t[ls].l, t[rs].l), t[id].r = max(t[ls].r, t[rs].r);
}
void drg(int id){
    if(! (ls + rs)) return ;
    int len = t[ls].r - t[ls].l + 1, ren = t[rs].r - t[rs].l + 1;
    t[ls].l = t[id].l, t[ls].r = t[ls].l + len - 1;
    t[rs].l = t[ls].r + 1, t[rs].r = t[rs].l + ren - 1;
}
void down(int id){
    if(! (ls + rs)){
        t[id].rev = 0;
        return ;
    }
    if(t[id].rev) swap(ls, rs), t[ls].type = 0, t[rs].type = 1;
    t[ls].rev ^= t[id].rev, t[rs].rev ^= t[id].rev;
    t[id].rev = 0;
}
void build(int id, int l, int r, int fa){
    t[id].l = l, t[id].r = r, t[id].fa = fa;
    if(l == r) return t[id].leafy = l, void();
    int mid = (l + r) >> 1;
    build(ls = id * 2, l, mid, id);
    build(rs = id * 2 + 1, mid + 1, r, id);
    t[ls].type = 0, t[rs].type = 1;
    up(id);
}
vector <array <int, 3>> oper;
void find(int id, int l, int r){
    down(id);
    drg(id);
    if(t[id].l > r || l > t[id].r) return ;
    if(l <= t[id].l && t[id].r <= r) return t[id].rev ^= 1, oper.push_back({id, t[id].type, t[id].fa});
    find(ls, l, r);
    find(rs, l, r);
}
void update(int id){
    while(id) up(id), id = t[id].fa;
}
void work(int l, int r){
    int ll = l;
    for(int i = 0; i < oper.size(); i++){
        int f = oper[i][2], y = oper[i][1], x = oper[oper.size() - i - 1][0];
        if(y){
            t[f].rc = x;
            t[x].type = 1;
            t[x].fa = f;
            int len = t[x].r - t[x].l + 1;
            t[x].l = ll;
            t[x].r = t[x].l + len - 1;
        }
        else{
            t[f].lc = x;
            t[x].type = 0;
            t[x].fa = f;
            int len = t[x].r - t[x].l + 1;
            t[x].l = ll;
            t[x].r = t[x].l + len - 1;
        }
        ll = t[x].r + 1;
        // up(f);
    }
    for(auto [x, _, __] : oper) update(t[x].fa);
}
void dfs(int id){
    if(! id) return ;
    down(id);
    if(ls + rs == 0) return cout << t[id].leafy << ' ', void();
    dfs(ls), dfs(rs);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    int n, m, Y = 0;
    cin >> n >> m;
    t[0].l = INT_MAX;
    t[0].r = INT_MIN;
    t[0].siz = 0;
    t[0].rev = 0;
    build(1, 1, n, 0);
    while(m--){
        int l, r;
        cin >> l >> r;
        oper.clear();
        find(1, l, r);
        work(l, r);
    }
    dfs(1);
    return 0;
}

:::

Rebuild

Sqrt Rebuild Tree

考虑模板平衡树：

设 m = O(n)。

不进行任何平衡操作，每 \sqrt n 次插入或删除操作就重构一次。

复杂度 O(n\sqrt n)。

B Rebuild Segment Tree

还是差不多。但是重构时间我不会调，更不会分析。

因为这里可不是普通平衡树那样简单分析树高。

:::warning[\texttt{score = 72}]

#include<bits/stdc++.h>
const int maxn = 2e5 + 10, P = 1000;
using namespace std;
int p[maxn], fnt = 0;
struct node{
    int lc, rc, fa, siz, l, r, leafy;
    bool type, rev;
}t[maxn * 4];
#define ls t[id].lc
#define rs t[id].rc
void up(int id){
    t[id].siz = t[ls].siz + t[rs].siz + 1;
    if(ls + rs)t[id].l = min(t[ls].l, t[rs].l), t[id].r = max(t[ls].r, t[rs].r);
}
void drg(int id){
    if(! (ls + rs)) return ;
    int len = t[ls].r - t[ls].l + 1, ren = t[rs].r - t[rs].l + 1;
    t[ls].l = t[id].l, t[ls].r = t[ls].l + len - 1;
    t[rs].l = t[ls].r + 1, t[rs].r = t[rs].l + ren - 1;
}
void down(int id){
    if(! (ls + rs)){
        t[id].rev = 0;
        return ;
    }
    if(t[id].rev) swap(ls, rs), t[ls].type = 0, t[rs].type = 1;
    t[ls].rev ^= t[id].rev, t[rs].rev ^= t[id].rev;
    t[id].rev = 0;
}
void build(int id, int l, int r, int fa){
    t[id].l = l, t[id].r = r, t[id].fa = fa;
    if(l == r) return t[id].leafy = p[++fnt], void();
    int mid = (l + r) >> 1;
    build(ls = id * 2, l, mid, id);
    build(rs = id * 2 + 1, mid + 1, r, id);
    t[ls].type = 0, t[rs].type = 1;
    up(id);
}
vector <array <int, 3>> oper;
void find(int id, int l, int r){
    down(id);
    drg(id);
    if(t[id].l > r || l > t[id].r) return ;
    if(l <= t[id].l && t[id].r <= r) return t[id].rev ^= 1, oper.push_back({id, t[id].type, t[id].fa});
    find(ls, l, r);
    find(rs, l, r);
}
void update(int id){
    while(id) up(id), id = t[id].fa;
}
void work(int l, int r){
    int ll = l;
    for(int i = 0; i < oper.size(); i++){
        int f = oper[i][2], y = oper[i][1], x = oper[oper.size() - i - 1][0];
        if(y){
            t[f].rc = x;
            t[x].type = 1;
            t[x].fa = f;
            int len = t[x].r - t[x].l + 1;
            t[x].l = ll;
            t[x].r = t[x].l + len - 1;
        }
        else{
            t[f].lc = x;
            t[x].type = 0;
            t[x].fa = f;
            int len = t[x].r - t[x].l + 1;
            t[x].l = ll;
            t[x].r = t[x].l + len - 1;
        }
        ll = t[x].r + 1;
        // up(f);
    }
    for(auto [x, _, __] : oper) update(t[x].fa);
}
int temp[maxn], top = 0;
void dfs(int id){
    if(! id) return ;
    down(id);
    if(ls + rs == 0) return temp[++top] = t[id].leafy, void();
    dfs(ls), dfs(rs);
}
void rebuild(int id, int L, int R, int fa){
    top = 0;
    dfs(id);
    fnt = 0;
    for(int i = 1; i <= top; i++) p[i] = temp[i];
    build(id, L, R, fa);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    int n, m, Y = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) p[i] = i;
    t[0].l = INT_MAX;
    t[0].r = INT_MIN;
    t[0].siz = 0;
    t[0].rev = 0;
    build(1, 1, n, 0);
    while(m--){
        int l, r;
        cin >> l >> r;
        oper.clear();
        find(1, l, r);
        work(l, r);
        Y++;
        if(Y == P){
            Y = 0;
            rebuild(1, 1, n, 0);
        }
    }
    dfs(1);
    for(int i = 1; i <= n; i++) cout << temp[i] << ' ';
    return 0;
}

:::

WBLT

链接。

我们现在拥有了一只 Leafy 树！但她好像不平衡。

大概就是用单双旋转维护。

下面是一个图片，展示了单旋。

双旋差不多（其实是我懒得画了，oiwiki 有），复杂度不会证明。

Chapter 2 单侧递归线段树

以板子为例。

P16702 [MCO 2026] 雨水收集 - 洛谷

设 L_i=\max_{j=l}^ia_j,R_i=\max_{j=i}^ra_j。

有等式：\min(L_i,R_i)=L_i+R_i-\max_{i=l}^ra_i。

答案 f(l,r) = \sum_{i=l}^r\min(L_i,R_i)-a_i=\sum_{i=l}^rL_i+R_i-\sum_{i=l}^ra_i-(r-l+ 1)\max_{i=l}^ra_i。

这个何以维？考虑 pre(id,k) 表示前缀 \max 已经为 k，此时 id 节点内部的前缀 \max。

记 sp(id) 表示考虑 [L(id),R(id)] 的前缀 \max 和。

暴力做 pre(id,k)=pre(ls,k)+pre(rs,\max(k,ls)) 肯定不行，所以分类讨论：

• 如果 k\ge \max(id)，肯定是 k(r_{id}-l_{id}+1)。
• 否则，如果是叶子节点，那么满足 k<\max(id)，肯定是 \max(id)。
• 否则，如果 k\ge \max(ls)，那么 pre(ls,k)=k(r_{ls}-l_{ls}+1)+pre(rs,k)。
• 否则，由于 sp(id)=sp(ls)+pre(rs,\max(ls))，所以 pre(rs,\max(ls))=sp(id)-sp(ls)，此时返回 pre(ls,k)+sp(id)-sp(ls)。

后缀同样。关系式变成 ss(id)=ss(rs)+suf(ls,\max(rs))。

:::success[code]

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e6 + 10;
#define int long long 
struct node{
    int l, r, max, sum, tag, sp, ss;
    void maketag(int k){
        tag += k;
        max += k, sum += (r - l + 1) * k;
        sp += (r - l + 1) * k, ss += (r - l + 1) * k;
    }
}t[maxn * 4];
int a[maxn];
#define ls id << 1
#define rs id << 1 | 1
#define len(id) (t[id].r - t[id].l + 1)
void down(int id){
    if(! t[id].tag) return;
    t[ls].maketag(t[id].tag);
    t[rs].maketag(t[id].tag);
    t[id].tag = 0;
}
int prefix(int id, int k){
    // t[id].sp = t[ls].sp + prefix(rs, t[ls].max);
    if(k >= t[id].max) return len(id) * k;
    if(t[id].l == t[id].r) return t[id].max;
    down(id);
    if(k >= t[ls].max) return k * len(ls) + prefix(rs, k);
    return prefix(ls, k) + t[id].sp - t[ls].sp;
}
int suffix(int id, int k){
    // t[id].ss = t[rs].ss + suffix(ls, t[rs].max);
    if(k >= t[id].max) return len(id) * k;
    if(t[id].l == t[id].r) return t[id].max;
    down(id);
    if(k >= t[rs].max) return k * len(rs) + suffix(ls, k);
    return t[id].ss - t[rs].ss + suffix(rs, k);
}
void up(int id){
    t[id].sum = t[ls].sum + t[rs].sum;
    t[id].max = max(t[ls].max, t[rs].max);
    t[id].sp = t[ls].sp + prefix(rs, t[ls].max);
    t[id].ss = t[rs].ss + suffix(ls, t[rs].max);
}
void build(int id, int l, int r){
    t[id].l = l, t[id].r = r;
    if(l == r){
        t[id].max = t[id].sp = t[id].ss = t[id].sum = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    up(id);
}
vector <int> nodes;
void update(int id, int l, int r, int k){
    if(t[id].l > r || l > t[id].r) return;
    if(l <= t[id].l && t[id].r <= r) return t[id].maketag(k);
    down(id);
    update(ls, l, r, k);
    update(rs, l, r, k);
    up(id);
}
void query(int id, int l, int r){
    if(t[id].l > r || l > t[id].r) return;
    if(l <= t[id].l && t[id].r <= r) return nodes.push_back(id);
    down(id);
    query(ls, l, r);
    query(rs, l, r);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while(q--){
        int opt, l, r, x;
        cin >> opt >> l >> r;
        l++, r++;
        if(opt == 0){
            cin >> x;
            update(1, l, r, x);
        }
        else{
            nodes.clear();
            query(1, l, r);
            int ans = 0, pm, sm, M;
            pm = sm = M = INT_MIN;
            for(int i = 0; i < nodes.size(); i++){
                int id = nodes[i];
                ans -= t[id].sum;
                M = max(M, t[id].max);
                ans += prefix(id, pm);
                pm = max(pm, t[id].max);
            }
            for(int i = nodes.size() - 1; i >= 0; i--){
                int id = nodes[i];
                ans += suffix(id, sm);
                sm = max(sm, t[id].max);
            }
            cout << ans - (r - l + 1) * M << endl;
        }
    }
    return 0;
} 
/*
千里眼を持つという友よ

足元の石も見えぬか
*/

:::

Chapter 3 线段树分治

相信大家都觉得这个很水，不过在此讲一下。

能做什么？

• 操作有时效性。
• 单点查询。

就是在线段树上 dfs，然后回溯撤销即可……没了？对。

模板不说了，可撤销并查集即可。

例题：

• P5631 最小mex生成树 - 洛谷。

• P5227 [AHOI2013] 连通图 - 洛谷。

• P5787 【模板】线段树分治 / 二分图 - 洛谷。

• P16458 [UOI 2026] mex plus - 洛谷。

Chapter 4 李超线段树

这个大家应该都能发明。

这个【李超线段树】学习笔记 - cold_jelly - 博客园真的很好！！！！我觉得我这个肯定不如 ta 写的。

对每个节点维护在中点处最优的线段。

情况一：被中点线段吊打。跳过。

情况二：吊打中点线段，那么修改。

情况三：与中点线段交集在 [l,mid]：

递归左区间。

情况四：与中点线段交集在 [mid+1,r]：

此时递归右区间。

找到所有覆盖的线段树区间后，每个区间还要 pushdown 老 tag（这里指更劣的那个线段，也就是次大值）。这个可以通过单侧递归实现。

int mid = (t[id].l + t[id].r) >> 1;// 除了叶子结点,mid = t[ls].r
if(cmp(t[id].best, x, mid))swap(t[id].best, x);//down old tag
if(cmp(t[id].best, x, t[id].l))insert(ls, l, r, x);
else if(cmp(t[id].best, x, t[id].r))insert(rs, l, r, x);

总插入复杂度 O(\log^2n)。

查询只需要对路径上的所有区间取 \max 就行了，这点我只会比较感性的理解。

就比如有一个线段在 rs 方向被下推了，说明这个线段在 [mid+1,r] 还是有点优势。

在 ls 方向就是 [l,mid] 有点优势。

但是我们不知道它被推到那一层，所以要路径取 \max。

:::success[code]

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-10;
const int maxn = 1e5 + 10;
#define fequal(x, y) (fabs((x) - (y)) < eps)
struct Seg{
    bool cz;
    double k, b, root, up;
    int id;
    Seg(){
        k = b = 0.0;
        cz = 0;
        id = 0;
    }
    Seg(int x, int y, int u, int v, int i){
        id = i;
        if(x == u){
            cz = 1;
            root = x;
            up = max(y, v);
        }
        else{
            cz = 0;
            k = (y - v) * 1.0 / (x - u);
            b = y - k * x;
        }
    }
    double get(int x){
        if(! cz)return k * x + b;
        if(fequal(x, root))return up;
        return 0;
    }
};
bool cmp(Seg x, Seg y, int l){// x < y
    if(fequal(x.get(l), y.get(l))){
        if(x.id < y.id)return 0;
        return 1;
    }
    return x.get(l) < y.get(l);
}
struct node{
    int l, r;
    Seg best;// best a(r)t mid
}t[maxn * 4];
#define ls id << 1
#define rs id << 1 | 1
void build(int id, int l, int r){
    t[id].l = l, t[id].r = r;
    if(t[id].l == t[id].r)return ;
    int mid = (l + r) >> 1;
    build(ls, l, mid);build(rs, mid + 1, r);
}
void insert(int id, int l, int r, Seg x){
    if(t[id].l > r || l > t[id].r)return ;
    if(l <= t[id].l && t[id].r <= r){
        if(cmp(x, t[id].best, t[id].l) && cmp(x, t[id].best, t[id].r))return ;// 被吊打
        if(cmp(t[id].best, x, t[id].l) && cmp(t[id].best, x, t[id].r)){//吊打
            t[id].best = x;
            return ;
        }
        int mid = (t[id].l + t[id].r) >> 1;// 除了叶子结点,mid = t[ls].r
        if(cmp(t[id].best, x, mid))swap(t[id].best, x);//down old tag
        if(cmp(t[id].best, x, t[id].l))insert(ls, l, r, x);
        else if(cmp(t[id].best, x, t[id].r))insert(rs, l, r, x);
        return ;
    }
    insert(ls, l, r, x);insert(rs, l, r, x);
}
Seg max(Seg x, Seg y, int l){
    if(cmp(x, y, l))return y;
    return x;
}
Seg query(int id, int x){
    if(t[id].l > x || x > t[id].r)return Seg();
    if(t[id].l == t[id].r)return t[id].best;
    return max(max(query(ls, x), query(rs, x), x), t[id].best, x);
}
#define online1(x) (((x) + last - 1) % 39989 + 1)
#define online2(x) (((x) + last - 1) % 1000000000 + 1)
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    int n, last = 0, cnt = 0;
    cin >> n;
    build(1, 1, 39989);
    while(n--){
        int op;
        cin >> op;
        if(op == 0){
            int k;
            cin >> k;
            k = online1(k);
            cout << (last = query(1, k).id) << endl;
        }
        else{
            int x, y, u, v;
            cin >> x >> y >> u >> v;
            x = online1(x);
            y = online2(y);
            u = online1(u);
            v = online2(v);
            if(x > u){
                swap(x, u);
                swap(y, v);
            }
            insert(1, x, u, Seg(x, y, u, v, ++cnt));
        }
    }
    return 0;
}

:::

Chapter 5 Stern-Brocot Tree

你说得对，但是 SBT 也是线段树。

略去 \infin 个字。

Chapter 6 树套树

这个没啥技巧。

就是维护：

• 矩形加。
• 矩形和。

之类。

做法很简单，外层一个线段树，每个节点上再一个线段树，此时你就会发现空间爆了。

聪明的同学可能会使用动态开点 + vector <int>，发现 vector <int> 的内存重新分配导致它炸飞了。

更聪明的同学发现 deque <int> 不会重新分配内存。

然后你就远离人类了……我真的写过这种东西。

好吧，正解是可持久化一下。