线段树

2023/6/13 C++ 算法竞赛 线段树

线段树是很重要的数据结构，它的扩展性比树状数组强得多。

文章

知乎有一篇文章讲的不错

算法学习笔记(14): 线段树

核心代码

ll tree[N<<2],a[N],tag[N<<2];
ll ls(ll x){return x<<1;}
ll rs(ll x){return x<<1|1;}
void push_up(ll p)
{
    tree[p]=tree[ls(p)]+tree[rs(p)];
}
void build(ll p,ll pl,ll pr)
{
    tag[p]=0;
    if(pl==pr)
    {
        tree[p]=a[pl];
        return;
    }
    ll mid=(pl+pr)>>1;
    build(ls(p),pl,mid);
    build(rs(p),mid+1,pr);
    push_up(p);
}
void addtag(ll p,ll pl,ll pr,ll d)
{
    tag[p]+=d;
    tree[p]+=d*(pr-pl+1);
}
void push_down(ll p,ll pl,ll pr)
{
    if(tag[p])
    {
        ll mid=(pl+pr)>>1;
        addtag(ls(p),pl,mid,tag[p]);
        addtag(rs(p),mid+1,pr,tag[p]);
        tag[p]=0;
    }
}
void update(ll L,ll R,ll p,ll pl,ll pr,ll d)
{
    if(L<=pl&&pr<=R)
    {
        addtag(p,pl,pr,d);
        return;
    }
    push_down(p,pl,pr);
    ll mid=(pl+pr)>>1;
    if(L<=mid)
        update(L,R,ls(p),pl,mid,d);
    if(mid<R)
        update(L,R,rs(p),mid+1,pr,d);
    push_up(p);
}
ll query(ll L,ll R,ll p,ll pl,ll pr)
{
    if(pl>=L&&pr<=R)
        return tree[p];
    push_down(p,pl,pr);
    ll res=0;
    ll mid=(pl+pr)>>1;
    if(L<=mid)
        res+=query(L,R,ls(p),pl,mid);
    if(R>mid)
        res+=query(L,R,rs(p),mid+1,pr);
    return res;
}

例题

洛谷P3372 [模板]线段树1

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll tree[N<<2],a[N],tag[N<<2];
ll ls(ll x){return x<<1;}
ll rs(ll x){return x<<1|1;}
void push_up(ll p)
{
    tree[p]=tree[ls(p)]+tree[rs(p)];
}
void build(ll p,ll pl,ll pr)
{
    tag[p]=0;
    if(pl==pr)
    {
        tree[p]=a[pl];
        return;
    }
    ll mid=(pl+pr)>>1;
    build(ls(p),pl,mid);
    build(rs(p),mid+1,pr);
    push_up(p);
}
void addtag(ll p,ll pl,ll pr,ll d)
{
    tag[p]+=d;
    tree[p]+=d*(pr-pl+1);
}
void push_down(ll p,ll pl,ll pr)
{
    if(tag[p])
    {
        ll mid=(pl+pr)>>1;
        addtag(ls(p),pl,mid,tag[p]);
        addtag(rs(p),mid+1,pr,tag[p]);
        tag[p]=0;
    }
}
void update(ll L,ll R,ll p,ll pl,ll pr,ll d)
{
    if(L<=pl&&pr<=R)
    {
        addtag(p,pl,pr,d);
        return;
    }
    push_down(p,pl,pr);
    ll mid=(pl+pr)>>1;
    if(L<=mid)
        update(L,R,ls(p),pl,mid,d);
    if(mid<R)
        update(L,R,rs(p),mid+1,pr,d);
    push_up(p);
}
ll query(ll L,ll R,ll p,ll pl,ll pr)
{
    if(pl>=L&&pr<=R)
        return tree[p];
    push_down(p,pl,pr);
    ll res=0;
    ll mid=(pl+pr)>>1;
    if(L<=mid)
        res+=query(L,R,ls(p),pl,mid);
    if(R>mid)
        res+=query(L,R,rs(p),mid+1,pr);
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1)
        {
            int k;
            cin>>k;
            update(x,y,1,1,n,k);
        }
        else if(op==2)
            cout<<query(x,y,1,1,n)<<'\n';
    }
    return 0;
}
img_show