我在这里提供我见识到的三个精彩算法的解析，强烈地推荐给初学的算法爱好者，它们可能会令你眼界大开，同时坚定你在算法大道上勇往直前的信念。
#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，如果想一起交流的可以加这个群：941636044 ，有什么问题可以群里面交流，群里面也有许多方便学习C语言C++编程以及有关算法的资料可以给你利用。
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] += add
void 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<
有了上述定理，我们就不难意会insert函数和query函数的作用了。
#1. 机器浮点数的秘密，”巧夺天工”的完美实例，基于标准浮点数的快速开平方倒数算法
这是一个公开的秘密，这是一个所有程序员得以欣赏的智慧之美。她在许多程序员的心目中高居“最美代码”的第一位，所有溢美之词都无法表达他们所感受到的震撼。
一定会有许多人想在这里贴这段代码，少年，来我这里，我帮你揭开她神秘的面纱。
公式太多，贴图讲解。如果想一起交流的可以加这个群：941636044 ，有什么问题可以群里面交流，群里面也有许多方便学习C语言C++编程以及有关算法的资料可以给你利用。
网友评论