树状数组(Binary Indexed Tree)是又一种静态的树结构。它的首要用途是用于维护前缀和，也即：一数组a[1..n]，随时会改变其中某a[i]，还会询问s[i]=a[1]+a[2]+…+a[i]，树状数组可完美解决这一问题。

定义数组c[0..n]，其中c[i]=a[i-2^k+1]+a[i-a^k+2]+…+a[i]，其中k为i在二进制下末尾0的个数。当我们改变一个a[i]时，会有很多c[i]随之改变；若需查询某个s[i]，需要累加多个c[i]。好在确定需要改变或累加的元素都可以用比较简便的方法得出，这方法的核心就是lowbit值。

定义lowbit(x)=x&(x^(x-1))，它相当于将最右边的1左边的东西全部去掉。若需改变a[i]，则c[i]、c[i+lowbit(i)]、c[i+lowbit(i)+lowbit(i+lowbit(i)]……就是需要改变的c数组中的元素。若需查询s[i]，则c[i]、c[i-lowbit(i)]、c[i-lowbit(i)-lowbit(i-lowbit(i))]……就是需要累加的c数组中的元素。这看上去有些玄妙，我觉得其实也可以不用透彻理解。

一维的树状数组的每个操作的复杂度都是O(logn)的，非常高效。它可以扩充为n维，这样每个操作的复杂度就变成了O((logn)^n)，在n不大的时候仍然完全可以接受。扩充的方法就是将原来改变和查询的函数中的一个循环改成嵌套的n个循环在n维的c数组中操作。

要注意树状树组能处理的是下标为1..n的数组，绝对不能出现下标为0的情况。因为lowbit(0)=0，这样会陷入死循环。对于我这个从来都用C语言思考的家伙来说，这一点格外需要注意。

似乎树状数组也可以用来解决一些与前缀和关联不大的问题，例如NOI2004的cashier，但我还不太会（那题我只会用平衡树或线段树或虚二叉树解）。

示例程序：ural1470.cpp（三维的树状数组）

收缩有向图中的强连通分量大约是图论的线性算法中最具技巧性一种了。我们的首要目的是对于每个顶点设定一个Belong值，也就是它从属于哪个顶点所代表的强连通分量，至于重新建立图的边，不过是将所有边扫描一遍看是否在新图中出现而已，比较容易。

下面是利用一遍DFS求强连通分量的方法：对于每个顶点，设立Num、Low、Used、Alive四个属性，一个Stack保存当前正在被遍历的顶点；每访问一个顶点，将它的Num和Low设立为当前时间戳，Used、Alive设为True，并将顶点入栈，对于它的每条边，若边的终点未Used，则访问，而后用终点的Low值更新它的Low值，对于每个Used且Alive的终点，用它的Num值更新当前值；访问完毕当前顶点后，若Low与Num相等，说明找到了一个强连通分量，它包括栈中所有在当前顶点上方的顶点，将它们出栈并记下Belong值，出栈的顶点的Alive要置为false。

注意这里的Low值与求割顶和桥时的Low值的定义不太相同，它是与当前顶点双连通的最低顶点，所以才要用Alive来标记是否能到达当前顶点。

示例程序：cow.cpp
（HAOI 2006 cow）

异或方程组就是形如这个样子的方程组：

M[0][0]x[0]^M[0][1]x[1]^…^M[0][N-1]x[N-1]=B[0]
M[1][0]x[0]^M[1][1]x[1]^…^M[1][N-1]x[N-1]=B[1]
…
M[N-1][0]x[0]^M[N-1][1]x[1]^…^M[N-1][N-1]x[N-1]=B[N-1]

其中“^”表示异或(XOR, exclusive or)，M[i][j]表示第i个式子中x[j]的系数，是1或者0。B[i]是第i个方程右端的常数，是1或者0。

解这种方程可以套用高斯消元法，只须将原来的加减操作替换成异或操作就可以了，两个方程的左边异或之后，它们的公共项就没有了。

具体的操作方法是这样的：对于k=0..N-1，找到一个M[i][k]不为0的行i，把它与第k行交换，用第k行去异或下面所有M[i][j]不为0的行i，消去它们的第k个系数，这样就将原矩阵化成了上三角矩阵；最后一行只有一个未知数，这个未知数就已经求出来了，用它跟上面所有含有这个未知数的方程异或，就小觑了所有的着个未知数，此时倒数第二行也只有一个未知数，它就被求出来了，用这样的方法可以自下而上求出所有未知数。

示例程序：t3.cpp
(HAOI 2005  t3)

一组平面上的点，求一个包含所有点的最小的凸多边形，这就是凸包问题了。这可以形象地想成这样：在地上放置一些不可移动的木桩，用一根绳子把他们尽量紧地圈起来，这就是凸包了。

求凸包有很多方法，不过最适合OI的估计还是Graham’s Scan这个方法了。它的大致方法是这样的： 首先，找到所有点中最左边的（y坐标最小的），如果y坐标相同，找x坐标最小的；以这个点为基准求所有点的极角（atan2(y-y0,x-x0)），并按照极角对这些点排序，前述基准点在最前面，设这些点为P[0]..P[n-1]；建立一个栈，初始时P[0]、P[1]、P[2]进栈，对于P[3..n-1]的每个点，若栈顶的两个点与它不构成“向左转”的关系，则将栈顶的点出栈，直至没有点需要出栈以后将当前点进栈；所有点处理完之后栈中保存的点就是凸包了。

如何判断A、B、C构成的关系不是向左转呢？如果b-a与c-a的叉乘小于0就不是。a与b的叉乘就是a.x*b.y-a.y*b.x。

上面的这个Graham的实现比我原来按照USACO里的课文写得简单多了，主要是它通过简单的预处理保证了P[0]、P[1]以及P[n-1]肯定是凸包里的点，这样就可以避免在凸包“绕回来”的时候繁杂的处理。

示例程序：fc.cpp
(USACO Training: fc)

矩阵乘法的定义很简单，比如说S=X*Y，那么就有S[i][j]=sum(X[i][k]*Y[k][j])。

利用矩阵乘法，可以解决一类DP问题。这一类问题的特点是：状态的某一维特别巨大，但是沿着这一维的决策过程是完全重复或者循环的。

比如说这个问题：一个有向图，沿着每条边走过去的时间都为1，问时刻0在在S点，时刻t在T点共有多少种不同的路径（不一定是简单路径）。

很容易想到的思路是DP，设v[i][j]表示时间i时在v顶点的路径数，边界条件是v[0][S]=1，只需求解v[t][T]即可。由于v[i]之与v[i-1]有关，可以很方便地将状态的储存空间压缩从O(nt)为O(n)，但是如果t特别大（比如说1e9）O(n^2*t)的时间还是要TLE的（最一般的状态转移是需要n^2时间的）。这时就可以使用矩阵乘法来优化。

将v[i]这个一维数组想成一个1*n的矩阵，我们会发现v[i+1]=v[i]*M，其中M是有向图的n x n的邻接矩阵。为什么是这样不大好单纯用语言解释，如果你深刻理解了矩阵乘法的意义，再考虑一下前面的问题的状态转移的过程就会明白。所以说我们要求解的v[t]其实就是v[0]*M*M*M…（t个M）。根据矩阵乘法的结合律，它也就是v[0]*M^t。而M^t这个东西是可以利用类似于快速幂取模的方法在O(log t)的时间内计算出来的（把矩阵乘法当作元运算）。这样我们就把上述时间复杂度变成了O(log t * n^3)，在n不太大，而t可能非常大时，这是非常好使的优化。

更多时候问题没有这么简单，比如说图的顶点可能按照某周期禁止到达啊（ZJOI 2005 day1 swamp），也就是说图的邻接矩阵会随着t而变化。但只要它是周期性的，还是可以直接使用矩阵来优化。只是实现时要注意矩阵乘法是不满足交换律的。

示例程序：swamp.cpp
(ZJOI 2005 day1 swamp)

并查集，就是Union-Find Set，也称不相交集合 (Disjoint Set)。这在数据结构中本是很简单的一种东西。当然，我是指算法的实现简单，而非其理论分析简单。但我今天还是要扯一下这个，因为我突然发现我这几天写的并查集都是错的，今天做题时才发现。所以还是把这个很简单的数据结构总结一下。

正如它的名字揭示的，并查集的基本操作有两个：Union和Find。其中Find(x)返回元素x所在的集合的编号，Union(i,j)将i与j所在的集合合并，也就是说在此之后对它们中的每一个调用Find的返回值必须是一样的。

实现时采用父亲表示法的树结构，保证所有在一个集合里的元素都在一棵树内，集合的代表元素就是根。初始时所有节点的父节点都是自身，查找时只须沿着向上的路径查找即可；如果要将两棵树合并只须将其中一棵的根的父节点设为另一棵树的根即可。最主要的优化是所谓路径压缩。简言之，就是在Find的实现时并不简单的return find(U[x]); 而是 return U[x]=find(U[x]); 这样就将当前节点到根的路径上的所有节点的父亲都设为了根，将原本可能比较长的路径“压缩”了。当然这是递归的实现，非递归的话需要沿路径走两次，第一次找到根，第二次再改变。

union操作更简单，只是U[find(x)]=find(y);一句而已。我前两天写Tarjan算法时把这一句错写成U[x]=find(y)，竟然也AC了……汗……不过今天做另一道需要并查集的题目就没那么幸运了。

路径压缩的并查集n个操作的序列的均摊复杂度为O(nα(n))，其中 α是阿柯曼函数的一个反函数，增长极慢，在可以想象的n的范围内不超过5，故可视为常数。

并查集的一般用途就是用来维护某种具有自反、对称、传递性质的关系的等价类。

实现并查集只需要一个数组和两个分别是两行和一行的函数，故不再发示例代码了。

图的割顶即删掉之后图就不连通的顶点，桥即删掉之后图就不连通的边。

求图的割顶与桥都需要对图的DFS进行简单扩充，即在DFS过程中求出每个顶点的Low值，Low的定义是：

Low[v]=min{
　　Num[v],
　　Num[w], ( link[v][w] && Num[w] < Num[v] && Par[v]!=w ， 后向边)
　　Low[w], ( link[v][w] && Num[w] > Num[v] ，树边)
}

其中Num[v]表示每次DFS到v顶点时标记的时间戳，Par[v]是DFS树中v的父节点。

(v,w)是桥当且仅当Num[v]<Low[w]。

v是割顶当且仅当v不是根且Num[v]<=Low[w]或v是根且DFS树中v有不止一个的子节点。

（以上Par[w]==v）

示例程序（求图的桥）：
zju2588.cpp

LCA 问题，即 Least Common Ancestors（最近公共祖先）的意思是：给定一有根树，求其两个节点最近的公共祖先；节点的祖先即从节点至根的路径上的节点的集合。

LCA 问题可以转化为 RMQ 问题求解，方法是：从根开始对树进行一次深度优先遍历，每次沿一条边到达另一节点时记录下节点的深度，这样就得到一个序列；对于问题中的两个节点，以它们的首次出现为两端的子序列中的最小值就是最近公共祖先。规模为n的 LCA 经过转化变成了规模为2n-1的 RMQ，渐进复杂度不变，然后就可以使用 RMQ 的各种方法来解答。

但是即便LCA转换成了RMQ，比较好写的ST之类方法还是O(nlogn)的，在竞赛中更好用的似乎是 Tarjan 的 O(nα(n)) 的离线算法。算法用到了并查集，在对树的一次深度优先遍历后完成，方法大致是这样的：每次访问到一个节点，对它建立一个并查集，设定它的祖先为自己；访问它的每个子节点，并在每次访问结束后设儿子的并查集的代表顶点的祖先为自己；将自己标记为黑色，对于每个与它有关的问题，若另一节点也为黑色，则这个问题的答案就是另一节点所在的并查集的代表顶点的祖先。

至于RMQ转换成LCA其实也简单，要将原数组转换成听上去有点神秘的“Cartesian Tree”（笛卡尔树）。所谓Cartesian Tree，是一个二叉树，每个节点的值大于子节点（堆序），节点的中序遍历满足原数组顺序（排序二叉树）。看到这儿我明白了——这不就一Treap么……当然，我们是不用挨个插入 Treap 的O(nlogn) 算法的。是采用自数组从左向右扫描，每次的新数沿着旧树的右路径上升至不能上升。每个节点进入和退出右路径最多一次，所以是均摊 O(n) 的。呵呵，说起来简单，我还没实现过这个呢，什么时候真闲得慌了可以写写玩玩。

LCA 的 Tarjan 算法示例程序：
ural1471.cpp

KMP是字符串匹配的高效算法。

它的基本思路是，对于模式串建立一个“失败转移表”(fail transform table)。设模式串为B，原串为A，也就是说，当A[i]!=B[j]的时候，A[i]可能与B[P[j]]匹配。

P可以在事先对B进行一次“自匹配”以计算出来。我们看到的KMP总是两段很相似的代码。

今天写KMP的时候开始老写错，最后没办法了上Google Code Search搜索了一下KMP，参考或者说抄袭了一下排在第一的libg++里面的代码……这大约是有点悖德的事情，不过显然我也顾不得那么多了现在。

程序：ural1423.cpp

RMQ问题 (Range Minimum/Maximum Query)，首先给出一个序列，然后不断询问某个区间内的最大值和最小值。显然，我们在回答所有询问之前，需要根据序列进行一定的预处理。

一种算法是采用线段树，即在线段树的每个节点保存该区间的最大值与最小值，O(n)的预处理时间（需要自底向上构建），可以O(logn)地回答每个问题。

另一种算法就是神奇的ST算法（Sparse Table） ，以求最大值为例，设v[n][f]表示[n,n+2^f)这个区间内的最大值，那么在询问到[a,b)区间的最大值时答案就是max(v[a][f],v[b-2^f][f])，其中f是满足2^f<=b-a的最大的f。至于那张稀疏表，可以用递推的方法在O(nlogn)（也就是表的元素数）的时间内构建。也就是说v[n][f]=max(v[n][f-1],v[n+2^(f-1)][f])。

另外，RMQ问题与LCA（Least Common Ancestors，最近公共祖先）问题可以互相转化。LCA问题有一个经典的离线算法Tarjan算法，稍后我将会介绍。

程序：
lineupg.it.cpp（线段树，因询问较多，无法AC本题）
lineupg.st.cpp（ST算法）
(USACO Jan07 Gold lineupg)