第 3 章 · 02 线段树与 Treap 难点精讲 ★

第 3 章 · 02 线段树与 Treap 难点精讲 ★

本节定位:对应 OI Wiki docs/ds/seg.md(线段树)+ docs/ds/treap.md(Treap)。难度:进阶难点(★)。前置依赖:本章 01 节(二叉树/树状数组)+ 第 2 章(复杂度/递归)。

⚠️ 注意:这一节是数据结构章的"分水岭"。线段树和平衡树是省选级的入场券,学不会基本告别 NOI 省选。但它们也确实是整个数据结构里最难啃的两块骨头,需要慢节奏多推导,不能指望看一遍就会。

为什么难

线段树难在哪:

1. 懒标记(lazy propagation)下传时机:区间修改时,如果不把修改下传到叶子(那退化成 O(n)),而是"打标记延迟",查询经过时才下传——这个"延迟"思维很反直觉。
2. pushdown 顺序:下传标记前要先 pushdown 父节点,否则子节点的旧标记会被覆盖。
3. 空间 4n:堆式存储要开 4n 而非 2n,很多人不知道为什么,开了 2n 然后 RE。
4. 标记合并:多个标记(加法 + 乘法)同时存在时,下传顺序和合并规则极易错。

Treap 难在哪:

1. 旋转操作抽象:左旋右旋要改变多个父子关系,纸上画图都容易乱。
2. 两种实现风格差异大:旋转式 Treap(靠左右旋维持平衡)和 FHQ Treap(分裂 + 合并)代码风格完全不同,初学者容易混。
3. 随机化保证平衡的直觉:为什么给每个节点随机一个优先级、再按优先级堆化,就能保证期望树高 O(\log n)?这个概率论证不直观。

慢节奏精讲 · 线段树 docs/ds/seg.md

核心思想:区间分治成 O(\log n) 个节点

线段树把一个长 n 的区间递归二分,形成一棵二叉树。关键观察:任意区间 [l, r] 都能被拆成树上最多 O(\log n) 个节点的并。所以单次区间操作只需碰 O(\log n) 个节点。

以 n = 5 为例,线段树形态(节点标的是管辖区间):

查询 [3, 5] 时,不用碰所有叶子,只拆成 [3,3] 和 [4,5] 两个节点——这就是"O(\log n) 个节点"的含义。

堆式存储:节点 p 的左儿子是 2p,右儿子是 2p+1。

build / 单点修改 / 区间查询

这三步 Wiki docs/ds/seg.md 讲得很清楚,核心代码:

void build(int s,int t,int p){              // 建树 [s,t]
  if(s==t){ d[p]=a[s]; return; }
  int m=(s+t)/2;
  build(s,m,2*p); build(m+1,t,2*p+1);
  d[p]=d[2*p]+d[2*p+1];                     // 合并儿子信息
}
void update(int x,int v,int s,int t,int p){ // 单点修改
  if(s==t){ d[p]=v; return; }
  int m=(s+t)/2;
  if(x<=m) update(x,v,s,m,2*p); else update(x,v,m+1,t,2*p+1);
  d[p]=d[2*p]+d[2*p+1];
}
​

区间查询就是把 [l,r] 拆成若干完整节点递归合并,Wiki 有完整代码,这里不重复。

★★★ 懒标记 lazy propagation(线段树精髓)

这是线段树真正的难点。问题:做区间加(给 [l,r] 每个元素加 v)时,如果递归到叶子再改,复杂度退化成 O(n)。

核心思路:如果某个节点管辖的区间 [s,t] \subseteq [l,r] 完全被覆盖,那就不必再往下递归——直接在这个节点上打一个"加 v"的标记,更新这个节点的和(d[p] += v * (t-s+1)),然后立刻返回。子节点的修改延迟到将来某次确实要进入子树时再做。

void pushdown(int p,int len){              // 把 p 的标记下传给两个儿子
  if(tag[p]){
    d[2*p]   += tag[p] * (len - len/2);    // 左儿子长度 len-len/2
    d[2*p+1] += tag[p] * (len/2);          // 右儿子长度 len/2
    tag[2*p]   += tag[p];                  // 标记下传
    tag[2*p+1] += tag[p];
    tag[p] = 0;                            // p 的标记清空
  }
}
void add(int l,int r,int v,int s,int t,int p){
  if(l<=s && t<=r){                        // 完全覆盖
    d[p] += (long long)v * (t-s+1);
    tag[p] += v;                           // 打标记,不下传
    return;
  }
  pushdown(p, t-s+1);                      // ★进入儿子前必须 pushdown
  int m=(s+t)/2;
  if(l<=m) add(l,r,v,s,m,2*p);
  if(r>m)  add(l,r,v,m+1,t,2*p+1);
  d[p] = d[2*p] + d[2*p+1];                // 回收
}
​

查询时同样:进入儿子前先 pushdown。

关键铁律:只要要进入某个节点的儿子(无论修改还是查询),就必须先 pushdown 这个节点。否则儿子节点上的旧 d 值没更新,得到错误结果。

为什么空间要开 4n

堆式存储下,若 n = 2^k + 1,线段树最后一层会有大量"无用叶子",总节点数最多 4n - 5。所以数组开 4n 是安全下界。开 2n 会 RE,开 2.5n 也可能不够,直接 4n。

进阶变体(Wiki 各页)

• docs/ds/persistent-seg.md:可持久化线段树(主席树)。每次修改新建 O(\log n) 个节点,保留历史版本。
• docs/ds/seg-in-balanced.md / docs/ds/seg-merge-split.md:线段树合并分裂,实现动态开点 + 区间第 k 小。
• docs/ds/seg-beats.md:Segment Tree Beats,区间最值操作(Chtholly Tree),省选级。
• 动态开点:值域 10^9 但操作只有 10^5 时,不预先建树,用到哪个节点才开。

