# 课前零食：把相同的一段装进一个盒子

> ODT（Ordered Disjoint Tree，也常被戏称为 Chtholly Tree）很会抓住一种幸运时刻：数组里相同的值恰好连成了长段。它不承诺把任意区间操作都变成魔法；它只是把“许多格恰好一样”压进一张卡片。今天既要看它何时聪明，也要亲手把它弄到最狼狈。

## 本节目标

学完后，你能：

- 从逐格数组观察出连续相同值可以压成一个区间段；
- 用有序、互不重叠的段卡维护当前数组，并说清每张卡的语义；
- 手动执行 split(pos)，理解它只切边界、不改变任何数组值；
- 用 split(l)、split(r+1) 精确取出一个操作区间，并模拟加法、赋值与第 k 小；
- 区分 ODT 的正确性与复杂度保证：前者对任意输入成立，后者可能依赖随机操作或题目契约。

## 前置知识与课前自测

前置：数组下标、区间、排序、C++ 的有序集合 std::set 的直觉。暂时不需要会写迭代器。

1. 数组 5,5,5,2,2,8 可以压成几张“相同值段卡”？
2. 若一张卡代表 [3,7] 全为 4，位置 5 的值是多少？
3. 为了让 [l,r] 恰好是完整卡片的并，为什么右边界应当在 r+1 处切，而不是 r 处切？

<details><summary>先写答案：自测答案</summary>

1. 三张： [1,3,5]、[4,5,2]、[6,6,8]。2. 是 4。3. 切 r+1 后，覆盖 r 的那张卡完整留在区间内；切 r 会把 r 错放到右侧。

</details>

## 互动规则：段卡不是数组的摘要魔法

在纸上写初始数组：

~~~text
位置：1 2 3 4 5 6 7 8 9
数值：1 1 1 4 4 2 2 2 2
~~~

把它压为三张段卡：

~~~text
[1,3,val=1]   [4,5,val=4]   [6,9,val=2]
~~~

纸上四栏仍是：**对象**（哪些段卡）、**状态**（每张 l,r,value）、**动作**（切、遍历、删、插）、**账本**（卡片覆盖是否刚好是 1..n、是否重叠）。贯穿任务是先 add(2,7,+3)，再 assign(3,8,9)，最后问 kth(1,9,5)。

请把“ODT 很快”这句话暂时锁进抽屉。今天先确认它到底少做了哪一类工作，又在哪些数据上根本少不了。

## 从零搭框架：先看见重复格子，再发明段卡

### 第 0 步：逐格账本里重复了什么

若要给 [6,9] 每格加 3，数组做法会访问四个格；若这四格本来同为 2，它们经历的是一模一样的动作。我们不妨只写一句“[6,9] 从 2 变为 5”。

> 停顿 0：初始数组中若 query(1,9) 只问“值为 2 的元素有多少”，逐格看需要读几格？段卡要读几张卡？它省掉的是比较，还是重复保存的状态？

<details><summary>展开：段数 k 才是 ODT 的真实工作量</summary>

逐格看 9 格；段卡看 3 张，直接由 [6,9] 的长度知道有 4 个 2。它不是把每个数算得更快，而是让一串相同状态共用一份 value。以后一次操作触及多少，主要取决于覆盖了多少段 k，而不是区间长度。

</details>

### 第 1 步：给每张段卡写一份严格合同

一张卡 (l,r,value) 的合同是：

1. 它代表数组每个位置 i∈[l,r] 的值都为 value；
2. 段卡按 l 递增，互不重叠；
3. 所有段卡的并恰好覆盖 [1,n]。

若相邻两张卡 value 相同，**可以**合并成更长段，得到“极大等值段”的更整洁表示。很多经典 ODT 实现的正确性并不强制每次加法后立刻合并相等邻段；它只要求每张卡内部等值、覆盖不乱。赋值会直接把一整段范围压为一张卡，才是常见性能来源。把“可合并的优化”误当成“每一步必须合并的不变量”，很容易写乱迭代器。

![同值连续格子被一张段卡代表](../插图/11-平衡树/00-ODT-01-把数组压成段.svg)

> 停顿 1：对 [4,5,val=4]，若只把位置 5 改为 7，改后至少需要几张段卡？请写出每张的左右端点和值。

<details><summary>展开：切开不是破坏数组</summary>

需要 [4,4,4]、[5,5,7] 两张。段卡数量增加了，但每个位置的语义仍和逐格数组一致。ODT 的所有细节都围绕“先把边界切齐，再按完整卡片操作”。

