精华内容
下载资源
问答
  • 线段树lazy标记

    2017-08-10 10:30:00
    线段树的核心就是build,query,update,其中update又分为单点更新和区间更新,在区间更新的过程中,如果一路更新到底可能会造成时间消耗很大,而后续的询问并没有用到,这样就造成了资源的浪费,lazy就在这里发挥...

    http://poj.org/problem?id=3468

    线段树的核心就是build,query,update,其中update又分为单点更新和区间更新,在区间更新的过程中,如果一路更新到底可能会造成时间消耗很大,而后续的询问并没有用到,这样就造成了资源的浪费,lazy就在这里发挥作用。

    在update的过程中如果找到了update的区间(比如2-5),那就把2-5的区间的sum值修改就好了,如果按照正常的思维,这时应该把2-5所在的子区间也全部更新,但是在后续的query中可能并没有用到以下的这些更新值,那么就先不用更新,先用lazy把它存起来。

    这样的后果就是在下次询问(query)的过程中,如果有遇到lazy值不为0,也就是有一些更新还没有完成的情况时,就需要把lazy值给释放出来,向下更新一下。

    另外在线段树中,区间更新和单点更新得区别就在于update函数,单点更新,位置只能位于一个区间内,而区间更新,这个区间极有可能位于跨度两个区间,这需要注意。

    还有写线段树时,pushup和pushdown函数是刚学的,觉得可以让程序更简单易懂,现在渐渐感觉到每个人写程序的风格都是不一样的,一个比较好的算法实现流程可能差不多,但是自己代码的模板是不一样的。

    下面的链接是我学习线段树很有力的帮助,博主代码风格简洁,整理的例题也很到位,很喜欢~虽然有些代码还是有些问题……但是适合像我这样萌新(菜鸟),hhh,分享给大家。

    http://blog.csdn.net/metalseed/article/details/8039326

    POJ3468AC代码

    #include<iostream>
    using namespace std;
    
    const int maxn = 100005;
    
    struct Tree
    {
        int left, right;
        long long sum;
        long long lazy;
    }tree[maxn*4];
    
    long long a[maxn];
    
    void pushup(int root)
    {
        tree[root].sum = tree[root * 2].sum + tree[root * 2 + 1].sum;
    }//向上更新父节点
    
    void pushdown(int root, int m)
    {
        if (tree[root].lazy)
        {
            tree[root * 2].lazy += tree[root].lazy;
            tree[root * 2 + 1].lazy += tree[root].lazy;
            tree[root * 2].sum += tree[root].lazy*(m - (m / 2));
            tree[root * 2 + 1].sum += tree[root].lazy*(m / 2);
            tree[root].lazy = 0;
        }
    }//向下更新,lazy关键
    
    void build(int root, int start, int end)
    {
        tree[root].lazy = 0;
        tree[root].left = start;
        tree[root].right = end;
    
        if (start == end)
        {
            tree[root].sum = a[start];
            return;
        }
    
        int mid = (start + end) / 2;
        build(root * 2, start, mid);
        build(root * 2 + 1, mid + 1, end);
        pushup(root);
    }
    
    void update(int root,int start,int end,int value)
    {
        if (start <= tree[root].left&&tree[root].right <= end)
        //区间的更新,这句话的意思与start == tree[root].left&&tree[root].right == end相同
        {
            tree[root].lazy += value;
            tree[root].sum += (long long)value*(tree[root].right - tree[root].left + 1);
            return;
            //lazy关键
        }
    
        /*if (tree[root].left == tree[root].right)
            return;*/
        pushdown(root, tree[root].right - tree[root].left + 1);
    
        int mid = (tree[root].right + tree[root].left) / 2;
    
        if (end <= mid)
            update(root * 2, start, end, value);
        else
            if (start >= mid + 1)
                update(root * 2 + 1, start, end, value);
            else
            {
                update(root * 2, start, mid, value);
                update(root * 2 + 1, mid + 1, end, value);
            }//区间更新与单点更新的不同就是多了这个else
        pushup(root);
    }
    
    long long query(int root,int start,int end)
    {
        if (start <= tree[root].left&&tree[root].right <= end)
            return tree[root].sum;
        pushdown(root, tree[root].right - tree[root].left + 1);
        //lazy,然后现在需要调用这个值,就要更新
        int mid= (tree[root].right + tree[root].left) / 2;
        long long reu = 0;
        if (end <= mid)
            reu += query(root * 2, start, end);
        else
            if (start >= mid + 1)
                reu += query(root * 2 + 1, start, end);
            else
                reu = query(root * 2, start, mid) + query(root * 2 + 1, mid+1, end);
        return reu;
    }
    
    int main()
    {
        int n, q;
        while (cin >> n >> q)
        {
            int i;
            for (i = 1; i <= n; i++)
                cin >> a[i];
            build(1, 1, n);
            while (q--)
            {
                char order;
                int a, b, c;
                cin >> order;
                if (order == 'Q')
                {
                    cin >> a >> b;
                    cout << query(1, a, b) << endl;
                }
                else
                    if(order=='C')
                    {
                        cin >> a >> b >> c;
                        update(1, a, b, c);
                    }
            }
        }
        return 0;
    }
    展开全文
  • 线段树lazy标记

    传送门


    题目大意:
    某个闻名中外的旅店有n个房间(由于很著名,所以n<=5W),现在有m个旅客提出了要求,1 x代表这位旅客要预定x个连续的房间,并且编号越靠前越好,2 x y代表这位旅客要退x~x+y-1这一段连续的房间…
    对于每次预定操作,输出第一个房间的编号,如果无法满足,输出0


    分析:
    (队长曾经说过…)我们先把题意简单化:
    有一段1~n的区间,初始值为1,现在有m次操作,分为两种:
    1、找到最靠前的长度为x的一段连续的1区间,并且把这段区间变为0…
    2、把x~y这段0区间变为1…
    简单来说,这道题就是一个区间修改,区间查询的题目,肯定需要数据结构,应该使用什么捏?
    线段树…
    记得某位神犇在博客里写道:做线段树不能为了做题而做,首先线段树是一种辅助结构,它是为问题而生的,因而必须具体问题具体分析…..
    好有哲理的一段话说….>_<
    写线段树,最重要的是要确定好线段树需要记录那些节点信息…
    好了,不扯了,我们还是回归此题吧>_<…
    这道题的修改操作就是最简单的修改操作,那么查询操作怎么办捏??
    既然我们要查询的和区间长度有关系,那么我们的节点信息肯定也是区间长度…
    话说我们一定至少需要3个信息:
    1、midlen,就是区间内连续最长的一段1的长度
    2、llen最长前缀1区间
    3、rlen最长后缀1区间
    话说2&3是干什么的(打酱油的>_<)
    因为我们如果要维护midlen,那么llen&rlen是必不可少滴~~
    接下来还有一个麻烦事—要求查询区间最靠前
    (⊙o⊙)…
    分类讨论吧…
    1、如果左儿子的midlen>=x那么就返回query(左儿子)
    2、如果左儿子的后缀+右儿子的前缀>=x,直接返回左儿子的后缀开始的下标
    3、若果右儿子的midlen>=x那么就返回query(右儿子)
    4、那就只能返回0了(忧桑~~>_<)


    话说,线段树每次都虐我,而且每次写线段树基本都需要好几个小时,<( ̄3 ̄)>… 忧桑啊… ̄へ ̄


    代码如下:
    (模板copyMG)

    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    const int maxn=50000+5;
    int n,m;
    struct lala{
        int l,r,llen,rlen,midlen,lazy;//lazy=1全满,lazy=0全空,lazy=-1...自己体会吧
        void changelen(){
            midlen=llen=rlen=lazy*(r-l+1);
        } 
    }tree[maxn*4];
    inline void build(int tr,int l,int r){
        tree[tr].l=l,tree[tr].r=r,tree[tr].lazy=1;
        tree[tr].changelen();
        if(l==r)
            return;
        int mid=(tree[tr].r+tree[tr].l)>>1;
        build(tr<<1,l,mid),build(tr<<1|1,mid+1,r);
    }
    inline void change(int tr,int l,int r,int val){
        if(tree[tr].l==l&&tree[tr].r==r){
            tree[tr].lazy=val,tree[tr].changelen();
            return;
        }
        int mid=(tree[tr].l+tree[tr].r)>>1;
        if(tree[tr].lazy!=-1){
            tree[tr<<1].lazy=tree[tr<<1|1].lazy=tree[tr].lazy;
            tree[tr].lazy=-1;
            tree[tr<<1].changelen(),tree[tr<<1|1].changelen();
        }
        if(l>mid)
            change(tr<<1|1,l,r,val);
        else if(r<=mid)
            change(tr<<1,l,r,val);
        else
            change(tr<<1,l,mid,val),change(tr<<1|1,mid+1,r,val);
        int tmp=max(tree[tr<<1].midlen,tree[tr<<1|1].midlen);
        tree[tr].midlen=max(tmp,tree[tr<<1].rlen+tree[tr<<1|1].llen);
        tree[tr].llen=tree[tr<<1].llen,tree[tr].rlen=tree[tr<<1|1].rlen;
        if(tree[tr<<1].midlen==tree[tr<<1].r-tree[tr<<1].l+1)
            tree[tr].llen+=tree[tr<<1|1].llen;
        if(tree[tr<<1|1].midlen==tree[tr<<1|1].r-tree[tr<<1|1].l+1)
            tree[tr].rlen+=tree[tr<<1].rlen;
    }
    inline int query(int tr,int len){
        if(tree[tr].l==tree[tr].r&&len==1)
            return tree[tr].l;
        if(tree[tr].lazy!=-1){
            tree[tr<<1].lazy=tree[tr<<1|1].lazy=tree[tr].lazy;
            tree[tr].lazy=-1;
            tree[tr<<1].changelen(),tree[tr<<1|1].changelen();
        }
        if(tree[tr<<1].midlen>=len)
            return query(tr<<1,len);
        if(tree[tr<<1].rlen+tree[tr<<1|1].llen>=len)
            return tree[tr<<1].r-tree[tr<<1].rlen+1;
        if(tree[tr<<1|1].midlen>=len)
            return query(tr<<1|1,len);
        return 0;
    } 
    signed main(void){
        scanf("%d%d",&n,&m),build(1,1,n);
        while(m--){
            int x,y,z;
            scanf("%d",&z);
            if(z==1){
                scanf("%d",&x),cout<<(y=query(1,x))<<endl;
                if(y!=0)
                    change(1,y,y+x-1,0);
            }
            else
                scanf("%d%d",&x,&y),change(1,x,x+y-1,1);
        }
        return 0;
    }

    by >_< neighthorn

    展开全文
  • 线段树lazy标记技术副题详解

    题意:

    给长度为n的序列及k(0<k<=n<=200000),m个操作p,x,y。其中(1)p==0:将x位置处的数变为y;(2)p==1:将x,y位置处的数互换。(3)p==2查询x-y位置之间连续k个数的和的最大值。

    分析:

    求连续区间的和最大,可以把区间看成一个点,这样这n-k+1个区间的最大和可以看做n-k+1个点的最大值,当更新原序列中位置x的值就相当于更新区间中x-k+1到x区间的值,然后用线段树做成段更新。成段更新要用到lazy标记,我的理解是:当更新或query的时候如果当前区间满足要求(T[k].l==s&&T[k].r==t)直接标记lazy并返回。否则将当前的lazy赋给它的子区间(父区间满足的性质子区间也满足,这是线段树中比较重要的思想),然后继续往下更新或query.注意更新后子区间的性质有变化,要向上更新父区间(这样才能保证父区间满足的性质子区间也满足)。

    代码:

    <pre name="code" class="cpp">//poj 4047
    //sep9
    #include <iostream>
    using namespace std;
    const int maxN=200012;
    struct Node
    {
    	int l,r,maxx,lazy;
    }T[maxN*4];
    int n,m,k;
    int v[maxN],b[maxN];
    int build(int l,int r,int k)
    {
    	int mid=(l+r)>>1;
    	T[k].l=l;
    	T[k].r=r;
    	T[k].lazy=0;
    	if(l==r){
    		T[k].maxx=b[l];
    		return T[k].maxx;
    	}
    	int x=build(l,mid,2*k);
    	int y=build(mid+1,r,2*k+1);
    	T[k].maxx=max(x,y);
    	return T[k].maxx;
    }
    int query(int s,int t,int k)
    {
    	if(T[k].l==s&&T[k].r==t)
    		return T[k].maxx+T[k].lazy;
    	T[2*k].lazy+=T[k].lazy;
    	T[2*k+1].lazy+=T[k].lazy;
    	T[k].maxx+=T[k].lazy;
    	T[k].lazy=0;
    	if(t<=T[2*k].r)
    		return query(s,t,2*k);
    	else if(s>T[2*k].r)
    		return query(s,t,2*k+1);
    	else{
    		int x=query(s,T[2*k].r,2*k);
    		int y=query(T[2*k+1].l,t,2*k+1);
    		return max(x,y);
    	} 
    }
    
    void update(int s,int t,int k,int c)
    {
    	if(T[k].l==s&&T[k].r==t){
    		T[k].lazy+=c;
    		return ;
    	}
    	T[2*k].lazy+=T[k].lazy;
    	T[2*k+1].lazy+=T[k].lazy;
    	T[k].maxx+=T[k].lazy;
    	T[k].lazy=0;
    	if(t<=T[2*k].r)
    		update(s,t,2*k,c);
    	else if(s>T[2*k].r)
    		update(s,t,2*k+1,c);
    	else{
    		update(s,T[2*k].r,2*k,c);
    		update(T[2*k+1].l,t,2*k+1,c);
    	} 		
    	T[k].maxx=max(T[2*k].maxx+T[2*k].lazy,T[2*k+1].maxx+T[2*k+1].lazy); 
    }
    
    int main()
    {
    	int cases;
    	scanf("%d",&cases);
    	while(cases--){
    		scanf("%d%d%d",&n,&m,&k);
    		memset(b,0,sizeof(b));
    		for(int i=1;i<=n;++i)
    			scanf("%d",&v[i]);
    		for(int i=1;i<=k;++i)
    			b[1]+=v[i];
    		for(int i=2;i<=n-k+1;++i)
    			b[i]=b[i-1]-v[i-1]+v[i+k-1];	
    		build(1,n-k+1,1);
    		while(m--){
    			int q,x,y;
    			scanf("%d%d%d",&q,&x,&y);
    			if(q==0){
    				update(max(1,x-k+1),min(n-k+1,x),1,y-v[x]);
    				v[x]=y;
    			}else if(q==1){
    				update(max(1,x-k+1),min(n-k+1,x),1,v[y]-v[x]);
    				update(max(1,y-k+1),min(n-k+1,y),1,v[x]-v[y]);
    				swap(v[x],v[y]);
    			}else
    				printf("%d\n",query(x,y-k+1,1));	
    		}
    	}
    	return 0;	
    } 


     
    

    展开全文
  • 线段树lazy标记优化

    2020-03-20 15:20:35
    线段树:优雅的分块暴力 区间修改(单点修改),区间查询 POJ3468 #include<iostream> #include<cstdio> #include<cstring> #include<string> const int maxn = 1e6+10; using namespace ...
    线段树:优雅的分块暴力

    区间修改(单点修改),区间查询

    POJ3468
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    const int maxn = 1e6+10;
    using namespace std;
    typedef long long ll;
    
    ll aa[maxn], ans;
    struct node{
        ll a, b, len;
        ll sum;
        ll lazy;
    };
    
    node tree[maxn*4];
    void pushup(int rt){tree[rt].sum = tree[rt<<1].sum+tree[rt<<1|1].sum;return;}
    int cnt  =1;
    
    void build(ll a, ll b, int num){
        cnt = max(num, cnt);
    
            tree[num].a = a;
            tree[num].b = b;
            tree[num].lazy = 0;
            tree[num].len = (b-a+1);
            if(a == b){tree[num].sum = aa[a];}
            else{
            int mid = (a+b)>>1;
            build(a, mid, num<<1);
            build(mid+1, b, (num<<1)+1);
            pushup(num);
    
            }
    }
    
    void pushdown(int rt){
        if(tree[rt].lazy){
            tree[rt<<1].lazy+=tree[rt].lazy;
            tree[rt<<1|1].lazy+=tree[rt].lazy;
    
            tree[rt<<1].sum+=tree[rt<<1].len*tree[rt].lazy;
            tree[rt<<1|1].sum+=tree[rt<<1|1].len*tree[rt].lazy;
            tree[rt].lazy = 0;
        }
    }
    
    /*345各加3,+6不是+9???*/
    void query(ll a, ll b, int num){
        if(a>tree[num].b||tree[num].a>b) return;
        if(tree[num].a>=a&&tree[num].b<=b){
            pushdown(num);
            ans+=tree[num].sum;
            return;
        }
        pushdown(num);
    
        query(a, b, num<<1|1);
        query(a, b, (num<<1));
    
        pushup(num);
    }
    
    void add(ll a, ll b, ll val, int num){
        if(a>tree[num].b||tree[num].a>b) return;
        if(tree[num].a>=a&&tree[num].b<=b){
            tree[num].sum+=tree[num].len*val;
            tree[num].lazy+=val;
            return ;
        }
        pushdown(num);  //向下更新时先pushdown
    
        add(a, b, val, num<<1);
        add(a, b, val, num<<1|1);
        pushup(num); //更新
    }
    
    int main(){
        int n, m;
        cin>>n>>m;
        for(int i = 1; i <= n; i++){
            scanf("%lld", &aa[i]);
        }
    
        build(1, n, 1);//从一开始建树
    
        /*for(int i = 1; i <= cnt; i++){
            printf("%d  ;%d  %d :sum : %d\n", i, tree[i].a, tree[i].b, tree[i].sum);
        }*/
        ll x, y, z;
        char ch;
        for(int i = 0; i < m; i++){
            //scanf("%c %d%d\n", &ch, &x, &y);
            cin>>ch>>x>>y;
            if(ch == 'Q'){
                ans = 0;
                query(x, y, 1);
                printf("%lld\n", ans);
                //getchar();
            }
            else{
                scanf("%lld\n", &z);
                add(x, y, z, 1);
               /* for(int i = 1; i <= cnt; i++){
            printf("%d  ;%d  %d :sum : %d\n", i, tree[i].a, tree[i].b, tree[i].sum);
        }*/
            }
        }
    
        return 0;
    }
    
    
    展开全文
  • 线段树lazy标记永久化

    2017-07-14 09:07:51
    1、为什么要有这玩意:当我们用可持久化的数据结构lasy标志可能不能下传,或者用动态开点线段树时如果标记下传会造成无用空间。 2、实现: 以下内容纯属自己YY。 最主要思路,标记不下传,查询时经过一个节点就加上...
  • 最近花近两个星期敲线(da)段(you)树(xi)。其实花了一节课磕磕巴巴...线段树练习4 给你N个数,有两种操作 1:给区间[a,b]内的所有数都增加X 2:询问区间[a,b]能被7整除的个数 区间修改区间查询 结构体里添加
  • 如果在题目中使某个区间所有元素的对应值*x或+-x,直接用线段树对每个元素进行计算,时间复杂度升高为nlogn,而用lazy标记可以减小时间复杂度。 假设需要对某区间+num; void pushup(int p) {//数值向上传递 dat...
  • 线段树lazy标记1血题

    2016-04-19 23:33:11
    第一个写对的线段树
  • 这道题属实是线段树的道比刷题,又加又乘的,当然还可能会有乘除,阶乘等等可能的情况。 对于这道题,主要的一个就是怎么记录lazy标记,首先的话一个数组是肯定不行的,设乘的为lazy,加的为add。 每次我们更新时...
  • pushdown的时候一定要注意乘的是上次的lazy不是本次的!!!!! #include  #include  #include #define ll long long #define N 100010 using namespace std; struct node { ll l,r,len,lz,val; } c[5*N]; void...
  • 线段树lazy标记??Hdu4902

    2014-07-31 22:08:22
    Nice boat Time Limit: 30000/15000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 335 Accepted Submission(s): 159 Problem Description ...There is an ol
  • program df; type point=record c,a,b,d:longint; end; var i,j,n,m,x,y,k,t,g,h:longint; up,down,ans,z:int64;...f:array[0..500000] of point;...a:array[0..500000] of longint;...c:array[0..500000] of int64
  • 懒得标记的第一题,写一下就能理解这个奥妙,能使线段树更加的优化 #include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; #define lson l , m , rt &lt;&lt; 1 #...
  • //覆盖的线段颜色 cov[p]=0; } } void Update(int p,int l,int r,int x,int y,int cr) //cr为颜色编号 { if(x<=l&&y>=r) { cov[p]=cr; return; } Pushdown(p); int mid=(l+r)/2; if(x) Update(p,l,mid,x...
  • lazy[rt]=lazy[rt];lazy[rt|1]=lazy[rt]; sum[rt]=lazy[rt]*(mid-l+1); sum[rt|1]=lazy[rt]*(r-mid); lazy[rt]=0; } void build(int l,int r,int rt){ sum[rt]=lazy[rt]=0; if(l==r){ sum[rt]=1; return; }...
  • #include #include using namespace std; const int maxn=100002; int tree[maxn],cov[maxn]; void Pushup(int p) { tree[p]=tree[p]|tree[p|1];//通过或运算符来计数 } void Pushdown(int p) ... if(cov
  • 明明就是个裸的线段树还不让我一遍过。 tmd标记每次要取反而不能直接标记1或者0。。因为有可能传递下来的标记和修改的标记重叠了。。#include #include #include #include #define fo(i,a,b) for(int i=a;i;i++) #...
  • 不用lazy标记会超时 #include #include<iostream>> #include #define N 100050 using namespace std; typedef long long int ll; struct Node { int left,right; ll sum; ll mark; }tree[N]; int num[N]; ...
  • 值得注意的是,这题其实不需要打lazy标记,直接维护维护前缀前缀和即可。 事实上,因为满足区间减法,你也可以用树状数组写。并且还有二维进阶题目等着你。 #include #include #include #include ...
  • tree[root*2+1].lazy+=tree[root].lazy; tree[root].lazy=0; } } void updata(ll l,ll r,ll add,ll root) { tree[root].sum+=(r-l+1)*add; if(tree[root].l==l&&tree[root].r==r) { tree[root].lazy+=add; ...
  • 否则的话我们直接对当前区间打上标记后返回。 #include #include #include #include using namespace std; #define LL long long #define rep(i,j,k) for(int i=j;i;i++) #define sca(x) scanf("%d",&x); #...
  • 题目意思很好懂 就是求解一段区间不同的数字的个数 由于数字的种类小于30 所以可以用位运算来代表不同的种类 纠结了好久开始一直TLE后来才改的位运算 然后用到的就是区间的覆盖问题了 #include ...
  • 现在写出来了但是被卡了一个点,有一个点超时只有95分,老师说这一题用线段树只能写到95了,于是把这种做法也发一下 program mys; type ab= record l,r,w,c:longint; end ; var i,j,k,m,n,t,b,c,tot,...
  • http://poj.org/problem?id=3468 有了上一题的基础 这题就是小菜了 #include #include #include #define MAX 100010 using namespace std; typedef struct { long long l; long long r;... long l
  • 也就转化为线段树查询区间和,区间修改。 区间修改用lazy标志即可。 AC代码 #include using namespace std; typedef long long ll; #define lson l , m , rt   #define rson m + 1 , r , rt | 1 ...
  • 线段树lazy标记

    2018-06-14 17:56:35
    题目最多给到10万个操作,简单的线段树会超时,需要用到lazy标记。在区间修改时,如果每次都更新到叶子节点会非常耗费时间,为节省时间,当某次更新的区间与当前更新的区间一致的话,则本次更新仅更新该节点,并将该...
  • 线段树lazy标记

    2018-08-06 11:41:03
    线段树区间修改与区间查询,如果我们对区间中的每一个值依次进行修改,那么最终结果一定是tle。因此我们在这里加入lazy标记lazy标记,对于区间更新而言,如果我首次更新这段区域,我就先将需要更新的值加到lazy...
  • 线段树 + lazy标记

    2021-04-08 18:48:45
    我先将如何通过线段树解决区间最大值问题来表示一个线段树 线段树的核心思想时通过一个点来代表一个区间的信息,如下图(圆圈里面代表的时序号,下面是区间) 我们将序号存入一维数组中,然后用序号代表下面区间的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,055
精华内容 2,422
关键字:

线段树lazy标记