倍增算法

倍增算法

【序言】

        我认为吧，所有能够优化复杂度的算法都是神奇的，所有能够化繁琐为形象的文字都是伟大的。一直觉得倍增算法是个很神奇的东西，所以决定写点东西纪念一下它。但是作为一个非常不称职的OIER，我非常讨厌在看别人的算法解析时整版的i，j，k等我看到鼠标就惯性移到右上角的符号语言，所以我想用最形象的方式来纪念它。

【一】

        从前，有一只可爱得不得了的小白兔，它想从A地去往遥远的B地。

        2B小白兔：

            向右边跳一步，左边跳一步，再向右边跳很多步，再……（对不起，这个太脑残了）

        普通小白兔：

            向右边跳一步，再跳一步，再跳一步……再跳一步，哇，到了！好开心！

        超级小白兔：

            向右边跳一大步，一步跳到B，然后默默回头，鄙视一下那只一步一步跳的小白兔。

        我相信作为一个正常人，是不会考虑到2B小白兔的这种做法的，因为它太脑残了。

        同时我也相信，作为一个正常人，也不会考虑到超级小白兔的这种做法的，因为……

            “我擦！你什么时候说可以这样跳了！（愤怒）”

            “我什么时候说不可以了！（卖萌）”

        但是你不得不承认，超级小白兔还是有两把刷子的，因为它真的是太厉害了，厉害得你想都没有想到。

【二】

        从前，有一只可爱得不得了的小白兔，它想从A地去往遥远的B、C、D、E、F这几个让它魂牵梦萦的地方。（不要问我从哪里来，我的梦想在远方）

        2B小白兔：

            （对不起，我的生命有限，我不想再提到它了）

        普通小白兔：

            一步又一步，生命不息，跳跃不止。

        超级小白兔：

            一步到B，再一步到C，再一步到D，再一步到E，再一步到F，完工。

        你不用解释，我深知你就想当那只超级小白兔，哼，你肯定是那样跳的。（神马？不是？兄弟你的智商我救不了了……）

        是的，不这样跳的人对不起社会啊，浪费时间就是浪费青春，浪费青春就是犯罪。

        好的，既然你是这样跳的，那你能告诉我你是怎么知道从A只要跳2个格子就会刚好到B的？难道你在空中使用了GPRS全球卫星定位系统？你少来好么！主页君现在都没用过这种东西，你一只白白嫩嫩下酒菜的小兔子还用这个？笑死我吗？哈哈，你一定是出发前就偷偷学普通兔子一步一步跳过一遍，然后拿个本子做小抄，记录好从每个格子跳任意步会到达的地方，然后赶在天亮之前回来，风光的按照踩点计划大步的跳，让我们觉得你很厉害的样子，我没说错吧？不过看在你有这个诚心的份上，还是为你的聪明鼓掌吧。

【三】

        从前，有一只可爱得不得了的小白兔，它想从A地去往遥远的1（此处省略很多0）个地方，因为它真的是太没事情做了。

        普通小白兔：

            从离开家门的那天起，我就没有想过要放弃一步一步地跳往终点。（嗯，加油）

        超级小白兔：

            轻轻松松，绝不多走一步。（哼哼）

        你想知道最后的结果吗？呵呵，好像还没有出结果……

        写给普通小白兔的话：

            亲爱的小白兔，我知道你勇毅，你质朴，但是，苦海无涯，回头是岸。

        写给超级小白兔的话：

            我不知道你的小抄本是否还够用，我不知道你摸着黑就出门是为了什么，你不觉得你的行踪早就已经暴露了吗？你以为你很聪明吗？不，你错了，你就一下酒菜，永远都是，因为你不知道倍增算法，这是你失败的根源，再见，我心中永远不会逝去的蠢兔子。

