前情回顾。因为学了 PQ-Tree 而 zhy 提起析合树与 PQ-Tree 类似的结构关系于是就去又看了下析合树。
这个算法太有用了！至少比 PQ-Tree 有用多了！析合树是处理排列连续段问题的利器。其实还是没用
对于一个排列的子区间，如果它的值域也是一段长度相同的区间的话就称为它是该排列的连续段。记一个排列的连续段集合为 \(I_p\)。然而 \(|I_p|\) 是 \(O(n^2)\) 级别的，不易于维护。
我们观察连续段的性质，发现它很类似于 PQ-Tree 的集合连续限制：对于两个非平凡相交的连续段 \(I_1,I_2\)（非平凡相交即 \(I_1\cap I_2\notin \{\emptyset,I_1,I_2\}\)），\(I_1\cup I_2\) 在 \(I_p\) 中。
因此我们只需要考虑那些不跟其它段非平凡相交的连续段（称之为“本原段”），依据包含关系建出树，这就是析合树。
标签：PQ,Tree,笔记,学习,排列,连续,析合树,平凡 From： https://www.cnblogs.com/yyyyxh/p/devide-combine_tree.html