June 3, 2024
时间戳：dfn[u]表示节点u深度优先遍历的序号。追溯点：low[u]表示节点u及其后代所能追溯到的最早（最先被发现）祖先点v的 dfn[v]值，即 \[\begin{diplaymath*} \text{low}[u] = \min_{(u,s),(u,w) \in E}\{\text{dfn}[u], \text{low}[s], \text{dfn}[w]\} \end{displaymath*} \]
其中s是u的儿子，(u, w)是反向边B.
low[u]计算步骤： \[\begin{displaymath*} \text{low}[u] = \begin{cases} \text{dfn}[u] \\ \min\{\text{low}[u], \text{dfn}[w]\} \\ \min\{\text{low}[u],\text{low}[s]\} \end{cases} \end{displaymath*}\]
《算法训练营入门篇》 陈小玉
June 3, 2024
图的连通性 时间戳和追溯点 无向图桥的判定法则 无向图割点的判定法则
负环(Negative-weight Cycle)与最短路径 Shortest path is cycle-free Relaxation(松驰操作)
June 2, 2024
F[i, j]表示 i 的 2^j 辈祖先，即 i 节点向根节点走 2^j 步到达的节点。可以分两个步骤：
递推公式：
F[i,j] = F[F[i,j-1], j-1], i=1,2,...,n, j=0,1,2,...,k, 2^k<=n, k=log2(n)
void st_create() {
for (int j = 1; j <= k; j++)
for (int i = 1; i <= n; i++)
F[i][j] = F[F[i][j - 1]][j - 1]
}
int lca_st_query(int x, int y) {
if (d(x) > d(y)) { //保证x的深度小于或等于y的深度
swap(x, y);
}
for (int i = k; i >= 0; i--)
if (d(F[y][i]) >= d(x))
y = F[y][i];
if (x == y)
return x;
for (int i = k; i >= 0; i--)
if (F[x][i] != F[y][i])
x = F[x][i], y = F[y][i];
return F[x][0];
}
《算法训练营进阶篇》 陈小玉
...
June 2, 2024
u 和 v 的公共祖先指一个节点既是 u 的祖先，又是 v 的祖先。u 和 v 的最近公共祖先指距离 u 和 v 最近的公共祖先。若 v 是 u 的祖先，则 u 和 v 的最近公共祖先是 v。
树上任意两点之间的距离(用 LCA 求解):
dist[u]+dist[v]-2×dist[lca]。
从 u 向上一直到根节点，标记所有经过的节点；若 v 已被标记，则 v 节点为 LCA(u, v)；否则 v 也向上走，第 1 次遇到已标记的节点时，该节点为 LCA(u, v)。
将 u、v 中较深的节点向上走到和深度较浅的节点同一深度，然后两个点一起向上走，直到走到同一个节点，该节点就是 u、v 的最近公共祖先，记作 LCA(u,v)。若较深的节点 u 到达 v 的同一深度时，那个节点正好是 v，则 v 节点为 LCA(u, v)。
《算法训练营进阶篇》 陈小玉
...
June 1, 2024
May 29, 2024
CREATE RESTORE POINT restore_point_name GUARANTEE FLASHBACK DATABASE;
使用GUARANTEE FLASHBACK DATABASE选项可以确保即使发生介质故障，也可以恢复到这个Restore Point。
select name, scn from v$restore_point;
SHUTDOWN IMMEDIATE;
STARTUP MOUNT;
FLASHBACK DATABASE TO RESTORE POINT restore_point_name;
ALTER DATABASE OPEN RESETLOGS;
RESETLOGS选项用于重置联机重做日志的序列号。
删除 Restore Point
DROP RESTORE POINT restore_point_name;
Flashback技术的局限性包括：
May 29, 2024
Flashback Database 整个架构包括:
一旦数据库启用了Flashback Database， 则RVWR进程会启动，该进程会向Flash Recovery Area中写入Flashback Database Log，这些日志包括的是数据块的"前镜像(before image)"， 这也是Flashback Database 技术不完全恢复块的原因。
SELECT name,flashback_on FROM V$DATABASE;
alter system set db_recovery_file_dest='C:/oracle/product/10.2.0/flash_recovery_area' scope=both;
alter system set db_recovery_file_dest_size = 10G scope=both;
10G的容量偏少，如果这个空间用完，数据库会无法访问，在该值改好前，也无法关闭数据库。
alter system set db_flashback_retention_target = 1440 scope=both;
STARTUP MOUNT;
ALTER DATABASE FLASHBACK ON;
对Flashback log空间情况进行更细粒度的记录和估计。这个视图以小时为单位记录数据库的活动量， Flashback_Data 代表Flashback log产生数量， DB_Data代表数据改变数量， Redo_Data代表日志数量，通过这3个数量可以反映出数据的活动特点，更准确的预计Flash Recovery Area的空间需求。
...
May 29, 2024
May 29, 2024