首页 > 其他 > 详细

线段树之各类模板

时间:2018-05-21 20:15:35      阅读:180      评论:0      收藏:0      [点我收藏+]

线段树的认识,可以参考哔哔丽丽的视频。

(1)单点曽减,区间求和

飞翔

技术分享图片
#include<stdio.h>
#define lson l,m,rt<<1///左儿子
#define rson m+1,r,rt<<1|1///右儿子
const int maxn = 55555;
int sum[maxn<<2];
void PushUP(int rt)///上一个的值由两个儿子相加
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt)///建立
{
    if(l==r)
    {
        scanf("%d",&sum[rt]);///在建立的过程中赋值
        return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    PushUP(rt);
}
void update(int p,int add,int l,int r,int rt)
///p点增减add
{
    if(l==r)
    {
       sum[rt]+=add;
       return ;
    }
    int m=(l+r)>>1;
    if(p<=m)
    update(p,add,lson);
    else
    update(p,add,rson);
    PushUP(rt);
}
///LR区间求和
int query(int L,int R,int l,int r,int rt)
{
    if(L <= l && r<=R)
        return sum[rt];
    int m=(l+r)>>1;
    int ret=0;
    if(L <= m )
    ret+=query(L,R,lson);
    if(R > m)
    ret+=query(L,R,rson);
    return ret;
}
int main( )
{
    int a,b,t,n;
    scanf("%d",&t);
    for(int cas=1 ; cas<=t ; cas++)
    {
        printf("Case %d:\n",cas);
        scanf("%d",&n);
        build(1,n,1);
        char op[10];
        while(scanf("%s",op))
        {
            if(op[0]==E)
            break;
            int a,b;
            scanf("%d%d",&a,&b);
            if(op[0]==S)
            update(a,-b,1,n,1);
            else if(op[0]==Q)
            printf("%d\n",query(a,b,1,n,1));
            else
            update(a,b,1,n,1);
        }
    }
    return 0;
}
View Code

(2)单点替换,区间最值

飞翔

技术分享图片
#include<stdio.h>
#include<algorithm>
using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

const int manx = 222222;
int MAX[manx<<2];
void PushUP(int rt)///父亲的值由儿子来得出
{
    MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}
void build(int l,int r,int rt)
{
    if ( l==r )
    {
        scanf("%d",&MAX[rt]);
        return ;
    }
    int m = (l+r) >> 1;
    build(lson);
    build(rson);
    PushUP(rt);
}
void update(int p,int sc,int l,int r,int rt)
{   
    ///p点变为sc
    if (l==r)
    {
        MAX[rt]=sc;
        return ;
    }
    int m=(l+r)>>1;
    if(p <= m )
    update(p,sc,lson);
    else
    update(p,sc,rson);
    PushUP(rt);

}
int query(int L,int R,int l,int r,int rt)
{    ///L到R的最大值
    if(L <= l&&r<= R)
        return MAX[rt];
    int m=(l+r)>>1;
    int ret=0;
    if(L<=m)
    ret=max(ret,query(L,R,lson));
    if(R>m)
    ret=max(ret,query(L,R,rson));
    return ret;
}
int main( )
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        build(1,n,1);
        while(m--)
        {
            char op[2];
            int a,b;
            scanf("%s%d%d",op,&a,&b);
            if(op[0]==Q)
            printf("%d\n",query(a,b,1,n,1));
            else
            update(a,b,1,n,1);
        }
    }
    return 0;
}
View Code

 感激这位大牛的模板

线段树之各类模板

原文:https://www.cnblogs.com/shuaihui520/p/9069021.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!