线段树基础合集

codevs上的一些题，是线段树入门(裸)题，比较全面。

包括：

1080：单点修改，区间求和

1081：区间add，询问单点值

1082：区间add，区间求和

4919：复杂一点的区间修改，区间求和

4927：区间add，区间set，区间求和

另外还有我不会的

，大佬说是分块做？

CodeVS-1080

裸地基本线段树，当个板子吧。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <iomanip>
#include <string>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

using namespace std;
const int MAXN = ;
const int MA_XN=;
const int oo = ;
const long long int loo = l;
typedef long long int ll;
typedef struct{
    int data;
    int lazy;
} tree;
tree sum[MAXN<<];


void PushUP(int rt){
    sum[rt].data=sum[rt<<].data+sum[rt<<|].data;}
void build (int l,int r,int rt){
    if ( l == r )
    {
        int ttt;
        scanf("%d",&ttt);
        sum[rt].data=ttt;
        return;
    }
    int m = ( l + r ) >> ;
    build (lson);
    build (rson);
    PushUP ( rt );
}
void update(int p,int num,int l,int r,int rt)
{
    if(l==r)
    {
        sum[rt].data+=num;
        return;
    }
    int m=(l+r)>>;
    if(p<=m)
    {
        update(p,num,lson);
    }
    if(p>m)
    {
        update(p,num,rson);
    }
    PushUP(rt);
}
ll query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        return sum[rt].data;
    }
    int m=(l+r)>>;
    ll res=;
    if(L<=m) res+=query(L,R,lson);
    if(m<R) res+=query(L,R,rson);
    return res;
}
int main ()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(sum,,sizeof(sum));
        build(,n,);
        int m;
        scanf("%d",&m);
        for(int i=;i<m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if(a==)
            {
                //加法
                update(b,c,,n,);
            }
            else
            {
                int res=query(b,c,,n,);
                printf("%d\n",res);
            }
        }
    }
    return ;
}

CodeVS-1081

这题很无聊，询问单点值。直接参考1082的代码吧。

CodeVS-1082

基本的lazy标记使用。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
#define M(a,b) memset(a,b,sizeof(a))
#define N n
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

using namespace std;

const int MAXN=;
const int oo=;
typedef long long LL;
const LL loo=l;
typedef long double LB;
const LL mod=+;
const double eps=;
struct SegmentTree
{
    LL sum;
    int lazy;
}stree[*MAXN];

void pushup(int rt)
{
    stree[rt].sum=stree[rt<<].sum+stree[rt<<|].sum;
}
void pushdown(int rt, int m)
{
    if(stree[rt].lazy!=)
    {
        stree[rt<<].sum+=LL(m-(m>>))*stree[rt].lazy;
        stree[rt<<|].sum+=LL(m>>)*stree[rt].lazy;
        stree[rt<<].lazy+=stree[rt].lazy;
        stree[rt<<|].lazy+=stree[rt].lazy;
        stree[rt].lazy=;
    }
}
void build(int l, int r, int rt)
{
    if(l==r)
    {
        int tmp;scanf("%d", &tmp);
        stree[rt].sum=tmp;
        stree[rt].lazy=;
        return;
    }
    int m=(l+r)>>;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int L, int R, int c, int l, int r, int rt)
{
    if(L<=l&&r<=R)
    {
        stree[rt].sum+=LL(r-l+)*c;
        stree[rt].lazy+=c;
        return;
    }
    pushdown(rt, r-l+);
    int m=(l+r)>>;
    if(L<=m) update(L, R, c, lson);
    if(m<R) update(L, R, c, rson);
    pushup(rt);
}
LL query(int L, int R, int l, int r, int rt)
{
    if(L<=l&&r<=R)
    {
        return stree[rt].sum;
    }
    pushdown(rt, r-l+);
    int m=(l+r)>>;
    LL res=;
    if(L<=m) res+=query(L,R, lson);
    if(m<R) res+=query(L, R, rson);
    return res;
}
int main(int argc, char *argv[])
{
    int m, n;
    while(scanf("%d", &n)==)
    {
        build(, n, );
        int m;scanf("%d", &m);
        while(m--)
        {
            int cz;scanf("%d", &cz);
            if(cz==)
            {
                int l, r, c;scanf("%d%d%d", &l, &r, &c);
                update(l, r, c, , n, );
            }
            else
            {
                int l, r;scanf("%d%d", &l, &r);
                printf("%lld\n", query(l, r, , n, ));
            }
        }
    }

    return ;
}