</details>

### 第 2 步：发明 split(pos)，只做一件小事

要在 pos 开始操作，先找到包含 pos 的段 [l,r,v]：

- 若 pos=l，边界已齐，直接返回这张卡；
- 若 l<pos≤r，把它替换为 [l,pos-1,v] 与 [pos,r,v]，返回右半；
- 若 pos=n+1，允许把它理解成“尾后迭代器”，不新建任何卡。

~~~text
split(pos):
    it = the segment [l,r,v] containing pos
    if pos == l: return it
    replace [l,r,v] by [l,pos-1,v] and [pos,r,v]
    return iterator of [pos,r,v]
~~~

![在两道边界切开，中央就成为完整段的连续区间](../插图/11-平衡树/00-ODT-02-split切边界.svg)

> 停顿 2：初始段卡上执行 split(2) 后会出现哪四张或几张卡？执行 split(8) 呢？每一次切开后，所有位置的数值有没有改变？

<details><summary>展开：只多了边界，没有改数值</summary>

split(2) 把 [1,3,1] 变成 [1,1,1]、[2,3,1]；总共四张卡。split(8) 把 [6,9,2] 变成 [6,7,2]、[8,9,2]。切前切后逐项数组都仍是 1,1,1,4,4,2,2,2,2；split 只是让之后的区间端点能对齐。

</details>

### 第 3 步：两个 split 把 [l,r] 变成一段卡片范围

先令 begin=split(l)，再令 end=split(r+1)。此时从 begin 走到 end 之前，恰好是一串被完整覆盖的段卡：

~~~text
begin = split(l)
end = split(r + 1)
# [begin, end) 里的所有段，刚好拼成原数组 [l,r]
~~~

这比“判断每一张卡和区间相交多少”干净得多。加法可以逐卡改 value；赋值可删除 begin 到 end 的全部卡，再插入一张 [l,r,x]；第 k 小则收集每张的 (value,length)，按 value 排序并扣长度。

## 问题动机：它为什么能处理一些线段树不喜欢的混合操作

若每次询问都临时问区间第 k 小、临时幂次的幂和，常规线段树很难维护一个小而固定的摘要；逐元素则太慢。ODT 换研究对象：不直接按元素数 n 工作，而按当前段数 k 工作。区间赋值在很多随机过程里会抹掉一串旧断点、压缩 k，因此某些题故意把随机生成方式写进题面。

但这不是“ODT 的 O(log n) 定理”。它的有序集合定位/切边界约 O(log k)，之后仍要逐张访问覆盖的 k 段；k 可以是 n。

## 步步式引导：同一框架下，正确性与复杂度分开验收

### 1. 加法：逐段改 value，可能不减少段数

对 add(l,r,x)，切边界后遍历中央段，令 value+=x。每张段内所有位置都收到同一个加数，所以语义正确。可是不同段加同一个 x 后通常仍不同；段数不一定下降。

### 2. 赋值：删除中央，插回一张统一段

对 assign(l,r,x)，先切边界，擦掉中央所有卡，再插入 [l,r,x]。这一步把可能很多段压缩为一张；若相邻卡也恰为 x，可选择再合并。它是 ODT 在随机大区间赋值里常常轻盈的原因。

### 3. 构造它的坏日子

从 1,2,3,…,n（每格不同）开始，重复做 add(1,n,1)。每次 n 个值仍互不相同，段数始终 Θ(n)，每次都必须扫 Θ(n) 张卡。正确性一丝不差，复杂度却会退化。

> 停顿 3：为什么“统一给全数组加 1”不能把 1,2,3,… 合并？请写出加后相邻两格的差。若改成 assign(1,n,0)，段数怎样变化？

<details><summary>展开：同一个动作，不同的势能</summary>

加后变 2,3,4,…，相邻差仍为 1，所以没有相等邻段可合并；赋值后所有位置都为 0，中央 n 张卡直接变一张。ODT 的效率来自值与操作分布制造的压缩，不来自“区间”这两个字本身。

</details>

## 核心知识：三种说法不要混用

| 说法 | 是否总成立 | 含义 |
|---|---|---|
| 段卡语义正确 | 是 | 每段内等值，段卡有序、不重、完整覆盖 |
| split 不改数组 | 是 | 只把一张等值卡分成两张同值卡 |
| 一次操作很快 | 不总是 | 取决于被访问段数、以及题目给出的随机/压缩契约 |

