介绍：

差分数组用来记录一个数组中相邻数据的差，比如给出一个数组a，a[i]表示数组a的第i个元素，另外给出一个数组d表示差分数组那么d[i] = a[i] - a[i-1]，所以d[i]表示数组a中第i个元素与前一个元素的差值，那么差分数组的意义在哪呢？

简单题(easy)

Description

有一个 n个元素的数组，每个元素初始均为 0。有 m条指令，要么让其中一段连续序列数字反转—— 0变 1，1变 0（操作 1），要么询问某个元素的值（操作 2）。

引入：

树状数组所处理的问题（简单罗列）：

• 求出[a,b]之间的和
• 求出前k项的和
• 更新第k项的数据

Tarjan算法

Tarjan算法中几个关键点:

• dfn数组：dfn[u]表示结点u的深度优先次序

• low数组：low[u]表示以u为根节点的最近的子节点的次序

• stack数组：模拟栈

• instack数组：对属于同一个强连通分量的点进行染色