在本文中,我们主要介绍树线段的内容,自我感觉有个不错的建议和大家分享下

    标题链接:    

    标题粗心:   给出初始化的区间值，m次查询

                  每次查询区间[a，b]的最大值－最小值

    解题思路:   线段树    更新: 无更新    查询:区间查询

                      建立线段树的时候，每一个结点存储左右子树的最大值和最小值

                      查询时直接访问区间最大值和最小值，不需要查找到最低

                      查询时间复杂度O(logN)

    代码:

    

    每日一道理

风，那么轻柔，带动着小树、小草一起翩翩起舞，当一阵清风飘来，如同母亲的手轻轻抚摸自己的脸庞，我喜欢那种感觉，带有丝丝凉意，让人心旷神怡。享受生活，不一定要有山珍海味、菱罗绸缎为伴，大自然便是上帝所赐予人类最为珍贵的。

#include 
    
     #include 
     
      #include 
      
       #define MAXN 70000#define INF 0x3f3f3f3f#define MAX(a,b) a>b?a:b#define MIN(a,b) a
       
        >1#define L(a) a<<1#define R(a) (a<<1)+1typedef struct snode{    int left,right;    int max,min;}Node;Node Tree[MAXN<<1];int num[MAXN],minx,maxx;void Build(int t,int l,int r)    //以t为根结点建立左子树为l，右子树为r的线段树{    int mid;    Tree[t].left=l,Tree[t].right=r;    if(Tree[t].left==Tree[t].right)    {        Tree[t].max=Tree[t].min=num[l];        return ;    }    mid=MID(Tree[t].left,Tree[t].right);    Build(L(t),l,mid);    Build(R(t),mid+1,r);    Tree[t].max=MAX(Tree[L(t)].max,Tree[R(t)].max);  //更新结点的最大值=MAX(左子树，右子树)    Tree[t].min=MIN(Tree[L(t)].min,Tree[R(t)].min);  //更新结点的最小时=MIN(左子树，右子树)}void Query(int t,int l,int r)    //查询结点为t，左子树为l，右子树为r的最大值和最小值{    int mid;    if(Tree[t].left==l&&Tree[t].right==r)    {        if(maxx
        
         Tree[t].min)            minx=Tree[t].min;        return ;    }    mid=MID(Tree[t].left,Tree[t].right);    if(l>mid)    {        Query(R(t),l,r);    }    else if(r<=mid)    {        Query(L(t),l,r);    }    else    {        Query(L(t),l,mid);        Query(R(t),mid+1,r);    }}int main(){    int n,m,a,b,i;    memset(Tree,0,sizeof(Tree));    scanf("%d%d",&n,&m);    for(i=1;i<=n;i++)        scanf("%d",&num[i]);    Build(1,1,n);            //建立以1为根结点区间为[1,n]的线段树    while(m--)    {        scanf("%d%d",&a,&b);        maxx=0;minx=INF;     //初始化最大值为0,最小值为INF        Query(1,a,b);        //查询区间[a,b]的最大值和最小值        printf("%d\n",maxx-minx);    }    return 0;}
        
       
      
     
    

    注:原创文章，转载请注明出处

    

    

文章结束给大家分享下程序员的一些笑话语录： 程序语言综述

CLIPPER 程序员不去真的猎捕大象，他们只是购买大象部分的库然后花几年的时间试图综合它们。

DBASE 程序员只在夜间猎捕大象，因为那时没人会注意到他们还在使用石弓。

FOXPRO 程序员开始使用更新更好的步枪，这使他们花掉比实际狩猎更多的时间学习新的射击技术。

C 程序员拒绝直接购买步枪，宁可带着钢管和一个移动式机器车间到非洲，意欲从零开始造一枝完美的步枪。

PARADOX 程序员去非洲时带着好莱坞关于猎捕大象的电影剧本，他们认为照剧本行事就会逮到一头大象。

ACCESS 程序员在没有任何猎象经验的经验下就出发了，他们穿着华丽的猎装、带着全部装备，用漂亮的望远镜找到了大象，然后发觉忘了带扳机。

RBASE 程序员比大象还要稀少，事实上，如果一头大象看到了一个RBASE程序员，对他是个幸运日。

VISUAL ACCESS 程序员装上子弹、举起步枪、瞄准大象，这使大象感到可笑，究竟谁逃跑。他们无法抓住大象，因为由于他们对多重控制的偏爱，他们的吉普车有太多的方向盘因而无法驾驶。

ADA、APL和FORTRAN 程序员与圣诞老人和仙女一样是虚构的。

COBOL 程序员对和自己一样濒临灭绝的大象寄予了深切的同情。

--------------------------------- 原创文章 By

树和线段

---------------------------------