频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
初识线段树
2017-07-17 10:01:10      个评论    来源:cjj122的博客  
收藏   我要投稿

序列操作

【问题描述】

  给出一个有n个元素的的数组:A[1],A[2],…,A[n],你的任务是设计一个数据结构,支持以下三种操作:
  1 L R v:把A[L],A[L+1],…A[R]都增加v(v>=0)。
  2 L R v:把A[L],A[L+1],…A[R]都修改成(v>=0)。
  3 L R:计算A[L],A[L+1],…A[R]的元素和、最小值和最大值。
  输入保证任意时刻序列中所有元素和不超过10^9。
  
【输入格式】

  第一行包含 2 个正整数:n 和 m 。以下n行,每行一个整数,表示 A[i]。再以下 m 行,每行为上述三种操作之一。

【输出格式】

  针对操作类型3,依次输出元素和、最小值和最大值。

【输入样例】

10 7
1 2 3 4 5 6 7 8 9 10
3 4 8
1 3 7 2
2 4 8 5
3 3 7
1 6 9 1
2 3 5 0
3 4 7

【输出样例】
30 4 8
25 5 5
12 0 6

【数据范围】

1<=m,n<=100 000。
最初始的|A[i]|<=100。


#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=100005;
int minv[2*maxn],np,rt,maxv[2*maxn],sum[2*maxn],add[2*maxn],setv[2*maxn],a[maxn],lc[2*maxn],rc[2*maxn];
int n,m,ch,x,y,d;
void initial()
{
    rt=np=0;
    for(int i=1;i<=2*n;i++) setv[i]=-1;
    memset(lc,0,sizeof(lc));
    memset(rc,0,sizeof(rc));
}
void pushup(int now)
{
    minv[now]=min(minv[lc[now]],minv[rc[now]]);
    maxv[now]=max(maxv[lc[now]],maxv[rc[now]]);
    sum[now]=sum[lc[now]]+sum[rc[now]];
}
void pushdowncha(int now,int L,int R)
{
    if(setv[now]>=0)
    {
        int m=(L+R)>>1;
        add[lc[now]]=0;
        add[rc[now]]=0;
        maxv[lc[now]]=minv[lc[now]]=maxv[rc[now]]=minv[rc[now]]=setv[now];
        sum[lc[now]]=(m-L+1)*setv[now];
        sum[rc[now]]=(R-m)*setv[now];
        setv[lc[now]]=setv[now];
        setv[rc[now]]=setv[now];
        setv[now]=-1;
    }
}
void pushdownad(int now,int L,int R)
{
    if(add[now]>0)
    {
        int m=(L+R)>>1;
        sum[lc[now]]+=(m-L+1)*add[now];
        sum[rc[now]]+=(R-m)*add[now];
        maxv[lc[now]]+=add[now];
        add[lc[now]]+=add[now];
        maxv[rc[now]]+=add[now];
        add[rc[now]]+=add[now];

        minv[lc[now]]+=add[now];
        minv[rc[now]]+=add[now];
        add[now]=0;
    }
}
void build(int &now,int L,int R)
{
    now=++np;
    if(L==R)
    {
        maxv[now]=minv[now]=sum[now]=a[L];
        return;
    }
    int m=(L+R)>>1;
    build(lc[now],L,m);
    build(rc[now],m+1,R);
    pushup(now);
}
void update(int now,int L,int R,int i,int j,int d)
{
    if(L>=i && R<=j)
    {
        minv[now]+=d;
        maxv[now]+=d;
        sum[now]+=(R-L+1)*d;
        add[now]+=d;
        return;
    }
    pushdowncha(now,L,R);
    pushdownad(now,L,R);

    int m=(L+R)>>1;
    if(j<=m) update(lc[now],L,m,i,j,d);
    else if(i>m) update(rc[now],m+1,R,i,j,d);
    else
    {
        update(lc[now],L,m,i,m,d);
        update(rc[now],m+1,R,m+1,j,d);
    }
    pushup(now);
}
void change(int now,int L,int R,int i,int j,int d)
{
    if(L>=i && R<=j)
    {
        sum[now]=(R-L+1)*d;
        maxv[now]=minv[now]=d;
        setv[now]=d;
        add[now]=0;//保证了若刷值后仍有add,则必定加值在刷值之后 
        return;
    }
    pushdowncha(now,L,R);
    pushdownad(now,L,R);
    int m=(R+L)>>1;
    if(j<=m) change(lc[now],L,m,i,j,d);
    else if(i>m) change(rc[now],m+1,R,i,j,d);
    else 
    {
        change(lc[now],L,m,i,m,d);
        change(rc[now],m+1,R,m+1,j,d);
    }
    pushup(now);
}
int querysum(int now,int L,int R,int i,int j)
{
    if(L>=i && R<=j) return sum[now];
    pushdowncha(now,L,R);
    pushdownad(now,L,R);

    int m=(L+R)>>1;
    if(j<=m) return querysum(lc[now],L,m,i,j);
    else if(i>m) return querysum(rc[now],m+1,R,i,j);
    else
    {
        return querysum(lc[now],L,m,i,m)+querysum(rc[now],m+1,R,m+1,j);
    }
}
int querymin(int now,int L,int R,int i,int j)
{
    if(L>=i && R<=j) return minv[now];
    pushdowncha(now,L,R);
    pushdownad(now,L,R);

    int m=(L+R)>>1;
    if(j<=m) return querymin(lc[now],L,m,i,j);
    else if(i>m) return querymin(rc[now],m+1,R,i,j);
    else
    {
        return min(querymin(lc[now],L,m,i,m),querymin(rc[now],m+1,R,m+1,j));
    }
}
int querymax(int now,int L,int R,int i,int j)
{
    if(L>=i && R<=j) return maxv[now];
    pushdowncha(now,L,R);
    pushdownad(now,L,R);

    int m=(L+R)>>1;
    if(j<=m) return querymax(lc[now],L,m,i,j);
    else if(i>m) return querymax(rc[now],m+1,R,i,j);
    else
    {
        return max(querymax(lc[now],L,m,i,m),querymax(rc[now],m+1,R,m+1,j));
    }
}
void dfs(int now,int L,int R)
{
    if(now)
    {
        printf("%d %d %d\n",L,R,sum[now]);
        int m=(L+R)>>1;
        dfs(lc[now],L,m);
        dfs(rc[now],m+1,R);
    }
}
int main()
{
//  freopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout);
    scanf("%d%d",&n,&m);
    initial();
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(rt=0,1,n);
    while(m--)
    {
        scanf("%d%d%d",&ch,&x,&y);
        if(ch==1)
        {
            scanf("%d",&d);
            update(rt,1,n,x,y,d);
        }
        else if(ch==2)
        {
            scanf("%d",&d);
            change(rt,1,n,x,y,d);
        }
        else 
        {
            printf("%d %d %d\n",querysum(rt,1,n,x,y),querymin(rt,1,n,x,y),querymax(rt,1,n,x,y));
        }
//      cout<

讲道理这题真的坑: 1.关于lazy数组add[i]和setv[i]的判断顺序和是否清零的问题,先判断setv[i]是否>=0,然后进行下放,注意此时add[lc[now]]和add[rc[now]]要清零,add[now]不用,因为在之前change()函数里面已经排除了先加再清零的可能性,所以此处add[now]不变,若它有值则下一步继续修改值。 2.v可取到0,所以在初始化setv[i]的时候记得把值赋为-1。




上面的代码中基本包含了线段树的基本运算:

//1. 初始化:
void initial(){rt=np=0;memset(rc,0,sizeof(rc));memset(lc,0,sizeof(lc));}

//2. 上传操作(后序进行):
void pushup(int now)
{
    maxv[now]=max(maxv[lc[now]],maxv[rc[now]]);
}

//3.下传操作(先序进行):
void pushdown(int now)
{
    maxv[lc[now]]+=add[now];
    add[lc[now]]+=add[now];
    maxv[rc[now]]+=add[now];
    add[rc[now]]+=add[now];
    add[now]=0;
}

//4.建立(类似二叉树):
void build(int &now,int L,int R)
{
    now=++np;
    if(L==R)
    {
        maxv[now]=a[L];
        return;
    }
    int m=(L+R)>>1;
    build(lc[now],L,m);
    build(rc[now],m+1,R);
    pushup(now);
}

//5.对区间进行操作:
//例如将区间i~j中的所以元素值加d
void update(int now,int L,int R,int i,int j,int d)//把区间[i...j]的值加d 
{
    if(L>=i && R<=j)
    {
        maxv[now]+=d;
        add[now]+=d;
        return;
    } 

    pushdown(now);
    int m=(L+R)>>1;
    if(j<=m) update(lc[now],L,m,i,j,d);
    else if(i>m) update(rc[now],m+1,R,i,j,d);
    else 
    {
        update(lc[now],L,m,i,m,d);
        update(rc[now],m+1,R,m+1,j,d);
    }
    pushup(now);
}

//6.查找i~j中的最大元素:
int query(int now,int L,int R,int i,int j)
{
    if(L>=i && R<=j)
    {
        return maxv[now];
    }

    pushdown(now);
    int m=(L+R)>>1;
    if(j<=m) return query(lc[now],L,m,i,j);
    else if(i>m) return query(rc[now],m+1,R,i,j);
    else
    {
        return max(query(lc[now],L,m,i,m),query(rc[now],m+1,R,m+1,j));
    }
}
点击复制链接 与好友分享!回本站首页
上一篇:prim算法——小根堆实现
下一篇:关键词private
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训

版权所有: 红黑联盟--致力于做实用的IT技术学习网站