---------------------------------------------------------------------------------------------- 卖萌分割线 ----------------------------------------------------------------------------------------------------

        普通兔子 = 速度慢，无资源损耗 || 超级兔子 = 速度快，多资源损耗

        还记得那只离我们远去的2B兔子吗？对，其实我们早该想到了，越蠢得不可思议的兔子身上竟然有巨大的宝藏，再看看它的名字吧，“2B”！去掉一个“B”！就是“2”！对，你没有听错，就是“2”，你能想到4、8、16、32吗？

        再想想，超级兔子的小抄本不够用，不就是因为它为了应对所有的目的地信息，它记录下了任何一个格子跳任意步会到达的格子，100个格子它要记录大概5000条信息，1000个格子大概要记录500000条信息，10000个格子它大概要记录50000000条信息，至于你晕没晕，我相信它应该晕了。

        可不可以把记录的信息数降到最低呢？当然可以，2B兔子帮你忙，让你用2战胜敌人。

        当你只记录任何一个格子跳1、2、4、8、16……步会到达的格子的时候，你有没有发现信息数突然少了好多好多啊！真的少了好多好多啊！100个格子只要500条左右，1000个格子只要5000条左右，10000个格子只要50000条左右，不比不知道，一比吓一跳啊！

        安心小抄五十年，健康生活一辈子。

        从此，超级小白兔成为了聪明小白兔，它的生活是这样的：

        在夜深人静的时候，它偷偷出门做小抄，记录下从每个格子跳1、2、4、8……个格子后会到达的格子，然后在太阳出来后，它在众目睽睽之下，开始了表演。

        从A出发：若跳8个格子（超过B了，放弃）

                  若跳4个格子（超过B了，放弃）

                  若跳2个格子（没超过B，跳吧）

                  若跳1个格子（没超过B，跳吧）

        从B出发：…………

        多么轻松的事情，只要一本很薄的小抄就可以了，最关键的是：它绝对不会连着跳两步都是跳相同的格子数，因为如果跳两次2个格子都是可行的话，那么它干嘛不跳4个格子捏？

        我们可是从多到少来判断的啊！！

        好的，聪明小白兔白天的事情你已经看懂了，且看它晚上是怎么打小抄的吧。

        从A出发跳1步到1（记录下来）

        从1出发跳1步到2（记录下来）

        …………（跳1步的记录完毕）

        从A出发跳2步？就是从A出发跳1步再跳1步的到的地方，翻看小抄，直接誊写从1出发跳1步会到的2这个格子作为A跳2步会到的格子。

        从1出发跳2步？跟刚才一样，直接誊写。

        …………（跳2步的记录完毕）

        从A出发跳4步？你还真去跳4步？不，它也就是等于从A出发跳2步到的2号点再跳2步会到的格子，那么我们直接誊写2号格子跳2步会到的格子就可以了。

        ……

        ……

        看看聪明小白兔多么聪明！也许还有自认为更聪明的：

            “在记录A跳4步会到的格子的时候，为什么不直接从A跳4步看到了哪里再记录下来呢？跳4步跟跳1步的代价不是一样的么”

            “我这样回答你好了！把你丢在纽约的一个公交车站，问你一条线路的下一个站是什么？你怎么办？当然是自己亲自走到下一个站就知道了！那如果问你接下来的第4个站是什么？难道你可以直接走到第4个站而不用途径其它的站点了吗？这不现实，你还是要一个一个站的走，因为关键在于你只能知道你目前所在站点的下一个站是什么，想知道下下个站，除非你已经到了下个站，兔子跳格子也跟这类似，虽然聪明小白兔神通广大，但是不至于伟大到可以提前预知跳几步会到哪里啊！！”

        从此，聪明小白兔避免了成为人类的下酒菜，而被一群OIER们像神一样的供奉了起来，不要问它为什么，因为它也不知道，貌似只是某人卖了个小萌，事情就变成这样了。

                                                                                                                                                                                                            完

基本思想：（参考：from lanshui_Yang）

deep[i] 表示 i节点的深度, fa[i,j]表示 i 的 2^j (即2的j次方) 倍祖先，那么fa[i , 0]即为节点i 的父亲，然后就有一个递推式子：

fa[i,j]= fa [ fa [i,j-1] , j-1 ] 

可以这样理解：

设tmp = fa [i, j - 1] ，tmp2 = fa [tmp, j - 1 ] ，即tmp 是i 的第2 ^ (j - 1) 倍祖先，tmp2 是tmp 的第2 ^ (j - 1) 倍祖先 , 所以tmp2 是i 的第　2 ^ (j - 1) + 2 ^ (j - 1) =  2^ j 倍祖先，注意：这里的“倍”可不能理解为倍数的意思，而是距离节点i有多远的意思，节点i的第2 ^ j 倍祖先表示的节点u满足deep[ u ] - deep[ i ] = 2 ^ j。
这样子一个O(NlogN)的预处理求出每个节点的 2^k 的祖先

对每一个节点都记录走1,2,4,8.................步所能到达的距离，因为每一个点的操作是logn，所以预处理时间是O(NlogN)。

然后对于每一个询问的点对a, b的最近公共祖先就是：　