CodeVS-4919

复杂一点的区间修改，问多少数能被7整除。

因为涉及区间的加法，很容易想到，加法相当于shift操作。线段树的每个点上开一个长度7的数组，记录区间内模7余0123456的数分别有多少个。区间加法相当于shift操作。合并直接合并左右区间对应余数的个数即可。配合lazy使用。

另注：5037跟这题表面很像，实际这题的方法用不了。我表示无能为力。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
#define M(a,b) memset(a,b,sizeof(a))
#define N n
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

using namespace std;

const int MAXN=;
const int oo=;
typedef long long LL;
const LL loo=l;
typedef long double LB;
const LL mod=+;
const double eps=;
struct SegmentTree
{
    LL sum[];
    int lazy;
}stree[*MAXN];

void pushup(int rt)
{
    for(int i=;i<;i++)
        stree[rt].sum[i]=stree[rt<<].sum[i]+stree[rt<<|].sum[i];
}
void pushdown(int rt)
{
    if(stree[rt].lazy!=)
    {
        int py=stree[rt].lazy;
        int tmp[];
        for(int i=;i<;i++) tmp[i]=stree[rt<<].sum[i];
        for(int i=;i<;i++) stree[rt<<].sum[(i+py)%]=tmp[i];
        for(int i=;i<;i++) tmp[i]=stree[rt<<|].sum[i];
        for(int i=;i<;i++) stree[rt<<|].sum[(i+py)%]=tmp[i];

        stree[rt<<].lazy+=stree[rt].lazy;
        stree[rt<<|].lazy+=stree[rt].lazy;
        stree[rt].lazy=;
    }
}
void build(int l, int r, int rt)
{
    if(l==r)
    {
        for(int i=;i<;i++) stree[rt].sum[i]=;
        int tmp;scanf("%d", &tmp);
        stree[rt].sum[tmp%]=;
        stree[rt].lazy=;
        return;
    }
    int m=(l+r)>>;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int L, int R, int c, int l, int r, int rt)
{
    if(L<=l&&r<=R)
    {
        int py=c;
        int tmp[];
        for(int i=;i<;i++) tmp[i]=stree[rt].sum[i];
        for(int i=;i<;i++) stree[rt].sum[(i+py)%]=tmp[i];
        stree[rt].lazy+=c;
        return;
    }
    pushdown(rt);
    int m=(l+r)>>;
    if(L<=m) update(L, R, c, lson);
    if(m<R) update(L, R, c, rson);
    pushup(rt);
}
LL query(int L, int R, int l, int r, int rt)
{
    if(L<=l&&r<=R)
    {
        return stree[rt].sum[];
    }
    pushdown(rt);
    int m=(l+r)>>;
    LL res=;
    if(L<=m) res+=query(L, R, lson);
    if(m<R) res+=query(L, R, rson);
    return res;
}
int main(int argc, char *argv[])
{
    int m, n;
    while(scanf("%d", &n)==)
    {
        build(, n, );
        int m;scanf("%d", &m);
        while(m--)
        {
            char cz[];scanf("%s", cz);
            if(cz[]=='a')
            {
                int l, r, c;scanf("%d%d%d", &l, &r, &c);
                update(l, r, c%, , n, );
            }
            else
            {
                int l, r;scanf("%d%d", &l, &r);
                printf("%lld\n", query(l, r, , n, ));
            }
        }
    }
    return ;
}

