Nov 8

RMQ再学习笔记 不指定

felix021 @ 2010-11-8 23:54 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(12979) | 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]);
        }
    }
}




欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
cylcc006
2013-4-9 14:55
你好,下面代码有点小错误// 求区间最小值,而m<arr[k]求得是最大值if (m < 0 || m < arr[k])    m = arr[k];
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]