（线段树）单点更新，区间查询最值

关键词：

/* 单点更新，区间查询最值  */
/* 注意线段树的大小要比需要使用线段树的数据的个数 大3到4倍  */

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std ;

#define maxn 4000001
struct node {
    int le , ri ;
    int num ;
};

node tree[maxn*4] ;
int a[maxn] ;

int n , m ;
char ch ;
int x , y ;

void build(int root , int l , int r){
    if(l == r){
        tree[root].le = tree[root].ri = l ;
        tree[root].num = a[l] ;  
        return;
    }
    
    tree[root].le = l ;
    tree[root].ri = r ;
    
    int mid = (l + r) /2 ;
    build(root*2 , l , mid) ;
    build(root*2+1 , mid + 1 , r) ;
    
    tree[root].num = max(tree[root*2].num , tree[root*2+1].num) ;  
}

// 单点更新  （二叉查询）
void update(int root , int pos , int value ){
    if(tree[root].le == pos && tree[root].ri == pos){
        tree[root].num = value ;
        return;
    }
    
    int mid = (tree[root].le + tree[root].ri)/2 ;
    if(pos <= mid){//（二叉查询）
        update(root*2 , pos , value) ;
    } else {
        update(root*2+1 , pos , value) ;
    }
    
    tree[root].num = max(tree[root*2].num , tree[root*2+1].num) ;
}

//查询区间【start,end】中的最大值
int query(int root , int start , int ends){
    if(tree[root].le == start && tree[root].ri == ends){
        return tree[root].num ;
    }
    int mid = (tree[root].le + tree[root].ri)/2 ;
    //[start,mid] (mid , ends] .
    if( mid < start ){
        return query(root*2+1 , start , ends) ;
    } else if(ends <= mid ){
        return query(root*2 , start , ends) ;
    } else if( start <= mid && mid < ends){
        return max(query(root*2 , start , mid) , query(root*2+1 , mid+1 , ends) ) ;
    }
    
}

int main(){
    while(~scanf("%d%d" , &n , &m)){
        for(int i=1 ; i<=n ; i++){
            scanf("%d" , &a[i]) ;
        }
        build(1 , 1 , n ) ;
        
        for(int i=1 ; i<=m ; i++){
            scanf(" %c" , &ch) ;
            scanf("%d%d" , &x , &y) ;
            
            if(ch == ‘Q‘){
                printf("%d
" , query(1 ,x , y )) ;
            }
            if(ch == ‘U‘){
                update(1 , x , y ) ;
            }
            cout<<1<<endl ;  
        }
    }
    return 0 ;
}

hdu1754ihateit（线段树之单点更新区间最值查询）(代码片段)

IHateItTimeLimit:9000/3000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):101699    AcceptedSubmission(s):38294ProblemDescription很多学校 查看详情

线段树及其基本操作

...惰标记了解一下，其余略 实现步骤：略 备注：在线段树里，单点更新与单点累加和树状数组上的单点跟新有区别，树状数组还需与原数组求差值，线段树不用。线段树的区间求最值差别不大，在此贴一份A过题的最值代... 查看详情

hdu1754ihateit(线段树之单点更新，区间最值)

IHateItTimeLimit:9000/3000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):70863    AcceptedSubmission(s):27424ProblemDescription很多学校流 查看详情

hdu1754ihateit（线段树之单点更新+区间最值）

IHateIt                                & 查看详情

线段树区间最值单点更新模板bnuoj52965eexcellentengineers

http://acm.bnu.edu.cn/v3/external/gym/101512.pdf1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4#defineN1000105#definels(p)(p<<1)6#definers(p)(p<<1|1)7constintINF=1e9; 查看详情

51nod1287(二分/线段树区间最值&单点更新)

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1287 题意：中文题诶～ 解法１：b[i]存储max(a[0],.....,a[i])，显然b是单调不减的，所以直接二分x，再更新a和b数组即可； 代码：1#include<iostream>2#include<st 查看详情