CodeVS-4927

这题涉及两个lazy标记的传递顺序问题。set的优先级要高于add：比如一些数，我先add，在set，那么add便没用了；而我先set，在add，那么这个add也是有用的，仍需要向下传递。

按我的代码风格，每添加一个标记，立马修改本区间的值(sum,max,min)，并设置本区间lazy有效；若添加的标记是set，那么置本区间add无效；待查询时，要是查询本区间，那么不传递lazy，查询子区间时经过本区间，那么向下传递lazy。

向下传递lazy时注意：若set有效，那么先传递set，并置子区间的add无效；若本区间set与add同时有效，说明本区间先set后add过，两标记都要向下传递！我最开始犯了两个错误：1是传递set后将本区间的add也置为无效了；2是传递完set就return了。因为我的代码风格，set后置本区间add无效（子区间也是如此，因为向下传递set时置了add无效），所以addset同时出现一定是先set后add。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
#define M(a,b) memset(a,b,sizeof(a))
#define N n
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

using namespace std;

const int MAXN=;
const int oo=;
typedef long long LL;
const LL loo=l;
typedef long double LB;
const LL mod=+;
const double eps=;
struct SegmentTree
{
    LL sum;
    LL lazy;
    LL set;
    bool sset;
    LL mi;
    LL ma;
}stree[*MAXN];