先判断是否 d[x]< d[y] ,如果是的话就交换一下(保证 x 的深度大于 y 的深度), 然后把 x 调到与 y 同深度, 同深度以后再把a, b 同时往上调,调到有一个最小的 j 满足fa [x,j] != fa [y,j] (x,y是在不断更新的), 最后再把(x,y)往上调(x=p[x,0], y=p[y,0])  ,一个一个向上调直到x = y, 这时 x或y 就是他们的最近公共祖先。

 Ps：如果还是不明白，就手动模拟一棵节点数为9的树（如下图所示），很快就会理解的。还有我不得不感叹一句 ：二进制真的很神奇！！                  
    1. #include<iostream>  
    2. #include<cstring>  
    3. #include<algorithm>  
    4. #include<string>  
    5. #include<cmath>  
    6. #include<vector>  
    7. #include<cstdio>  
    8. #define mem(a , b) memset(a , b , sizeof(a))  
    9. using namespace std ;  
    10. inline void RD(int &a)  
    11. {  
    12.     a = 0 ;  
    13.     char t ;  
    14.     do  
    15.     {  
    16.         t = getchar() ;  
    17.     }  
    18.     while (t < '0' || t > '9') ;  
    19.     a = t - '0' ;  
    20.     while ((t = getchar()) >= '0' && t <= '9')  
    21.     {  
    22.         a = a * 10 + t - '0' ;  
    23.     }  
    24. }  
    25. inline void OT(int a)  
    26. {  
    27.     if(a >= 10)  
    28.     {  
    29.         OT(a / 10) ;  
    30.     }  
    31.     putchar(a % 10 + '0') ;  
    32. }  
    33. const int MAXN = 10005 ;  
    34. const int M = 30 ;  
    35. vector<int> G[MAXN] ;  
    36. bool vis[MAXN] ;  
    37. int deep[MAXN] ;  
    38. int fa[MAXN][M] ;  
    39. int n ;  
    40. int root ;  
    41. void chu()  
    42. {  
    43.     mem(vis , 0) ;  
    44.     mem(deep , 0) ;  
    45.     mem(fa , 0) ;  
    46.     int i ;  
    47.     for(i = 0 ; i <= n ; i ++)  
    48.         G[i].clear() ;  
    49. }  
    50. void dfs(int u)  
    51. {  
    52.     vis[u] = true ;  
    53.     int i ;  
    54.     for(i = 0 ; i < G[u].size() ; i ++)  
    55.     {  
    56.         int v = G[u][i] ;  
    57.         if(!vis[v])  
    58.         {  
    59.             deep[v] = deep[u] + 1 ;  
    60.             dfs(v) ;  
    61.         }  
    62.     }  
    63. }  
    64. void bz()  // 倍增祖先  
    65. {  
    66.     int i , j ;  
    67.     for(j = 1 ; j < M ; j ++)  
    68.     {  
    69.         for(i = 1 ; i <= n ; i ++)  
    70.         {  
    71.             fa[i][j] = fa[ fa[i][j - 1] ][j - 1] ;  
    72.         }  
    73.     }  
    74. }  
    75. void swap(int &x , int &y)  
    76. {  
    77.     int tmp = x ;  
    78.     x = y ;  
    79.     y = tmp ;  
    80. }  
    81. int LCA(int u , int v)  
    82. {  
    83.     if(deep[u] < deep[v]) swap(u , v) ;  
    84.     int d = deep[u] - deep[v] ;  
    85.     int i ;  
    86.     for(i = 0 ; i < M ; i ++)  
    87.     {  
    88.         if( (1 << i) & d )  // 注意此处，动手模拟一下，就会明白的  
    89.         {  
    90.             u = fa[u][i] ;  
    91.         }  
    92.     }  
    93.     if(u == v) return u ;  
    94.     for(i = M - 1 ; i >= 0 ; i --)  
    95.     {  
    96.         if(fa[u][i] != fa[v][i])  
    97.         {  
    98.             u = fa[u][i] ;  
    99.             v = fa[v][i] ;  
    100.         }  
    101.     }  
    102.     u = fa[u][0] ;  
    103.     return u ;  
    104. }  
    105. void init()  
    106. {  
    107.     scanf("%d" , &n) ;  
    108.     chu() ;  
    109.     int i ;  
    110.     for(i = 0 ; i < n - 1 ; i ++)  
    111.     {  
    112.         int a , b ;  
    113.         scanf("%d%d" , &a , &b) ;  
    114.         G[a].push_back(b) ;  
    115.         fa[b][0] = a ;  
    116.         if(fa[a][0] == 0)  
    117.         {  
    118.             root = a ;  
    119.         }  
    120.     }  
    121.     deep[root] = 1 ;  
    122.     dfs(root) ;  
    123.     bz() ;  
    124.     int u , v ;  
    125.     scanf("%d%d" , &u , &v) ;  
    126.     printf("%d ", LCA(u , v)) ;  
    127. }  
    128. int main()  
    129. {  
    130.     int T ;  
    131.     scanf("%d" , &T) ;  
    132.     while (T --)  
    133.     {  
    134.         init() ;  
    135.     }  
    136.     return 0 ;  
    137. }  

参考：

【白话系列】倍增算法 - CSDN博客
http://blog.csdn.net/jarjingx/article/details/8180560

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Renyi-Fan/p/8142711.html