区间最小值 线段树 （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

Times New Roman | Verdana | Georgia

← →

Problem Description

给定一个数字序列，查询任意给定区间内数字的最小值。

Input

输入包含多组测试用例，每组测试用例的开头为一个整数n(1<=n<=100000)，代表数字序列的长度。 接下去一行给出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 #include 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=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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。