void pushup(int rt)
{
    stree[rt].sum=stree[rt<<].sum+stree[rt<<|].sum;
    stree[rt].mi=min(stree[rt<<].mi, stree[rt<<|].mi);
    stree[rt].ma=max(stree[rt<<].ma, stree[rt<<|].ma);
}
void pushdown(int rt, int m)
{
    if(stree[rt].sset==true)
    {
        LL tmp=stree[rt].set;stree[rt].set=;stree[rt].sset=false;
        stree[rt<<].sum=tmp*(m-(m>>));
        stree[rt<<|].sum=tmp*(m>>);
        stree[rt<<].ma=stree[rt<<|].ma=tmp;
        stree[rt<<].mi=stree[rt<<|].mi=tmp;
        stree[rt<<].set=stree[rt<<|].set=tmp;
        stree[rt<<].sset=stree[rt<<|].sset=true;

        /*stree[rt].lazy=0;*/stree[rt<<].lazy=;stree[rt<<|].lazy=;
        //return;
    }
    if(stree[rt].lazy!=)
    {
        LL tmp=stree[rt].lazy;stree[rt].lazy=;
        stree[rt<<].sum+=tmp*(m-(m>>));
        stree[rt<<|].sum+=tmp*(m>>);
        stree[rt<<].ma+=tmp;stree[rt<<|].ma+=tmp;
        stree[rt<<].mi+=tmp;stree[rt<<|].mi+=tmp;
        stree[rt<<].lazy+=tmp;stree[rt<<|].lazy+=tmp;
    }
}
void build(int l, int r, int rt)
{
    if(l==r)
    {
        LL tmp;scanf("%lld", &tmp);
        stree[rt].sum=stree[rt].ma=stree[rt].mi=tmp;
        stree[rt].lazy=stree[rt].set=stree[rt].sset=;
        return;
    }
    int m=(l+r)>>;
    build(lson);
    build(rson);
    pushup(rt);
}
void update_set(int L, int R, LL s, int l, int r, int rt)
{
    if(L<=l&&r<=R)
    {
        stree[rt].sum=(LL)s*(r-l+);
        stree[rt].ma=stree[rt].mi=s;
        stree[rt].set=s;
        stree[rt].sset=true;
        stree[rt].lazy=;
        pushdown(rt, r-l+);
        return;
    }
    pushdown(rt, r-l+);
    int m=(l+r)>>;
    if(L<=m) update_set(L, R, s, lson);
    if(m<R) update_set(L, R, s, rson);
    pushup(rt);
}
void update_add(int L, int R, LL c, int l, int r, int rt)
{
    if(L<=l&&r<=R)
    {
        stree[rt].sum+=(LL)c*(r-l+);
        stree[rt].ma+=c;
        stree[rt].mi+=c;
        stree[rt].lazy+=c;
        pushdown(rt, r-l+);
        return;
    }
    pushdown(rt, r-l+);
    int m=(l+r)>>;
    if(L<=m) update_add(L, R, c, lson);
    if(m<R) update_add(L, R, c, rson);
    pushup(rt);
}
LL query_sum(int L, int R, int l, int r, int rt)
{
    if(L<=l&&r<=R)
    {
        return stree[rt].sum;
    }
    pushdown(rt, r-l+);
    int m=(l+r)>>;
    LL res=;
    if(L<=m) res+=query_sum(L, R, lson);
    if(m<R) res+=query_sum(L, R, rson);
    return res;
}
LL query_ma(int L, int R, int l, int r, int rt)
{
    if(L<=l&&r<=R)
    {
        return stree[rt].ma;
    }
    pushdown(rt, r-l+);
    int m=(l+r)>>;
    LL res=-loo;
    if(L<=m) res=max(res, query_ma(L, R, lson));
    if(m<R) res=max(res, query_ma(L, R, rson));
    return res;
}
LL query_mi(int L, int R, int l, int r, int rt)
{
    if(L<=l&&r<=R)
    {
        return stree[rt].mi;
    }
    pushdown(rt, r-l+);
    int m=(l+r)>>;
    LL res=loo;
    if(L<=m) res=min(res, query_mi(L, R, lson));
    if(m<R) res=min(res, query_mi(L, R, rson));
    return res;
}
int main(int argc, char *argv[])
{
    int m, n;
    while(scanf("%d%d", &n, &m)==)
    {
        M(stree, );
        build(, n, );
        while(m--)
        {
            char cz[];scanf("%s", cz);
            if(cz[]=='d')
            {
                int l, r;LL c;scanf("%d%d%lld", &l, &r, &c);
                update_add(l, r, c, , n, );
            }
            else if(cz[]=='e')
            {
                int l, r;LL c;scanf("%d%d%lld", &l, &r, &c);
                update_set(l, r, c, , n, );
            }
            else if(cz[]=='u')
            {
                int l, r;scanf("%d%d", &l, &r);
                printf("%lld\n", query_sum(l, r, , n, ));
            }
            else if(cz[]=='a')
            {
                int l, r;scanf("%d%d", &l, &r);
                printf("%lld\n", query_ma(l, r, , n, ));
            }
            else
            {
                int l, r;scanf("%d%d", &l, &r);
                printf("%lld\n", query_mi(l, r, , n, ));
            }
        }
    }
    return ;
}

线段树基础合集线段树基础合集

线段树基础合集

CodeVS-1080

CodeVS-1081

CodeVS-1082

CodeVS-4919

CodeVS-4927

继续阅读

C++实现反射（三）

UVALive 7141 BombX

HDU 5023 A Corrupt Mayor's Performance Art （线段树）

hdu 5023 A Corrupt Mayor's Performance Art

[HDU5023]A Corrupt Mayor's Performance Art

hdu 5023 A Corrupt Mayor's Performance Art（线段树+位运算）

【HDU 5023】A Corrupt Mayor's Performance Art 【线段树+状态压缩】

HDU5023(A Corrupt Mayor‘s Performance Art)

A Corrupt Mayor's Performance Art HDU - 5023

hdu 5023 A Corrupt Mayor's Performance Art(线段树区间更新)

POJ 1734 Sightseeing trip

洛谷 P3373 【模板】线段树 2

WIKIOI 1282 约瑟夫问题

迟来的4月小结

HDU 3397 Sequence operation

HDU 5381 The sum of gcd