正文

本次问题主要集中在HiHo一下第16~21周，从Tarjan的Sparse-Table（ST）算法开始到线段树的使用主要讲述RMQ问题的解决方案以及离散化思想。RMQ问题在《算法竞赛入门经典——训练指南》一书中第三章也有专门讨论，并包含了这里不会讨论的树状数组。

HiHo一下第16周

与前面的一样，题目不再详述。解决这个问题使用了Tarjan的Sparse-Table方法，并且在题目的提示中已经讲解了，但是并没有给出图示，只给出了递推关系式，这里补充给出题目给出的case的解决过程来具体说明ST方法的工作原理。

首先需要明确的是ST方法实际上依旧是分治法的一种，并且需要一个表来保存计算结果以备查询（看起来与动态规划很像哈）。

来看看使用ST方法对已知case的解决过程吧：

先上主要工作，也就是构建Table的过程图：

RMQ_ST

图中的第i行第j列的数据记录以j开始，长度为2^i的区间内的最小值。很显然，我们的第0行就是原数据了。

第1行则是两个元素中的最小值，注意这个结果可以保存下来用来计算第2行的数据。

第2行则是四个元素中的最小值，同样可以用来计算第3行的数据。

第三行则是八个元素中的最小值。

由于case中的数据量为10，所以我们没有第4行了（注意我们是从0开始计数的，HiHo中的数据则是从1开始计数的）。

计算每一行的最大耗费为O(N)，总共需要计算log(N)行，因此ST算法总的时间复杂度上界为O(N*logN)。

既然已经计算出了查询表，那么接下来就应该使用个这表来处理查询了，处理查询的思想是这样的：

假定想知道从下标为1的元素开始，长度为7的区间内数据的最小值，那么我们可以将这个区间表示为这样的连个区间的并：

下标为1的元素开始，长度为4的区间；
下标为4的元素开始，长度为4的区间；

如图示：

Query1

由于区间长度为4 = 2^2，我们去找第2行中下表为1和4的数据：1556和981，两者的最小值981就是想要的结果。

再来一个例子：

假定想知道从下标为1的元素开始，长度为9的区间内数据的最小值，那么我们可以将这个区间表示为这样的连个区间的并：

下标为1的元素开始，长度为8的区间；
下标为2的元素开始，长度为8的区间；

如图示：

Query2

由于区间长度为8 = 2^3，我们去找第3行中下表为1和2的数据：981和981，两者的最小值981就是想要的结果。

case中的查询按照上面的思想就可以求解了，很显然经过预处理之后，查询操作的时间复杂度是O(1)。

接下来给出我的TLE代码……

真是够了，跟《训练指南》中的代码比较过，除了内循环那部分，别的没出入，依旧TLE，然而改成书中的格式之后反而更慢（sad face）。

#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;

#define MAX_N 1000000
#define MAX_WEIGHT 10001
#define MIN(a,b) ((a)>(b))?(b):(a)

int d[20][MAX_N];

void RMQ_ST_INIT()
{
    int n = 0;
    cin >> n;
	for (int p = 0; p < n; ++p)
    {
        cin >> d[0][p];
    }

    for(int j = 1; (1 << j) <= n; ++j)
    {
		int stride = 1 << (j - 1);
        for(int k = 0 ; k < n; ++k)
        {
            if(k + stride >= n)
            {
                break;
            }
            d[j][k] = MIN(d[j-1][k],d[j-1][ k + stride]);
        }
    }
}

int query(int lb, int rb)
{
	lb--;
	rb--;
    int len = rb - lb + 1;
    int k = 1;
    while((1 << k) <= len){
        ++k;
    }
	k--;
    return MIN(d[k][lb],d[k][lb + len - (1 << k)]);
}

int main(int argc, char** argv)
{
    RMQ_ST_INIT();
    int qn = 0;
    cin >> qn;
    while(qn > 0)
    {
        int l = 0, r = 0;
        cin >> l >> r;
        cout << query(l,r) << endl;
        --qn;
    }
}

HiHO一下第17周

前面讨论了RMQ问题的ST算法，这次就是它在LCA问题上的具体应用了，其中的一个关键思想就是：将树转化为数组。

