I Hate It

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1754

解题思路

区间访问,单点修改。
算是个板子题,所以没有题解。
里面有大佬讲解线段树
我觉得线段树入门的话,说实话就一个板子,如果能自己敲出来说明入门了;
怎么入门?开始第一次学的时候,学了两天还是不能理解,即使理解了也只看到了皮毛,勉强背过板子,但其实是真的没有理解什么是线段树,要如何实现;
但是从那次学完之后,我就把线段树扔在脑后一个月,这次又拿起来一看,感觉大彻大悟,在没有看板子的情况下,直接猛敲,还是很爽的;
我这么说的就是希望如果一时不能理解某些东西,我们这种小白不要太着急,时间会沉淀知识的!

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long

using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f;

int n,m,stu[N],tree[N<<2],a,b;
char op;

void Build(int l,int r,int i)
{
    if(l==r) 
    {
        tree[i]=stu[l];
        return ;    
    }
    int mid=(l+r)>>1;
    Build(l,mid,i<<1);
    Build(mid+1,r,i<<1|1);
    tree[i]=max(tree[i<<1],tree[i<<1|1]);
    return ;
}
void Update(int l,int r,int i,int x,int y)
{
    if(l==r) 
    {
        tree[i]=y;
        return ;
    }
    int mid=(l+r)>>1;
    if(x>mid) Update(mid+1,r,i<<1|1,x,y);//right subtree
    else Update(l,mid,i<<1,x,y);//left subtree
    tree[i]=max(tree[i<<1],tree[i<<1|1]);
    return ;
}
int Query(int l,int r,int i,int x,int y)
{
    int res=-inf;
    if(x<=l && r<=y)
    return tree[i];
    if(x>r || y<l) return 0;
    int mid=(l+r)>>1;
    if(x<=mid) res=max(res,Query(l,mid,i<<1,x,y));//left subtree
    if(y>mid) res=max(res,Query(mid+1,r,i<<1|1,x,y));//right subtree
    return res;    
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        memset(tree,0,sizeof tree);
        for(int i=1;i<=n;i++)
        scanf("%d",&stu[i]);
        Build(1,n,1);
        while(m--)
        {
            cin>>op>>a>>b;
            if(op=='Q')
            printf("%d\n",Query(1,n,1,a,b));
            else
            Update(1,n,1,a,b);
        }
    }    
    return 0;
}
线段树 文章被收录于专栏

菜鸡随便搞一波

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-16 02:48
门头沟学院_2022
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-11 21:41
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-15 18:06
华南理工大学_2023
点赞 评论 收藏
转发
1 收藏 评论
分享

全站热榜

正在热议