并查集

原文oi wiki:并查集

基础

介绍

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。 顾名思义，并查集支持两种操作： 合并（Union）：合并两个元素所属集合（合并对应的树） 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合 路径压缩

启发式算法是什么呢？ 启发式算法是基于人类的经验和直观感觉，对一些算法的优化。 说白了,用思维去强行干碎(不是)复杂度

树上启发式合并

原文oi wiki:dsu-on-tree 我们考虑树上的离线问题或者是其他情况可以从树上dp的角度去思考：

例题

例题1 例题2

原文oi wiki:st表

原理十分简单

基于倍增思想，我们考虑如何求出区间最大值。可以发现，如果按照一般的倍增流程，每次跳 $2^i$ 步的话，询问时的复杂度仍旧是 $\Theta(\log n)$，并没有比线段树更优，反而预处理一步还比线段树慢。我们发现$\max(x,x)=x$，也就是说，区间最大值是一个具有「可重复贡献」性质的问题。即使用来求解的预处理区间有重叠部分，只要这些区间的并是所求的区间，最终计算出的答案就是正确的。 如果手动模拟一下，可以发现我们能使用至多两个预处理过的区间来覆盖询问区间，也就是说询问时的时间复杂度可以被降至 $\Theta(1)$，在处理有大量询问的题目时十分有效。

线段树

原文oi wiki:SegTree

简述

线段树（Segment Tree）是一种二叉树结构，主要用于高效地维护区间信息，例如区间和、区间最值、区间最大公约数等等。

你可以把它当作一个比树状数组（Binary Indexed Tree）更万能的数据结构，因为它不仅支持单点修改和区间查询，还可以通过扩展支持区间修改、区间最值查询等操作。