RMQ再学习笔记

glibc的qsort源码阅读笔记

批处理照片时EXIF信息的保留

Nov 8

felix021 @ 2010-11-8 23:54 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(14588) | Via 本站原创

大 | 中 | 小

2年多以前看的算法，当时基本看懂了（实际上还是有问题的），今天再翻出来，感觉基本忘了，重新实现一遍，试着自己把推导过程也写写。非常赞的算法。

RMQ: Range Minimum Query, 区间最小值查询。已知数组在区间 [0, n) 有定义，给出 i, j (0 <= i < j <=n)，求 [i, j) 之间的最小值。

朴素算法非常简单，但是显然，每次查询是O(N)的，效率很低：

min = +INFINITE
FOR k = i TO j - 1
IF min > arr[k]
min = arr[k]
END IF
END FOR
RETURN min

由于经常遇到需要多次查询的情况，所以朴素算法不合意。一个比较好的改进是使用线段树/树状数组，首先通过O(NlogN)预处理，让每个分支节点保存了其所有叶子节点的最小值（由底向上递推)。这样每次查询的时候，就可以在O(logN)的时间内得到结果。具体代码稍繁琐，这里不写了。

最好的方法，是用叫做sparse_table的算法，其思路和线段树很像，区别是通过O(NlogN)的预处理，可以让查询的时间复杂度降低到O(1)。其具体思路为：

预处理：
1. 记F[s][p] = min{ arr[i] | s <= i < s + 2^p} = min(arr[s..(s + 2^p - 1)])。例如， F[1][2] = min{ arr[i] | 1<= i < 5} = min(arr[1..4])。
2. 由1，易推知，F[s][0] = min { arr[i] | s <= i < s + 1} = arr[s].
3. 通过由底向上递推的预处理得到所有满足（s + 2^p <= n, 即区间[s, s + 2^p) 包含于[0..n)区间内）的F[s][p] = min(F[s][p-1], F[s+2^(p-1)][p-1])。例如， F[2][3] = min(arr[2..9]) = min(min(arr[2..5]), min(arr[6..9])) = min(F[2][2], F[6][2]) = min(F[2][3-1], F[2 + 2^(3-1)][3-1])。

查询[i, j)：
1. 令 k = log2(j - i)取整，则 (j - 2^k) <= (i + 2^k)，即区间 [i, i + 2^k) 和 [j - 2^k, j) 必定覆盖 [i, j)。例如，区间[3, 8)，k = log2(8-3)取整 = 2，则 [3, 7), [4, 8) 覆盖 [3, 8)。
2. RMQ[i, j) = min(F[i][k], F[j - 2^k][k]).

----扩展---
LCA（树中任意两个节点的最近公共祖先）问题，是可以通过RMQ+DFS来完成的，详见LCA问题。ZOJ 1141是一道纯LCA问题。

具体实现和检验代码如下（做了一点改进，F[s][p]中存放的是[s, s + 2^p)中最小值在数组中的索引）：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define N 1000
#define LogN 10
int arr[N];
int f[N][LogN];

void sparse_table(int arr[], int n)
{
int i, j, k;
k = (int)(log(n + 0.2) / log(2.0));
//精度考虑，加上0.2。对于k<49成立。对于k>=49，有log2(2^k-1 + 0.2) == log2(2^k + 0.2)

for (i = 0; i < n; i++) f[i][0] = i;
for (j = 1; j <= k; j++)
{
for (i = 0; i + (1 << j) <= n; i++)
{
int a = f[i][j-1], b = f[i+(1<<(j-1))][j-1];
f[i][j] = arr[a] < arr[b] ? a : b;
}
}
}

int rmq_idx(int arr[], int i, int j)
{
int k = (int)(log(j - i + 0.2) / log(2.0));
int a = f[i][k], b = f[j-(1<<k)][k];
return arr[a] < arr[b] ? a : b;
}

