首页 > 代码库 > 区间最小值 线段树 （2015年 JXNU_ACS 算法组暑假第一次周赛）
区间最小值 线段树 （2015年 JXNU_ACS 算法组暑假第一次周赛）
区间最小值
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 12 Accepted Submission(s) : 5
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
给定一个数字序列，查询随意给定区间内数字的最小值。
Input
输入包括多组測试用例，每组測试用例的开头为一个整数n(1<=n<=100000)。代表数字序列的长度。
接下去一行给出n个数字，代表数字序列。
接下去一行给出n个数字，代表数字序列。
数字在int范围内。
下一行为一个整数t(1<=t<=10000)，代表查询的次数。
最后t行，每行给出一个查询。由两个整数表示l、r(1<=l<=r<=n)。
Output
对于每一个查询，输出区间[l,r]内的最小值。
Sample Input
5 3 2 1 4 3 3 1 3 2 4 4 5
Sample Output
1 1 3
Author
吴迎
Statistic | Submit | Back
线段树问题。感觉这是最美的数据结构~
非常基础的线段树问题。对于这不懂的还是多多百度呀。
#include <stdio.h>
#include <algorithm>
using namespace std;
int num[100005];
struct node
{
int left,right,val;//每一个节点有三个值，左区间，右区间，和最小值
}c[100005*4];
void build_tree(int l,int r,int root)//建树
{
c[root].left=l;
c[root].right=r;
if(l==r)//假设左区间等于右区间就赋值
{
c[root].val=num[l];
return ;
}
int mid=(l+r)/2;
build_tree(l,mid,root*2);
build_tree(mid+1,r,root*2+1);
c[root].val=min(c[root*2].val,c[root*2+1].val);//递归得到
}
void find_tree(int l,int r,int &min1,int root)//查找
{
if(c[root].left==l&&c[root].right==r)
{
min1=c[root].val;
return ;
}
int mid=(c[root].left+c[root].right)/2;
if(mid<l)//先找到所要寻找的区间在树上的区间范围
find_tree(l,r,min1,root*2+1);
else if(mid>=r)
find_tree(l,r,min1,root*2);
else//找到了所要找的区间
{
int min2;
find_tree(l,mid,min1,root*2);//左儿子一个最小值
find_tree(mid+1,r,min2,root*2+1);//右儿子一个最小值
min1=min(min1,min2);//选最小的
}
}
int main()
{
int n,k;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
build_tree(1,n,1);
scanf("%d",&k);
while(k--)
{
int a,b,min1;
scanf("%d %d",&a,&b);
find_tree(a,b,min1,1);
printf("%d\n",min1);
}
}
return 0;
}区间最小值 线段树 （2015年 JXNU_ACS 算法组暑假第一次周赛）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。