什么是线段树分治？

线段树分治是一种离线处理问题的强大技巧。它适用于一类问题：存在一系列操作（或查询），每个操作只在某个时间段内有效。我们无法高效地在线处理这些有时效性的操作，但可以离线地将所有操作和查询读入，然后利用线段树的结构来处理它们。

核心思想

我们将时间轴看作一个大的区间，然后建立一棵线段树。对于每一个有时效性的操作（例如，在时间 [t_start, t_end] 内添加一条边），我们不直接执行它，而是将这个操作“挂”在线段树上对应的 log(T) 个节点上。

具体步骤如下：

什么是快速排序？

快速排序是另一种基于分治思想的排序算法。它通过一个“基准”(pivot)元素将数组分区，然后递归地对基准左右两边的子数组进行排序。

算法步骤

1. 选择基准 (Pivot): 从数组中选择一个元素作为基准。
2. 分区 (Partition): 重新排列数组，所有比基准小的元素都移动到基准的左边，所有比基准大的元素都移动到右边。
3. 递归 (Recurse): 递归地对基准左右两边的子数组进行快速排序。

什么是归并排序？

归并排序是一种高效的、基于分治思想的排序算法。它将一个大问题分解为多个小问题来解决。其核心操作是“归并”，即将两个已经有序的序列合并成一个有序序列。

算法步骤

1. 分解 (Divide): 将当前数组一分为二，直至每个子数组只有一个元素（此时可认为是有序的）。
2. 解决 (Conquer): 递归地对两个子数组进行归并排序。
3. 合并 (Combine): 将两个已排序的子数组合并成一个大的有序数组。