线段树(模板)

刚学了线段树,趁现在理解比较清楚,写篇博客供以后翻阅,线段树有很多应用,如求区间总和,最大值,最小值等,总之求区间问题都可以想想线段树,这里以求和为例

定义全局变量

const int maxn=1e5+10;
struct node
{
    int L,R;//当前节点的左右区间
    long long big,sum,lazy;//数据类型根据题意改,sum为当前节点的总和
} tree[4*maxn];//开四倍于数据量的空间

回溯函数

void pushup(int p)
{
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}

建树

void build(int l,int r,int p)
{
    tree[p].L=l,tree[p].R=r,tree[p].lazy=0;//给当前节点的左右区间和lazy初始值
    if(l==r)//叶子节点为递归边界
    {
        scanf("%lld",&tree[p].sum); //这里直接写入,减少使用一个存放数据的数组
        return ;//一定要return掉哦~
    }
    int mid=(l+r)/2;
    build(l,mid,2*p);//向左递归
    build(mid+1,r,p*2+1);//向右递归
    pushup(p);//回溯改变父亲节点的值
}

下压函数

//用于区间查询和区间修改,根据当前节点的lazy_tag改变儿子节点的数据
void pushdown(int p,int l,int r)//这里的l,r为左右孩子在待求区间里的个数,参照下面的查询函数理解
{
    if(tree[p].lazy)
    {
        tree[p*2].lazy+=tree[p].lazy;//改变儿子节点的lazy_tag
        tree[p*2+1].lazy+=tree[p].lazy;
        tree[p*2].sum+=tree[p].lazy*l;//根据当前节点lazy_tag改变儿子节点的值,这里可以体现lazy的延迟性
        tree[p*2+1].sum+=tree[p].lazy*r;
        tree[p].lazy=0;//当前节点的lazy变为0,完成下压操作
    }
}

区间查询

long long Quary(int a,int b,int p)//a,b为待求区间,p为当前节点的下标
{
    long long awn=0;//输出的待求区间的总和
    int l=tree[p].L;
    int r=tree[p].R;
    if(a<=l&&r<=b)//如果待求区间比当前节点包含的区间大,直接返回当前区间的值
    {
        return tree[p].sum;
    }
    int mid=(l+r)/2;
    pushdown(p,mid-l+1,r-mid);//2,3参数表示左右分别有几个含在区间内
    if(a<=mid)
        awn+=Quary(a,b,2*p);
    if(b>mid)//注意这里不能加等号,不然死循环导致越界
        awn+=Quary(a,b,2*p+1);
    return awn;
}

区间更新

void updata(int a,int b,int val,int p)
{
    int l=tree[p].L;
    int r=tree[p].R;
    if(a<=l&&r<=b)//如果待修改区间比当前节点的区间大,直接修改当前节点的值,同时修改lazy的值
    {
        tree[p].sum+=val*(r-l+1);
        tree[p].lazy+=val;
        return ;
    }
    int mid=(l+r)/2;
    pushdown(p,mid-l+1,r-mid);//lazy下压
    if(a<=mid)
        updata(a,b,val,2*p);
    if(b>mid)
        updata(a,b,val,2*p+1);
    pushup(p);
}

例题

vj C – A Simple Problem with Integers 模板题

AC代码:

#include <iostream>
#include <stdio.h>
using namespace std;

const int maxn=1e5+10;

struct node
{
    int L,R;
    long long big,sum,lazy;
} tree[4*maxn];
void pushup(int p)
{
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
void pushdown(int p,int l,int r)
{
    if(tree[p].lazy)
    {
        tree[p*2].lazy+=tree[p].lazy;
        tree[p*2+1].lazy+=tree[p].lazy;
        tree[p*2].sum+=tree[p].lazy*l;
        tree[p*2+1].sum+=tree[p].lazy*r;
        tree[p].lazy=0;
    }
}
void build(int l,int r,int p)
{
    tree[p].L=l,tree[p].R=r,tree[p].lazy=0;
    if(l==r)
    {
        scanf("%lld",&tree[p].sum);
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,2*p);
    build(mid+1,r,p*2+1);
    pushup(p);
}

long long Quary(int a,int b,int p)
{
    long long awn=0;
    int l=tree[p].L;
    int r=tree[p].R;
    if(a<=l&&r<=b)
    {
        return tree[p].sum;
    }
    int mid=(l+r)/2;
    pushdown(p,mid-l+1,r-mid);
    if(a<=mid)
        awn+=Quary(a,b,2*p);
    if(b>mid)
        awn+=Quary(a,b,2*p+1);
    return awn;
}

void updata(int a,int b,int val,int p)
{
    int l=tree[p].L;
    int r=tree[p].R;
    if(a<=l&&r<=b)
    {
        tree[p].sum+=val*(r-l+1);
        tree[p].lazy+=val;
        return ;
    }
    int mid=(l+r)/2;
    pushdown(p,mid-l+1,r-mid);
    if(a<=mid)
        updata(a,b,val,2*p);
    if(b>mid)
        updata(a,b,val,2*p+1);
    pushup(p);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    build(1,n,1);
    int a,b,c;
    char ch;
    while(m--)
    {
        getchar();
        scanf("%c%d%d",&ch,&a,&b);
        if(ch=='Q')
            printf("%lld\n",Quary(a,b,1));
        else
        {
            scanf("%d",&c);
            updata(a,b,c,1);
        }
    }

    return 0;
}

暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