【每日一题】3月31日题目精讲 树上倍增 ST表

void rmp_st(int n) //预处理ST表,数组中有n个元素
{
    for(int i = 1; i <= n; i++) f[i][0] = a[i];
    int m = (int)(log((double)n) / log(2.0));
    for(int j = 1; j <= m; j++)//先循环j再循环i，因为必须要把长度为1的区间都算出来了才能求长度为2的
    for(int i = 1; i+(1<<j)-1 <= n; i++)
        f[i][j] = min(f[i][j-1], f[i+(1<<(j-12))][j-1]);
}
int rmp_find(int l, int r)  //求区间 l 到 r 之间的最值
{
    int k = (int)(log(1.0 * (r-l+1)) / log(2.0));
    return min(f[l][k], f[r-(1<<k)+1][k]);
}

------------------------------------------------以下是本题题解的分界线-------------------------------------------------

做题的第一步是好好读题，而在读题过程中你需要将题目的信息转化成对你解题有用的信息，比如所“假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。”这句话实际上是说明你买到的珠宝的价值是递增的，而且请注意，不是求最长上升子序列哪一种，而是只要递增了就要选，而这个递增呢就会告诉你，如果你在A城市买了珠宝，那么从A往上走下一次在哪里卖珠宝或者你从A往上走x个城市能买到几个珠宝和你是从哪里走到A的并没有关系，而当我们从A 往上走的时候，A上方比他小的点也是没有意义的。

考虑用表示从i往上走，能买珠宝的第个点是哪个，显然，如果我们知道每个的值， 那么 ( 往上的第个点再往上个点)。那么怎么求呢？肯定不能暴力，因为暴力最坏情况可能会让你每次都跑到根（构造一条链，从根到叶子价值递增）。这个其实也可也倍增着跳——如果 的父亲fa比 大那自不必说，当i的父亲fa比 小，那么我们可以看fa的父亲向上走（k从大到小枚举）个能买进的点的权值（即），如果这个点权限比 点权值小，说明还需要往上走，就跳到f[fa] [k]上并把跳跃的长度减少一半(如果还是刚刚的跳跃高度，从f[fa] [k]往上跳长度，实际上就是从fa跳，相当于就是跳到了）；如果这个点的权值比 大，说明跳多了，就只是把跳跃长度减少一半再看。

注意我这里说的跳跃长度都是按照能买东西的点的个数计数，相当于我的f数组其实是对原树进行了重建，每个点往上走1步都的连向的它能到的第一个比他大的点（这样理解也许会容易很多——即我们对原树进行变形，每个点都连向它上方第一个能买东西的点，构成一个新的森林，于是问题就变成了，从u走到自己上方深度不小于dep[v]的点需要经过多少个点）。

有了这个值之后我们要求从 u 往上走到 v 经过了多少点，也可也倍增去求了——即从 u 出发尝试往上跳 高度，如果已经跳过 v 了，就减小 k，如果没有跳到 v 的上方，就先跳上去再减小 k。 注意，因为f数组存的能买东西的点，很有可能v根本不在这里面，所有跳的时候是通过判断深度来判断是否结束的。

我手算了一组样例帮助大家理解，我记得是lrj的紫书里面说过，学习数据结构最好的办法就手画，希望大家能动起手来，多写写多画画。

代码可戳我查看~

------------------------------------------------看过大家题解之后的补充-------------------------------------------------

本道题目4月7日中午12：00之前写的题解有获得牛币资格~

牛客博客开通方式