若当前操作触及 k 张段卡，边界定位约 O(log k)，遍历约 O(k)，第 k 小额外有排序代价。最坏情况下 k=Θ(n)。所以做题前必须写清：输入是否随机生成？是否有频繁覆盖长区间的赋值？能否构造大量互异段？如果不能给出令人信服的段数控制，就把 ODT 当作实验工具，而非提交方案。

## 实现指南

- C++ 通常按 l 在 std::set 中排序；先找到含 pos 的段，再 split。
- 必须先取 end=split(r+1)，再取 begin=split(l)，否则擦除时可能用到已失效迭代器。
- 赋值后插入 [l,r,x]；若自行实现相邻合并，先明确谁有资格被 erase，别在遍历时回头改已失效迭代器。
- 第 k 小的 k 是按元素次数而非段数扣减：一段 [l,r,v] 的贡献是 r-l+1 个 v。
- Python 实验室故意用列表保存段卡，便于看见切分；正式课才讨论 std::set 的迭代器纪律。
- 对用户任意给出的操作序列，不要声称 ODT 有均摊对数保证。

## 纸上模拟：先切齐，再给卡片动手术

从 [1,3,1]、[4,5,4]、[6,9,2] 开始，执行 add(2,7,+3)。填写：

| 阶段 | 段卡序列 | 哪些卡被实际改值 |
|---|---|---|
| split(2) 后 |  |  |
| split(8) 后 |  |  |
| 加 3 后 |  |  |

<details><summary>展开：一份可检查的流水线</summary>

split(2) 后有 [1,1,1]、[2,3,1]、[4,5,4]、[6,9,2]；split(8) 后再把最后段切成 [6,7,2]、[8,9,2]。中央三张 [2,3,1]、[4,5,4]、[6,7,2] 分别改为值 4、7、5；两端 [1,1,1] 与 [8,9,2] 完全不动。逐项结果为 1,4,4,7,7,5,5,2,2。

</details>

接着 assign(3,8,9)。先预测它会删掉中央几张卡、再留下几张；再问 kth(1,9,5) 时，别把“第 5 张段卡”误当成“第 5 小元素”。

## 互动小实验室

运行 [把相同的一段装进一个盒子.py](../../互动程序/11-平衡树/00-把相同的一段装进一个盒子.py)。实验室使用可读的段卡列表，不是 OJ 的 std::set 代码；它会显示每次 split、被触及段数和普通数组验算。可输入：

- show：查看段卡和展开后的数组；
- split 2：只切一个边界，观察数值不变；
- add 2 7 3：逐段加；
- assign 3 8 9：删中央、插一张段；
- kth 1 9 5：按段长度找第 5 小；
- pow 1 9 2 97：按段计算幂和模 97；
- attack：切换到全异值数组，体验一次全区间加必须扫很多段。

先猜“这次会碰几张卡”，再执行命令；它比背 split 的四行代码更能告诉你 ODT 是否适合一题。

## 扩展与联系

- ODT 只借用了平衡树的有序集合来找断点；它不像 Segment Tree、Treap、Splay 那样维护固定的树形区间摘要。
- [ODT 正式扩展课](04-高阶扩展-随机输入契约与ODT.md)会结合指定伪随机生成器，严格讨论何种题面事实支持期望复杂度。
- “极大等值段”与“若干等值段”的表示都可语义正确；前者更直观，后者在某些实现中少一次合并操作。先固定不变量再写代码。
- 若需要稳健的区间加、赋值、最值/和，Lazy Segment Tree 通常更可靠；若需动态顺序，考虑隐式 Treap/Splay；ODT 的独特优势来自段数小。

## 总结与自检

1. split(pos) 改变的是数组值还是段卡边界？
2. 为什么取 [l,r] 应切 l 和 r+1？
3. ODT 一次操作的主要代价与什么量有关？
4. 为什么全异值数组反复全区间加是坏例子？

<details><summary>自检答案</summary>

只改边界；中央卡要完整覆盖到 r；与被遍历的段数 k 有关；相邻差不变，k 长期保持 Θ(n)。

</details>

## 一周预热安排

- 第 1 天：把三组小数组压成段卡，练习写覆盖合同。
- 第 2 天：手做 split(1)、split(l)、split(n+1)。
- 第 3 天：用两个 split 取出 [l,r]，再做 add 与 assign。
- 第 4 天：构造全异值坏例，并解释为何赋值反而压缩。
- 第 5 天：运行互动程序后进入[ODT 正式扩展课](04-高阶扩展-随机输入契约与ODT.md)。