慢节奏精讲 · Treap docs/ds/treap.md

Tree + Heap = Treap

Treap = Tree(二叉搜索树)+ Heap(堆)。每个节点有两个值:

1. 键值 key:满足 BST 性质(左子树 key 都小,右子树 key 都大),用于排序。
2. 优先级 priority:满足堆性质(父节点 priority 优于儿子),用于维持平衡。

priority 随机生成。神奇之处在于:固定 key 序列但 priority 随机时,这棵 BST 的期望高度是 O(\log n)(等价于随机插入形成的 BST)。这就是"随机化保证平衡"——不是靠旋转规则维持最坏情况,而是靠概率保证期望。

两种实现

旋转式 Treap(见 docs/ds/treap.md)

插入:按 BST 找到位置插入,再像堆一样向上调整:如果当前节点 priority 比父差,就旋转。删除:把节点旋到叶子再删。

左旋(把右儿子提上来):

旋转后 D 变成根,B 变成 D 的左儿子,D 原来的左子 E 变成 B 的右子。一次旋转涉及 3 条边的父子关系变更。代码:

void rotate(int &p,int d){  // d=0 左旋(右儿子上),d=1 右旋(左儿子上)
  int k = ch[p][d^1];       // 取要提上来的儿子
  ch[p][d^1] = ch[k][d];    // p 收编 k 的内侧子树
  ch[k][d] = p;
  p = k;                    // k 成为新根
  update(p); update(ch[p][d]);
}
​

FHQ Treap(分裂合并式),见 docs/ds/treap.md 和 docs/ds/seg-merge-split.md:

不用旋转,只两个操作:

1. split(p, k):把树 p 拆成两棵,一棵 key \le k,一棵 key > k。
2. merge(a, b):合并两棵树(要求 a 的所有 key 都小于 b),按 priority 决定谁在上。

void split(int p,int k,int &x,int &y){     // x 装 <=k, y 装 >k
  if(!p){ x=y=0; return; }
  if(val[p] <= k){ x=p; split(ch[p][1], k, ch[p][1], y); }
  else            { y=p; split(ch[p][0], k, x, ch[p][0]); }
  update(p);
}
int merge(int x,int y){                    // 要求 x 的 key 都 < y
  if(!x||!y) return x|y;
  if(pri[x] < pri[y]){ ch[x][1]=merge(ch[x][1],y); update(x); return x; }
  else               { ch[y][0]=merge(x,ch[y][0]); update(y); return y; }
}
​

FHQ 的优势:代码更短、支持可持久化、不需要处理旋转的各种边界。初学者推荐 FHQ。

为什么 Treap 期望平衡

把 n 个不同 key 按随机 priority 插入,等价于"以随机顺序插入 key 形成 BST"。后者期望高度 O(\log n) 是经典结论(高度 \le 4.5 \ln n 左右)。所以只要 priority 用 rand() 或 mt19937 生成,Treap 树高期望 O(\log n),不会退化成链。

常见误区

⚠️ 注意:

1. 线段树忘 pushdown:进入儿子前没 pushdown,儿子 d 值是旧的,查询/修改结果全错。这是最常见的线段树 bug。
2. 线段树空间开 2n:RE。必须 4n。
3. 懒标记忘清零:节点初始 tag 没设 0,带垃圾值,完全乱套。全局数组自动 0,但局部要 memset。
4. 标记合并顺序错:加法 + 乘法标记共存时,必须先下传乘法再下传加法(mul 影响 add),顺序反了就错。
5. Treap 用 rand() 不够随机:rand() 范围小且分布一般,推荐 mt19937。
6. FHQ merge 时 key 大小关系反:merge(a, b) 要求 a 所有 key < b,反了就破坏 BST 性质。
7. 旋转式 Treap 删除时没旋到叶子:中途直接摘节点会断子树,必须旋到叶子或只有一个儿子时才删。

练习建议

💡 学习提示:线段树和 Treap 必须手写模板背下来。比赛时不可能让你现查。

线段树:

• 洛谷 P3372 【模板】线段树 1(区间加 + 区间求和,练懒标记)
• 洛谷 P3373 【模板】线段树 2(区间乘 + 区间加 + 区间求和,练标记合并)
• 洛谷 P1531 I Hate It(区间最大值)
• 进阶:P2894 酒店(区间连续空位)、P4198 楼房重建

Treap:

• 洛谷 P3369 【模板】普通平衡树(插入/删除/排名/前驱后继)
• 洛谷 P3391 【模板】文艺平衡树(FHQ Treap 区间翻转,练 split/merge)
• 洛谷 P1486 郁闷的出纳员

刷模板题时,先抄一遍 Wiki/标准代码理解,然后关掉代码默写。能默写出来才算掌握。

本节要点

1. 线段树核心:区间分治成 O(\log n) 个节点;堆式存储 p \to 2p, 2p+1;空间开 4n。
2. ★★★ 懒标记:完全覆盖的节点打标记延迟下传;进入儿子前必须 pushdown;标记合并(加+乘)有顺序。
3. Treap = BST(key)+ Heap(随机 priority),期望高度 O(\log n);两种实现:旋转式 / FHQ 分裂合并式(推荐初学)。
4. FHQ 核心:split 按值拆、merge 按 priority 合并、合并时 a 的 key 都小于 b。
5. 必练模板题:P3372/P3373(线段树)、P3369/P3391(Treap),能默写才算掌握。