介绍:

差分数组用来记录一个数组中相邻数据的差,比如给出一个数组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)。

学习历程 > 算法 > 树状数组
树状数组

Tarjan算法

Tarjan算法中几个关键点:

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

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

  • stack数组:模拟栈

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

算法