在写这篇文章之前，xxx已经写过了几篇关于改树线段主题的文章,想要了解的朋友可以去翻一下之前的文章

    题目链接:

    题目大意:  给出初始化区间的值，有m次操作

                  Q a b讯问[a,b]区间中的最大值，U a b将第a个元素替换为b

    解题思绪:  线段树    更新:单点替换   讯问:区间讯问

                 每次更新的时候在区间结点存储此区间的最大值，查询的时候就不须要每次都查到最下面

                 更新时间复杂度O(logN)，讯问时间复杂度O(logN)

    代码:

    

    每日一道理

如果人类不好好保护我们这个赖以生存的地球，终有一天，风沙的肆虐与垃圾的堆积会吞没我们美丽的家园。我向全世界的人们呼吁：让我们从现在开始，从我做起，手挽手，肩并肩共同保护建设我们的家园吧！

#include 
    
     #include 
     
      #include 
      
       #define MAXN 200005#define MAX(a,b) a>b?a:b#define MID(a,b) (a+b)>>1#define L(a) a<<1#define R(a) (a<<1)+1typedef struct snode{    int left,right;    int max;}Node;Node Tree[MAXN<<2];int num[MAXN],max;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=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(左子树，右子树)}void Insert(int t,int l,int r,int n)   //向根结点为t，左子树为l，右子树为r的区间替换元素n{    int mid;    if(Tree[t].left==l&&Tree[t].right==r)    {        Tree[t].max=n;        return ;    }    mid=MID(Tree[t].left,Tree[t].right);    if(l>mid)        Insert(R(t),l,r,n);    else if(r<=mid)        Insert(L(t),l,r,n);    else    {        Insert(L(t),l,mid,n);        Insert(R(t),mid+1,r,n);    }    Tree[t].max=MAX(Tree[L(t)].max,Tree[R(t)].max);  //每次插入从下往上更新}void Query(int t,int l,int r)        //查询根结点为t，左子树为l，右子树为r的区间最大值{    int mid;    if(Tree[t].left==l&&Tree[t].right==r)    {        if(max
       
        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(){    char ch;    int n,m,i,a,b;    while(scanf("%d%d",&n,&m)!=EOF)    {        for(i=1;i<=n;i++)            scanf("%d",&num[i]);        memset(Tree,0,sizeof(Tree));   //初始化线段树        Build(1,1,n);                  //1节电为根结电建立线段树        getchar();        for(i=0;i
       
      
     
    

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

    

    

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

　　1、头皮经常发麻，在看见一个蓝色屏幕的时候比较明显，在屏幕上什幺都看不见的时候尤其明显；

　　2、乘电梯的时候总担心死机，并且在墙上找reset键；

　　3、指甲特别长，因为按F7到F12比较省力；

　　4、只要手里有东西，就不停地按，以为是Alt-F、S；

　　5、机箱从来不上盖子，以便判断硬盘是否在转；

　　6、经常莫名其妙地跟踪别人，手里不停按F10；

　　7、所有的接口都插上了硬盘，因此觉得26个字母不够；

　　8、一有空就念叨“下辈子不做程序员了”；

　　9、总是觉得9号以后是a号；

　　10、不怕病毒，但是很害怕自己的程序；

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

树和线段

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