首页 > 数据结构 > 树形结构 > 区间最值查询-线段树
2016
12-03

区间最值查询-线段树

在前面的文章中介绍了线段树的简单应用:求给定区间的和。线段树还可以用于另一个经典的问题:范围最值查询(Range Minimum Query)。是针对数据集的一种条件查询。若给定一个数组 A[1,n],范围最值查询指定一个范围条件 i 到 j,要求取出 A[i,j]中最大/小的元素。

若A=[3,5,2,5,4,3,1,6,3],条件为 [3,8] 的范围最值查询返回 1,它是子数组 A[3,8] = [2,5,4,3,1,6]中最小的元素。

通常情况下,数组A是静态的,即元素不会变化,例如插入、删除和修改等,而所有的查询是以离线的方式给出的,即预先并不知道所有查询的参数。

简单的解法是 使用循环遍历,找出最值,时间复杂度为O(n)。

另一个做法是,先做预处理。创建一个二维数组,存储下所有可能得结果, arr[i][j] 存储 区间 [i,j]内的最值,以后每次查询都值需要O(1)的时间。但是预处理需要O(n^2)的时间,空间复杂度也为O(n^2)。

使用线段树可以作为一个折中的选择,预处理的时间为O(N),查询的时间为O(log N)。需要的空间为O(n)。

线段树的表示方法:

1. 叶节点即为给定数组中的所有元素
2. 每个内部节点代表该节点的子树下面的最小节点。

RangeMinimumQuery

 

C++代码实现如下:

#include 
#include 
#include 

int minVal(int x, int y) { return (x < y)? x: y; }  
int getMid(int s, int e) {  return s + (e -s)/2;  }   

/*   递归的完成查询操作       st    --> 指向线段树的指针
    index --> 线段树的当前节点,初始化为0,代表整个线段树
    ss & se  --> st[index]所代表的线段树区间
    qs & qe  --> 查询区间的起始位置 */
int RMQUtil(int *st, int ss, int se, int qs, int qe, int index)
{
    // 如果包含在线段树的区间内
    if (qs <= ss && qe >= se)
        return st[index];

    if (se < qs || ss > qe)
        return INT_MAX;

    // 如果有部分区间重叠
    int mid = getMid(ss, se);
    return minVal(RMQUtil(st, ss, mid, qs, qe, 2*index+1),
                  RMQUtil(st, mid+1, se, qs, qe, 2*index+2));
}

// Range Minimum Query
//主要调用RMQUtil 完成查询工作
int RMQ(int *st, int n, int qs, int qe)
{
    // 检查输入
    if (qs < 0 || qe > n-1 || qs > qe)
    {
        printf("Invalid Input");
        return -1;
    }

    return RMQUtil(st, 0, n-1, qs, qe, 0);
}

// 递归的方法创建array[ss..se]对应的线段树
// si 是当前节点的下标
int constructSTUtil(int arr[], int ss, int se, int *st, int si)
{
    if (ss == se)
    {
        st[si] = arr[ss];
        return arr[ss];
    }
    int mid = getMid(ss, se);
    st[si] =  minVal(constructSTUtil(arr, ss, mid, st, si*2+1),
                     constructSTUtil(arr, mid+1, se, st, si*2+2));
    return st[si];
}

/* 分配内存,调用constructSTUtil完成真正的工作. */
int *constructST(int arr[], int n)
{
    // 分配内存
    int x = (int)(ceil(log2(n))); //线段树的高度
    int max_size = 2*(int)pow(2, x) - 1; //线段树元素的个数
    int *st = new int[max_size];

    constructSTUtil(arr, 0, n-1, st, 0);
    return st;
}

int main()
{
    int arr[] = {1, 3, 2, 7, 9, 11};
    int n = sizeof(arr)/sizeof(arr[0]);

    // 构造线段树
    int *st = constructST(arr, n);

    int qs = 1;  // 查询的起始位置
    int qe = 5;  // 查询的结束位置

    printf("Minimum of values in range [%d, %d] is = %d\n",
                           qs, qe, RMQ(st, n, qs, qe));

    return 0;
}

输出:

Minimum of values in range [1, 5] is = 2

参考:http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  4. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  5. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  6. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。