本文所说 OI 方言（你也可以称其为程序设计竞赛方言、算法竞赛方言，但本文暂且称为 OI（不过大部分起源确实是 OI）），是指 OI 资料或中文 OI 资料中的以下 3 类名词。
- 含义与一般语境中的有所不同
- 一般语境中原本已有称呼，但 OI 中的叫法稍有偏离原文，或者使用了一个全新的名字
- 一般语境根本不使用
使用本文列举的方言或许会在某些语境下导致问题，例如双方对词的理解不同会造成困惑、对搜索非 OI 资料造成不必要的困难等等。当然，如果参与交流的人都明白表达的意思，或许问题不大。
一些 OI 方言不太偏离词源原意，或者是一个比较有描述性的新词，或者并没有广泛传播。这类词如果没什么值得说的就不包括在本文内了。
线段树
这或许是传播最广泛的、影响最广的一个 OI 方言了，甚至在很长时间里我都没意识到这是 OI 方言的一个例子。
线段树原本指一种计算几何中处理区间的数据结构。1983 年 W. Bucher, H. Edelsbrunner. On Expected- and Worst-Case Segment Trees 专门介绍了这一数据结构。该文引用的 1980 年 An optimal worst case algorithm for reporting intersections of rectangles 中同样限定为处理线段（原文各自用了 intervals 和 line segments 两种表达）的数据结构。（最早的相关资料似乎为 1977 年 Algorithms for Klee's rectangle problems，但它是未出版的笔记）
然而，在 2010 年之前，包括非中文的竞赛语境中，线段树已经用于指一般的进行信息合并的数据结构了。而今天搜索引擎里，算法竞赛的用法已经完全盖过了原本的意思，只剩下 Wikipedia 等少数网站。这必然经历了一些发展过程，但尚未调查清楚。
不过，早期似乎很少有明确对列表连续段进行操作的数据结构，线段树有将连续段分为 $O(\log n)$ 段的想法，相对较为接近，可以算作某种合理的语义扩充。类似地，各种平衡树原本也是专注于 BST 的功能，而在 OI 中同样常被视为维护列表的数据结构。（不过，显然至少从 link cut tree 开始就有将平衡树用于维护一般列表而非 BST 的想法了）
离散化
离散化，当然是想办法把连续的东西变成离散的东西来处理。这和对一堆数值按顺序标号有什么关系？
实际上，搜索较早时期 codeforces 中提及 discretization 的内容，可以发现全是中国大陆人发表的。（类似这样将中文 OI 方言翻译成其他语言的情况并不少见，“离散化”或许是最不容易在交流时意识到的）
它的起源或许也是误用了计算几何中的一些说法，但也尚未查明。
匈牙利算法
“匈牙利算法”和 Kuhn–Munkres 算法（OI 中常简称为“KM 算法”）是同一个东西。但在很长一段时间里，它被普遍误认为是指朴素的跑增广路计算无权图上二分图最大匹配的算法（这种做法一般就称为 Ford–Fulkerson）。
不过，现在搜索引擎的结果已经好很多了，不会像以前一样基本全是误用的 blog。
重量平衡树
出自 2013 年论文集，陈立杰的《重量平衡树和后缀平衡树在信息学竞赛中的应用》
我很困惑“重量平衡树”这个名称是怎么起的，不太像是随便起的名字。于是发了个邮件问陈立杰“重量平衡树”和“后缀平衡树”是什么来源，但也没回复具体是怎么回事
我的猜想是陈立杰看了 weight-balanced tree 的一些用法之后挪用了名字。但是陈立杰也没有介绍 weight-balanced tree 是什么东西，而是介绍了替罪羊树。
不过，我当时恰好看过 MIT 6.851，里面介绍 weight-balanced tree 时甚至提到了最早的名称 BB[α] tree，但后面的介绍也是替罪羊树。有点怀疑其中是否有什么联系。
此外，2014 冬令营讲课课件中陈立杰中将其翻译为 weight BST。
WBLT
顺带一提，后来 OI 中传播的 weight-balanced tree 的变种“WBLT”的这个名字最早是我使用的（）当时在想把原始信息都存在叶子上而非内部结点上的树该叫什么，灵机一动想到用 leafy 形容，然后一搜发现哇真的有 leafy BSP tree 这种说法，就顺理成章地这样叫了。不过当时在 WBLT 和 LWBT 两种简称中不确定哪种更好，最终历史纯属偶然地选择了 WBLT。让现在的我决定的话，其实会尽可能称为 leafy WBT，指出 leafy 是一种通用的信息存储方式，而这里只是将这种方式用在 WBT 上。
虚树
一看就像是纯属历史偶然从临时称呼变成了专有名词。起源很可能是 2013 年集训队解题报告中陈立杰的《JustForFun EXT 解题报告》，随后 2014 年论文集徐寅展的论文中做了专门的介绍，由此以“虚树”的名称传播开了。目前没有发现更早的资料。
圆方树（处理点双连通性的）
出自 2017 冬令营，陈俊锟与钟知闲的营员交流。当时重点在处理仙人掌的“圆方树”，而处理点双连通性的称为“广义圆方树”。在 2017 年论文集陈俊锟的论文中再次提及，直接称为“圆方树”。在 2018 冬令营陈俊锟的讲课《平凡的圆⽅方树和神奇的(动态)动态规划》再次介绍。
这么基本的描述图的点双连通结构的东西显然不会没有人发现（它只是“点与点双连通分量的关联二部图”，即二部图两侧分别为点与点双连通分量，点属于某个分量就连一条边）。在图论算法资料中，我能找到的最早的资料为 1989 年 Jeffery Westbrook and Robert E. Tarjan. Maintaining Bridge-Connected and Biconnected Components On-line，其中称为 block forest。图论中较早的资料常常把点双连通分量称为 block，因此按 OI 风格直译大致是“点双森林”的意思。要像“圆方树”一样称为树的话就是“点双树”。
有人说上面论文中也把 block forest 画成圆点和方点，某种意义上也是“圆方树”。但实际上，论文中的圆点和方点和“圆方树”所说的是相反的。
以下部分解释为什么没有更早提出单独的名称，无关心的话可以跳过。
懒得自己写了，让 claude 帮了下组织语言。点双连通分量太长了，就用旧名称 block 了。
追溯下去会发现一个有点反直觉的事实："包含所有点"的版本在思想史上其实更古老，它来自图论之前的点集拓扑；反而是图论把它"退化"成了只含割点的版本并率先命名。下面按时间线梳理。
1920–30 年代：拓扑学中的 cyclic element 理论。点双连通分解的思想最早出现在图论之外。Whyburn 于 1927 年引入 cyclic element 的概念来刻画 Peano 连续统的结构，1930 年 Kuratowski 与 Whyburn 将理论简化为成熟形态，其核心结论是：连续统的 cyclic elements 以树状方式组织起来——本质上就是后来图论中 block 分解结构定理的拓扑版本。
值得注意的是，在拓扑语境下不存在"只保留割点"的选项：每个点要么落在某个非退化 cyclic element（大致对应图论中的 block）中，要么自身就是一个退化的 cyclic element。换言之，"所有点都参与树结构"在这一原初版本中是默认形态。图论后来也直接承接了这套术语：Tutte 1966 年的书中就把 block 称为 cyclic elements。
1932：Whitney。图论一侧的起点是 Whitney 的工作，他证明了图可唯一分解为极大不可分子图（即现代语言的 block）。这条结构定理连同它的全部细节——每条边恰属一块、两块至多交于一个割点、块间不成环——可以浓缩为一句话：“点与 block 的关联二部图”是个树（非连通图则为森林）。不过 Whitney 本人并未以树的语言陈述它；树的视角要等到三十年后才被明确说出。
1964–1969：割点版获得名字并定型。Gallai 于 1964 年系统研究了 block 与割点之间的关系，他证明的一批计数恒等式（如连通图中 Σ_v (b(v) − 1) = b − 1，其中 b(v) 为包含点 v 的 block 数）用今天的眼光看，恰是"点–block关联二部图是树"的数值形式——全点版的结构此时已被实质证明，只是无人把这个二部图本身当作对象。1966 年 Harary 与 Prins 给出了 block-cutpoint tree 的名称，但它只含割点与 block；同年 Tutte 的书中称之为 cut-tree，后来 Bondy–Murty 2008 年的教材则称 block tree——这个概念直到今天也没有统一的名字。
真正令其流传开的是 Harary 那本 Graph Theory——它是 1970 年代事实上的标准图论教材，而 Harary 本人正是图论术语的标准化者（"block"一词似乎即出自他 1959 年的论文），经此一书，割点版及其名字成了两代人的默认语言。这带来一个微妙的后果：全点版与割点版仅相差一圈"平凡的叶子"，任何需要前者的人都会觉得这只是个不值得命名的局部改动——于是在此后几十年里，全点版不断被各个社区独立使用，却始终没有争得一个统一的名字。
1976：Kulli 的 block-point tree。第一个正式命名全点版的是 Kulli，他属于研究 graph-valued functions（线图、全图一类图算子）的学派，block-point tree 是他一系列"点 ∪ block"型图算子中的一员，而非对割点版的刻意修正。此时割点版已借教科书定型十年，这篇发表于小众期刊、动机也偏离主流的论文没能改变命名格局。
1989：算法界的重新发明。Westbrook 与 Tarjan 在增量维护 block 的问题中再次构造了同一结构，称之为 block forest。这一次全点版是被数据结构的需求逼出来的：加边会合并 block、令割点失去割点身份，只定义在割点上的树连定义域都不稳定，而全点版在 block 收缩下封闭，且查询的参数本就是任意点。
之后：持续的重造。同样的结构此后仍在互不引用的社区里反复出现：中国算法竞赛界的"圆方树"、奇点理论论文中的 brick-vertex tree，都是它。回望整条线索，故事的形状是清晰的：拓扑学里全点版是原生形态（1927–1930）；图论将其组合化时，因为非割点叶子在组合上确实"平凡"，名字落在了割点版上（1964–1969），并借 Harary 的教科书定型；此后全点版至少被独立命名了四次（Kulli 1976、Westbrook–Tarjan 1989、圆方树、brick-vertex tree），每次动机各异——图算子、动态数据结构、竞赛技巧、奇点理论——却始终无人打破 block-cutpoint tree 占据的教科书位置。一个概念可以被反复证明、反复使用、反复命名，却因为一个"足够近似"的近邻先占了名字，而在半个多世纪里保持匿名。
动态动态规划（动态 DP）
上文提到和圆方树一起介绍的，就一起说了。我对这个名称本身的感觉其实还好，不过感觉目前所有例题都能更直接地解释成有组合意义的信息合并。不知道现在有没有不能直接解释的题。
（如果不了解树上数据结构的信息合并的话，原理可参考 https://negiizhao.blog.uoj.ac/blog/4912 。不是说要写 top tree，只是发挥 top tree 的功能需要理解树上信息合并，所以其中很多内容只是解释信息合并道理）
猫树
你知道的，我对陈俊锟的这些意义不明的命名方式意见有点大的……虽说可能是个人感受吧。
不过这类东西似乎确实没有现有的名称。如果要归为更大的类，它可以视为分治的“在线化”或“记忆化”。当然这种思路不局限于“猫树”这样对序列或树进行分治，例如划分树也可以视为“在线化”的方法。
整体二分
上面“猫树”我原本写的是“整体二分”的“在线化”，写完突然意识到自己想的“整体二分”其实是个更一般的东西，也就是每个查询最多丢到一个子问题里，而不一定是按二分的结果分治。划分树确实是“整体二分”的在线化，但在“猫树”中确实并不是“二分”。并且意识到“整体二分”其实也是一个 OI 方言……
若不限于二分，将其统一到一般的语境下，即分治同时处理多个查询，是否有合适的称呼？也许不必使用专门的名字，但如果需要的话，“批量查询分治”似乎比较准确。若要与现有称呼妥协一下就是“整体分治”。不过，“整体二分”的例子仍然值得专门提及。“CDQ 分治”或许同样可以算作其中的一个子类。
FWT
FWT 仅对应 xor 卷积，与 or 和 and 卷积对应的常常称为 FMT（还有其他称呼，稍后再解释）。
我怀疑最初的混淆来自 Picks's Blog，里面将所有东西都称为 FWT。而后来 2015 年论文集吕凯风的《集合幂级数的性质与应用及其快速算法》中正确地分别称为 Walsh transform 和 Möbius transform。或许不同资料来源导致了 FWT 与 FMT 的混乱。
至于有人说 FWT 与 FMT 是指不同写法那更是完全没有道理，换其他东西实现不同做个区分还好说，两种写法只是循环枚举的写法长得不同，实际最内层语句做的事完全一样，实在没有必要起完全不同的名字。
不过，Walsh transform 和 Möbius transform 确实各自有几种不同的叫法。Walsh transform 可以参考 Wikipedia。Möbius transform 则和组合学有关，可以将 Möbius 反演公式推广到任意的局部有限偏序集里，相应变换也仍然称为 Möbius 变换和 Möbius 反演。若在半格上则可以对应半格运算的卷积。（例如经典的数论 Möbius 变换对应 gcd 卷积和 lcm 卷积）也有作者将变换和反演称为 zeta 变换和 Möbius 变换。（在数论 Möbius 变换中，分别对应数论函数乘上 zeta 函数和 Möbius 函数）对于这里所说子集上的 Möbius transform，也有资料称为 arithmetic transform。
树链剖分
最初起源为 link cut tree 的复杂度分析，将边分为了重边和轻边，但并没有为这个技术命名。我找到的最早的资料 1998 年 Dynamic 2-Connectivity with Backtracking 称其为 heavy path decomposition。2005 年 MIT 6.897 Lecture 5 称其为 heavy-light decomposition。随后 2007 年杨哲的《SPOJ375 QTREE 解法的一些研究》使用了 heavy-light decomposition 的叫法并翻译为轻重边路径剖分。2009 年集训队论文《分治算法在树的路径问题中的应用》仍然称其为“轻重边路径剖分”。而按 noip 吧记录，2011 年已经普遍使用“树链剖分”这个叫法了。
早年发生的事已经几乎不可考了，blog 和 OIBH 带走了太多历史资料，很难确认“树链剖分”这一叫法的起源，以及什么时候口语中几乎完全使用“树链剖分”这一称呼了。
不过，后来随着 long path decomposition 的传播，逐渐演化出了“重链剖分”和“长链剖分”的叫法，也算是稍微往原本的叫法回归了一些。考虑到描述性以及 long path decomposition 的说法，我认为 heavy path decomposition 确实是更好的称呼。
不过如果要较为正式地（像图论教材一样地正式）进行翻译的话，path 应翻译成路径，decomposition 通常翻译成分解（不知为何最初翻译成了剖分，或许是受到“三角剖分”的影响？），因此或许会称为“重路径分解”和“长路径分解”？
FHQ Treap
起源为冬令营范浩强讲课介绍了怎么纯函数式地实现 treap（但我认为纯函数式语言里实现插入删除也不会用原文写的大常数方法）。
我实在没有明白（在不讨论具体实现方法时使用）这个词的意义。首先 1989 年 Treap 原论文 已经指出了 treap 合并分裂的复杂度，1996 年版本 进行了更详细的介绍，包括一些更特殊的用法。而实现了插入删除的 treap 也可以轻松实现合并分裂，分裂只需要在分裂位置插入个优先级最大的点，然后取根的左右子树即可，合并则相反。在我看来无旋只是一个实现方式，讨论实现本身可能有说法，但平时解决问题的话，实现方式似乎并没有带来任何功能优势？
主席树
起源为黄嘉泰发现了一种计算区间第 k 小值的做法，被人称为主席树。
即使是在 OI 语境中也建议尽量避免使用这个词。这个词出来时是没有被赋予定义的，它的意思是在使用过程中产生的，而每个人有自己的理解。有人理解成区间k小值的做法，有人理解成函数式线段树，有人理解成持久化线段树，有人理解成持久化权值线段树。交流的时候很容易造成混乱。
即使在发生了一些混乱后，一部分人统一成了持久化权值线段树，但仍有大量历史遗留资料，可以注意到甚至上文第一个喊出“主席树”的 blog 都不可以解释成“持久化权值线段树”的意思。
例如，当年很多人用“带修主席树”或“树状数组套主席树”指带修区间k小值的做法，在他们看来“主席树”和上文一样就是线段树相加减得到区间权值信息的技巧。这导致后来的人看得一头雾水，不知道哪里有持久化，更不用说初学者面对这些资料时的感受了。
链式前向星
出自 Malash 的课件，blog 里有截图。
前向星是 forward star 的翻译，原本意思指一个点的所有出边的集合，相应的所有入边的集合称为 backward star 或 reverse star。此外也有资料称为 star 和 costar。也有作者用 forward star 和 backward star 来指子图而非边集。
或许与之相关的，star graph 的意思是 OI 方言里的“菊花图”。与前面的相对“冷门”（论文或较为深入的书里才会提及）的概念相比，star graph 是公认的术语。
一些资料里会提及图的 forward star representation 或 forward star data structure，意思是用存下 forward star 的方式来存储图，实际上与邻接表是同一个意思。不过也有些作者会区分邻接表和前向星，认为邻接表使用链表而前向星使用数组。
（图论的术语就是这么混乱……连 walk/path 和 path/simple path 都没有统一呢，目前仍有必要在提及之前对相关术语进行约定。）
因此，“链式前向星”无非是使用的列表为数组下标模拟指针的链表的邻接表。而 OI 中说的“前向星”大致来自于一些大学的课件，这些课件又是由区分邻接表与前向星（或者介绍前向星时给出了具体实现方式）的英文资料翻译而来。这样“前向星”的含义就演变成了相应的具体实现方式。
不过，“邻接表”一词不指定列表实现方式的用法也很常见。因此也可以完全不使用“前向星”和“链式前向星”二词，在必要时说明具体的实现方式即可。与之类似，另一个例子，现在常见的使用 std::vector 的存图方式无非是用 std::vector 实现列表的邻接表。
DSU
Disjoint Set Union 一听就是一个问题的名称，而不像是数据结构的名称，不知为何一些资料说是并查集的意思。
早在 1977 年 Robert Endre Tarjan 的 A Class of Algorithms which Require Nonlinear Time to Maintain Disjoint Sets 中，就正式将并查集所解决的问题称为了“The Disjoint Set Union Problem”。
见过很多人提出困惑“dsu on tree 和 dsu 其实一点关系都没有”，我不知道“dsu on tree”的称呼从何而来，但若把 dsu 解释为问题则相当自然，无非是加强了一下原问题，即需要支持查询关于某集合的一些信息。
OI 中常常把这类问题称为“启发式合并”，“dsu on tree”也就常被翻译为“树上启发式合并”。其实，“不相交集合合并”更像是对问题的描述，而“启发式合并”偏向于解决方法？
叉积
对于数学家来说，叉积一般只对 $\mathbb{R}^3$ 向量说，有时也会对 $\mathbb{R}^7$ 向量说，即使谈论推广也不会提及有 OI 中这样的“二维叉积”。OI 中的“二维叉积”会被直接称为 $\det$。
但 NumPy OpenCV 等库里也这样干了，提供了对二维向量算叉积的功能。
甚至算法导论也将其称为“叉积”，并且直接定义为 $\det$，而又在脚注里解释叉积其实是三维的概念，说明这确实不是完全恰当的说法，属于“方言”。
这大概已经不只是 OI 的方言了，阅读过相关资料、使用过相关软件功能的人都可能会认为可以对二维向量算叉积。或许是因为作者不知道数学中对多个 $\mathbb{R}^n$ 向量已有 $\det(v_1, v_2, \dots, v_n)$ 的写法（只要指定了一组基就可以这样写，这里是 $\mathbb{R}^n$ 自带的标准基），所以自行借用了“叉积”的名称。
exCRT, exLucas
一看就是对着 exgcd 编的名字。
从原本意思来说，CRT 是个定理，而我们常说的是其实是一种证明方法中所使用的具体构造，“ex”的 CRT 自然说不通。而 Lucas 定理也是众所周知和“exLucas”没有直接关联。显然都是遇到更一般的问题时想了对应的解决方案，并称为原做法的“ex”版本。
最初来源待调查，比较久远
单位根反演
可能与 vfk 的 炫酷反演魔术 有关。vfk 指出，很多常见的“反演”常常与把 Iverson 括号写成一个求和式有关，并且在文中提到了 IDFT 对应的 $\frac{1}{n}\sum_{k = 0}^{n - 1} \omega^{vk} = [n \mid v]$。
然而，vfk 也指出反演是指 $f(n) = \sum_{k} a_{n, k} g(k)$ 的反向变换，并不是指推导中的关键步骤“把 Iverson 括号写成一个求和式”。非要说反演的话，这里也应是 IDFT。
最初来源有待调查，我认为时间是 2018 年上半年。之后的一个重要事件可能是进了洛谷日报的 （也许是）冷门算法——单位根反演，它所引用的 【4.13 提高班小记】单位根&&杂题 也出现了“考虑用单位根反演它”的说法。可以看出最初的几年里它被用来指代入 $k$ 次单位根来计算 $\sum_{i} [x^{ik}] f(x)$ 的方法（其实无非是计算长度为 $k$ 的 DFT，然后只计算 0 处的 IDFT）。但可能因为大家总是先强调 $\frac{1}{n}\sum_{k = 0}^{n - 1} \omega^{vk} = [n \mid v]$，它的意思逐渐（在一部分资料中？）演变成了这个式子。