具体方法是这样的：我们知道DFS在工作的时候将会进入一个节点一次，退出一个节点一次（实际上就是该节点的Environment入栈和出栈啦），在这个过程中我们可以得到节点的深度信息，那么我们可以根据DFS的路径将每次遇到的深度信息放到一个数组中：

void dfs(Node* n, vector<int>& v)
{
  foreach( node in n->children)
  {
    v.push_back(n->depth);
    dfs(node,v);
    v.push_back(n->depth);
  }
}

于是对于树：

tree

上图说明了DFS的路径。

有下面的数组：

DFS路径：
[A, B, D, D, B, E, I, I, E, B, A, C, F, J, J, F, C, G, G, C, H, H, C, A]
得到的对应数组：
[0, 1, 2, 2, 1, 2, 3, 3, 2, 1, 0, 1, 2, 3, 3, 2, 1, 2, 2, 1, 2, 2, 1, 0]

回顾LCA问题，实际上就是求两个节点在树中深度最低的那个公共祖先，结社我们要求D（深度2）和I（深度3）的LCA，已知结果为B，的对应深度为1。

记下D和I 最后一次 出现的位置下标：3和7，在这段区间中的最小值为1对于节点为B，正是所求的结果。
d
同理，对于节点I和J的LCA，下标7和14之间的区间内，最小值为0，对应节点为A，同样为所求结果。

再有，对于节点C和J的LCA，下标22和14之间的区间内，最小值为1，对应节点为C，同样为所求结果。

事实上，上面的DFS路径其实是将树的无向边变为双向边得到的。

线段树

很显然，ST算法在原数组中的数据不会发生改动的时候工作的很好，而且代码也不难写，然而当原数组中的数据发生改变的时候，即便是只改变一个数据，就会导致表中数据大量的更新（看一下上面构建表过程图中的关系表示就知道了），这是不可接受的。

本想用《算法导论》上面的线段树例子，不过对比之后感觉不太合适进行应用方面的说明。还是按照《训练指南》上的说法来吧。

事实上，线段树跟前面图形方面的文中的Quad Tree很像的：子树的并集“覆盖”（之所以用引号是因为多少还是不同的，不过这种类比可以更好的理解线段树，或者反之理解Quad Tree）了父节点所代表的空间；这种类似甚至包含了对于树的查询过程：满足要求的节点直接得到结果，而完全不满足要求的则拒绝向下求解，部分满足要求的则继续向下细分。

直接借用HiHo上面的图来说明这一点：

线段树

一图胜千言，说白了就是Quad Tree的一维形式，然后标准的Quad Tree是二维的，三位的则是Oct Tree。

下面我们想要查询区间[3, 9]:

橘黄色的节点就是我们想要询问的节点了，这里的每个节点都保存着与该节点相关的区间的“目标数据”比如：最大值，最小值，和等等。查询最坏情况也只对两个边界来一个深度查询，因此也是O(logN)的耗费。

回想一下我们讨论的Quad/Oct Tree的工作方式，是不是几乎一样的？将空间中的物体集合换成其他信息了而已，思路都是一样的。

既然知道了查询，那么修改怎么办呢？区间修改是一个down-top的过程，我们对每个节点维护一个指向父节点的指针，自下而上修改相关区间的“目标数据”就可以了，非相关区间很明显是不受影响的，于是修改的时间耗费就成了树的高度，线段树很明显是一个二叉树，那么修改操作的时间耗费就是O(logN)。

关于修改，还有一个 比较重要 的方法就是“懒惰标识”，这个思想跟“懒惰求值”是一样的，也就是不到万不得已不去修改，只做一个标记说明此处在下一次“问询”的时候需要重新计算。这种情况一般多见于对于未知问询的保守策略，不问的东西永远不会去求解，从而能提高效率（不需要每次修改把所有的点都计算一遍，只计算参与问询的点）。

线段树基本上介绍完毕了，接下来是与线段树相关的一个思想，在解决“区间相关”问题上非常有帮助（再比如2/3D空间的包含、重叠之类的问题）。