RMQ & LCA

RMQ

1.理解了rmq的st算法。就是将每个大区间用刚好大于其长度一半的2^x的大小来将其分割为两个有重叠区间求解。即s~t被分为s~s + 2^x 和 t - 2^x + 1 ~t。吉大的第一个st是错误的。

2.学会了笛卡尔树，它每个结点有两个值，根据第一个值，它是一颗二叉搜索树，根据第二个值，它是堆（不一定是完全二叉树）。如果我们认为第一个值是数组下标，第二个值是数组对应位的值的话，这课树的两个结点的lca的第二个值就是两结点的第一个值在数组中划定的区间的rmq。我们通常是由一个数组来构建笛卡尔树，从左至右依次将数组中的每个元素加入树中，由于新加入的结点的下标是最大的，所以它一定位于搜索二叉树的最右端。而之前位于最右端的是上一个加入的结点，所以我们就从上一个加入的结点开始向其父亲不断推进（当前将加入的结点不可能在上一个结点的下方，因为所有下方的结点来说，无论当前结点插在哪里都永远在上一个结点的左边；而对于其父亲和祖先则可以经过如下调整使当前插入结点在最右端），找到一个比（对于大根堆）它大的，把该结点的右儿子变为当前插入结点的左儿子，再把当前结点改为其右儿子。

LCA

lca问题，离线的方法用tarjan

tarjan算法的流程如下。dfs遍历树，用并查集的方式，在当前dfs路径中找到一个点，这一点是遍历完成的点的祖先，而且这点的深度最大。把遍历完成的点合并到这个点，即这个点变成遍历完成的点的并查集中的father。这样，根据dfs的性质，可以知道，遍历完成的点其与当前正在遍历的点的lca即为其并查集中的祖先。实际操作的方法是对于一个结点，dfs每个子结点，然后把每个子结点合并到其本身。在此过程中顺带回答所有lca问题。

在线LCA有两种方法，第一种比较常见，即将其转化成RMA问题。先对树形图进行深度优先遍历，遍历过程记录路线中点的途经序列，每个非叶子节点会在序列中出现多次，从一个节点A的一个子节点回到A点再走另一个子节点的时候要再次加A加入序列。记录序列的同时还要记录序列中每个点在树中对应的深度。以及在序列中第一次出现的位置（其实不一定非要第一个才行），主要用于根据点标号查找其在序列中对应的下标。此时，LCA已经转化为RMQ，如果要求a,b的LCA，只需要找到a,b在遍历序列中分别对应的位置，并在深度序列中查找以这两点为端点的区间内的最小值即可。这个最小值在遍历序列中对应的点就是他们的LCA。这种方法预处理O(NlogN)，查询是O(1)。

另一种方法用到了DP的思想。用一个数组f[i][j]表示i点在树中到根节点的序列中距离i边数为2^j的点。那么f[i][j] = f[ f[i][j - 1] ][j - 1]。具体做法是，我们进行BFS，记录每个点的父节点，即f[i][0]。和每个点的深度。然后根据状态转移公式填充整个数组。在查询时，先看a,b两点谁的深度大，利用两者深度差的二进制序列，配合f数组，找到较深的点在较浅的点那层的祖先。然后继续使用f数组，每次向上探测2^i的距离的点两者的祖先是否为同一个，如果不是则i++后继续叠加向上探测2^i，如果是同一个则i--后重新探测。直到找到最小的公共祖先为止。这种方法预处理O(NlogN)，查询是O(NlogN)。但与上一种方法相比，不需要dfs，而用bfs，这样可以节省很多时间。