有没有一段代码，让你觉得人类的智慧也可以璀璨无比？

我在这里提供我见识到的三个精彩算法的解析，强烈地推荐给初学的算法爱好者，它们可能会令你眼界大开，同时坚定你在算法大道上勇往直前的信念。

#3. 二进制是人类的好朋友，在线的树的最近公共祖先（LCA）算法：

利用数的二进制表示可以产生很多加速算法，online-LCA是其中之一。许多算法的加速是对数率的，就是利用了数的二进制表示。

首先定义二维数组：prede[N+1][B+1], N表示树的结点的数量，结点以数字1到N代指，B满足条件：2^(B)>=N

令fa[i]表示结点i的父结点，那么prede[i][b]的含义是：

prede[i][0] = fa[i];prede[i][b] = prede[prede[i][b-1]][b-1]; // b >= 1

也就是说，prede[i][b]指的是从结点i往上走2^(b)步，所到达的结点。如果走到了尽头，就令prede[i][b]为0。

我们只需要O(NlogN)的复杂度，就可以完成prede的初始化。此外，我们还需要预处理出所有结点的高度，也就是depth[i]，定义为：

depth[root] = 0;depth[i] = depth[fa[i]] + 1;

当遇到询问LCA(x, y)，我们只需要采取如下行动，就可以O(logN)的代价获得答案：

int lca(int x, int y) {    if (depth[x] > depth[y]) swap(x, y);    for(int i = B; i >= 0; i --){      //令x和y高度一致      if (depth[prede[y][i]] >= depth[x]) y = prede[y][i];    }    //注意此时有可能出现x == y，那么LCA(x,y) == x，下方的for    //就不起作用了。    for(int i = B; i >= 0; i --){      //如果prede[x][i]和prede[y][i]不相同，说明这两者的高度      //都大于所求的LCA(x,y)，也就是在LCA(x,y)的下方，此时令      //x和y一同往根部以2^(i)的步数爬升      if (prede[x][i] != prede[y][i]) x = prede[x][i], y = prede[y][i];    }    if (x == y) return x;	//此时LCA（x,y) = x    return prede[x][0];	  //此时x和y有共同的父结点}

上述代码的精髓在于两个for(int i = B; i >= 0; i --)，这里利用了数的二进制表示。可以证明，对于任何严格小于2^(B+1)的非负整数t，下面的代码运行之后可以令a == t，

int a = 0;   for(int i = B; i >= 0; i --){     if(a + (1<<i) <= t) a += (1<<i);}

#2. 集合之交，树状数组，动态更改、查询数组前缀和算法 。

实现树状数组所需的代码极为简易，实际上它是一棵残缺的线段树，它可以实现一部分线段树的功能（但凡可以化为区间求和的问题基本上都能解决），但是毕竟不如线段树功能完整，有兴趣的读者应该学习一下线段树的知识。

问题描述：利用预处理的前缀和数组pre[N + 1]，我们可以O(1)的代价对静态的数组A[N + 1]求取区间和：

pre[i] = A[0] + A[1] + A[2] + ... + A[i];

A[a] + A[a+1] + A[a+2] + ... + A[b] = pre[b] - pre[a-1];

但是当需要对数组A进行动态的更改时，上述代码就失效了。我们需要一种算法，可以动态地更改以及查询前缀和数组pre[N+1]。下面首先展示树状数组的代码，然后解释其数学原理，它的插入和查询的代价都是O(logN)：

int Count[BiggestN+1], N; //使用前令Count所有元素为0，规定A[0]没有数              //据，也就是说数据从A[1]开始存，pre[0]总为零//实现功能A[i] += addvoid insert(int i, int add){  while( i <= N )  {    Count[i] += add;    i += i&(-i);  }}//返回pre[i]的值int query(int i){  int num = 0;  while( i > 0 )  {    num += Count[i];    i -= i&(-i);  }  return num;}

算法中最关键的语句是位操作i&(-i)，读者在稿纸上算一算就可以知道：

i -= i&(-i)的功能是令i的最低的非0位变为0；

i += i&(-i)的功能是令i的最低的非0位变为0，并往更高一位进一。

理解树状数组的行为，需要构造两个集合：

Define lowbit(i) = i&(-i);

up(a) = {a, a1, a2, ...}, ai = a(i-1) + lowbit(a(i-1));

down(a) = {a, a1, a2, ..., 0}, ai = a(i-1) - lowbit(a(i-1));

可以证明，对于任何a <= b的正整数对(a,b)，up(a)和down(b)的交集都有且仅有一个元素。对这个定理进行含糊的说明是很容易的，a == b的情况不必考虑，a < b时，总有一个最大的i，使得b的第i位大于a的第i位（也就是b的第i位是1，而a的第i位是0）,那么对b产生down(b)，对a产生up(a)，它们的唯一交集就是(1<<i)。注意这里讨论的第i位的i是从0开始索引的。读者可以在稿纸上找若干数对进行实验来加深印象。

有了上述定理，我们就不难意会insert函数和query函数的作用了。

#1. 机器浮点数的秘密，"巧夺天工"的完美实例，基于标准浮点数的快速开平方倒数算法

这是一个公开的秘密，这是一个所有程序员得以欣赏的智慧之美。她在许多程序员的心目中高居“最美代码”的第一位，所有溢美之词都无法表达他们所感受到的震撼。

一定会有许多人想在这里贴这段代码，少年，来我这里，我帮你揭开她神秘的面纱。

公式太多，贴图讲解。

Vote Me Up If You Like My Answer ^_^ 显示全部