hdu2795(线段树单点更新&区间最值)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2795 题意：有一个h*w的板子，要在上面贴n条1*x的广告，在贴第i条广告时要尽量将其靠上贴，并输出其最上能贴在哪个位置； 思路：可以将每行剩余空间大小存储到一个数组中，... 查看详情

hdu2795billboard(线段树单点更新&&求区间最值位置)

...都尽量选择靠上靠左的位置，那既然这样，我们以1~h建立线段树，给每一个叶子节点赋值初值w表示当前行最大能够容纳宽度为w的公告纸，那么对于某一输入wi只要在线段树的尽量靠左的区间找出能够容纳这张公告的位置（即叶 查看详情

hdu1540tunnelwarfare（线段树，单点更新，区间查询）

ProblemDescriptionDuringtheWarofResistanceAgainstJapan,tunnelwarfarewascarriedoutextensivelyinthevastareasofnorthChinaPlain.Generallyspeaking,villagesconnectedbytunnelslayinaline.Exceptthetwoattheends 查看详情

hdu3308线段树区间合并+单点更新+区间查询

LCISTimeLimit:6000/2000MS(Java/Others)    MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):6592    AcceptedSubmission(s):2866ProblemDescriptionGivenninte 查看详情

acm-icpc国际大学生程序设计竞赛北京赛区(2017)网络赛hihocoder#1586:minimum-区间查询最值求区间两数最小乘积+单点更新-线段树(结构体版)(代码片段)

#1586:MinimumTimeLimit:1000msCaseTimeLimit:1000msMemoryLimit:256MBDescriptionYouaregivenalistofintegersa0,a1,…,a2^k-1.Youneedtosupporttwotypesofqueries:1.OutputMinx,y∈[l,r] ax?ay.2.Letax=y.Inpu 查看详情

hdu-1754ihateit(线段树区间求最值)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1754题意：线段树的单点更新和区间求最值模板题，,,???,, 1#include<cstdio>2#include<iostream>3usingnamespacestd;45typedeflonglongLL;6constintN=200010;78LLans;9L 查看详情

hihocoderweek19rmq问题再临-线段树单点更新区间查询(代码片段)

单点更新区间查询 #include<bits/stdc++.h>usingnamespacestd;#definem((l+r)/2)#definels(rt<<1)#definers(rt<<1|1)constintN=2e6+10;ints[N],tr[N];voidbuild(intrt,intl,intr)if(l==r)tr[rt]=s[ 查看详情

线段树第二弹（区间更新）

...sp;       上篇文章，我们介绍了线段树的基本概念和单点更新、区间查询，今天，我们来接着上次的线段树问题继续深入研究。在解决线段树问题的过程中，我们会遇到要求修改区间中某一元素值的问题... 查看详情

zoj1610countthecolors题意+线段树区间更新&&单点查询(代码片段)

任意门：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1610CounttheColorsTimeLimit: 2Seconds     MemoryLimit: 65536KBPaintingsomecoloredsegmentsonaline,som 查看详情

hdu1754-zkw线段树(代码片段)

单点更新，区间最值 HDU1754////Createdbyhelicaon2018/3/18.////zkw线段树单点修改区间求最值//HDU1754#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>usingnamespacestd;constint 查看详情

hdu1166-敌兵布阵-[单点修改区间查询zkw线段树]

...：http://www.cnblogs.com/dilthey/p/6827959.html不过我们今天换一种线段树实现来做这道题；关于zkw线段树的讲解：https://zhuanlan.zhihu.com/p/29876526（而且我还在文章里被@了，超开心的ヾ(≧?≦*)ヾ）可以说是讲解非常的清楚了！ AC代码（... 查看详情

模板线段树-单点修改，区间查询

...打（又长又难调）------仅代表个人观点（能别打就别打）线段树是什么？大概长这样？（表示区间1到6）线段树是一颗二叉树，是通过二分思想建立的一颗表示区间关系的树形结构。（总之记住它很好用就对了）怎样建一颗线段... 查看详情