int rmq(int arr[], int i, int j)
{
return arr[rmq_idx(arr, i, j)];
}

int main()
{
int i, j, k;
srand(time(0));
for (i = 0; i < N; i++) arr[N] = rand();

sparse_table(arr, N);

for (i = 0; i < N; i++)
{
for (j = i + 1; j < N; j++)
{
int m = -1;
for (k = i; k < j; k++)
{
if (m < 0 || m < arr[k]) m = arr[k];
}
if (m != rmq(arr, i, j))
{
printf("i = %d, j = %d: %d vs %d\n",
i, j, m, rmq(arr, i, j));
return 1;
}
}
}
printf("OK!\n");
return 0;
}

ZOJ 1141代码

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <stack>
using namespace std;

vector <int> v[20000], E;
int cnt[20000], R[20000], D[20000], f[20000][20];

//v是各个定点的子节点vector。E保存了DFS时的顺序。
//cnt存放最后要输出的答案，R是每个节点在E中最先出现的位置，D是每个节点的深度。
//f是sparse_table。

void dfs(int n, int depth = 1)
{
E.push_back(n);
R[n] = E.size() - 1; //进入此节点
D[n] = depth;
for (unsigned i = 0; i < v[n].size(); i++)
{
dfs(v[n][i], depth + 1); //进入子节点
E.push_back(n); //离开子节点
}
}

void sparse_table()
{
int i, j, k, n = E.size();
for (i = 0; i < n; i++) f[i][0] = i;
k = (int)(log(n + 0.2) / log(2.0));
for (j = 1; j <= k; j++)
{
for (i = 0; i + (1 << j) <= n; i++)
{
int a = f[i][j-1], b = f[i+(1<<(j-1))][j-1];
f[i][j] = D[E[a]] < D[E[b]] ? a : b; //注：这里比较的是深度，不是节点的编号大小。
}
}
}

int rmq_idx(int i, int j)
{
int k = (int)(log(j - i + 0.2) / log(2.0));
int a = f[i][k], b = f[j-(1<<k)][k];
return D[E[a]] < D[E[b]] ? a : b; //注：这里比较的是深度，不是节点的编号大小。
}

int rmq(int i, int j)
{
return E[rmq_idx(i, j)]; //这里返回的是深度最大的公共祖先的编号，就是LCA了。
}

int LCA(int a, int b)
{
int i = R[a], j = R[b]; //注意上下界-。- WA了两次囧
if (i < j)
return rmq(i, j + 1);
else
return rmq(j, i + 1);
}

int main()
{
int n, m, id, child, i, j, root;
while (scanf("%d", &n) == 1 && n > 0)
{
E.clear();
for (i = 0; i < n; i++)
{
cnt[i] = 0; //入度=0
D[i] = 0; //节点的深度
R[i] = -1; //第一次出现位置
}
for (i = 0; i < n; i++)
{
scanf("%d : ( %d )", &id, &m);
id--;
v[id].clear();
for (j = 0; j < m; j++)
{
scanf("%d", &child);
child--;
v[id].push_back(child);
cnt[child]++; //入度++
}
}

for (i = 0; i < n; i++) if (cnt[i] == 0) break;
root = i;

dfs(root);
sparse_table();

//unsigned j;
//for(j=0; j<E.size(); j++)printf("%2d ",E[j]);puts("");
//for(j=0; j<E.size(); j++)printf("%2d ",D[E[j]]);puts("");

scanf("%d", &m);
int a, b;
for (i = 0; i < n; i++) cnt[i] = 0;
for (i = 0; i < m; i++)
{
scanf(" ( %d , %d )", &a, &b);
a--, b--;
//printf("LCA(%d, %d) = %d\n", a, b, LCA(a, b));
cnt[LCA(a, b)]++;
}
for (i = 0; i < n; i++)
{
if (cnt[i] > 0)
printf("%d:%d\n", i + 1, cnt[i]);
}
}
}

欢迎扫码关注：