精华内容
下载资源
问答
  • 线段树区间修改

    2019-09-27 16:12:36
    再补个线段树区间修改的板子 #include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f const int maxn=1e5+9; struct node{ int lazy,val,l,r; }T[maxn*4]; void pushup(int rt){...

    再补个线段树区间修改的板子

    #include<bits/stdc++.h>
    using namespace std;
    #define inf 0x3f3f3f3f
    const int maxn=1e5+9;
    struct node{
        int lazy,val,l,r;
    }T[maxn*4];
    void pushup(int rt){
        T[rt].val=T[rt<<1].val+T[rt<<1|1].val;
        return;
    }
    void pushdown(int rt){
        if(T[rt].lazy){
            T[rt<<1].lazy+=T[rt].lazy;
            T[rt<<1|1].lazy+=T[rt].lazy;
            T[rt<<1].val+=T[rt].lazy*(T[rt<<1].r-T[rt<<1].l+1);
            T[rt<<1|1].val+=T[rt].lazy*(T[rt<<1|1].r-T[rt<<1|1].l+1);
            T[rt].lazy=0;
        }
    }
    void build(int l,int r,int rt){
        T[rt].l=l;T[rt].r=r;
        if(l==r){
            cin>>T[rt].val;
            return ;
        }
        int mid=(l+r)>>1;
        build(l,mid,rt<<1);
        build(mid+1,r,rt<<1|1);
        pushup(rt);
    }
    void update(int L,int R,int l,int r,int rt,int val){
        if(l>=L&&r<=R){
            T[rt].val+=(r-l+1)*val;
            T[rt].lazy+=val;
            return;
        }
        pushdown(rt);
        int mid=(l+r)>>1;
        if(mid>=L)update(L,R,l,mid,rt<<1,val);
        if(mid<R)update(L,R,mid+1,r,rt<<1|1,val);
        pushup(rt);
    }
    int query(int L,int R,int l,int r,int rt){
        if(l>=L&&r<=R){
            return T[rt].val;
        }
        pushdown(rt);
        int mid=(r+l)>>1;
        int ans=0;
        if(mid>=L)ans+=query(L,R,l,mid,rt<<1);
        if(mid<R)ans+=query(L,R,mid+1,r,rt<<1|1);
        return ans;
    }
    int main(){
        ios::sync_with_stdio(0);
        cin.tie(0);
        int n;
        cin>>n;
        build(1,n,1);
        update(9,10,1,n,1,10);
        cout<<query(8,10,1,n,1)<<endl;
    }

     

    转载于:https://www.cnblogs.com/zookkk/p/10398120.html

    展开全文
  • 线段树 区间修改

    2019-01-16 23:57:22
    我们对于线段树区间修改你可以用一个最傻的办法循环进行单点修改(时间复杂度太高十分麻瓜)所以,我们要用一个聪明的做法** 延迟标记**(LAZY) 在限度拿书的“区间查询”指令中,每当遇到被询问区间[l,r]完全...

    我们对于线段树的区间修改你可以用一个最傻的办法循环进行单点修改(时间复杂度太高十分麻瓜)所以,我们要用一个聪明的做法** 延迟标记**(LAZY)

    在限度拿书的“区间查询”指令中,每当遇到被询问区间[l,r]完全覆盖的节点时,可以立即把该节点上存储的信息作为候选答案返回。已经有大佬证明,被询问区间[l,r]在线段树上会被分成O(logN)个小区间(节点)从而在O(logN)的时间内求出答案。

    我们在执行修改指令时,同样可以在 L<= Pl <= Pr <= R 的情况下立即返回,只不过在回溯之前向节点P增加一个标记,标识“该节点曾经被修改过,但其子节点尚未被更新”。

    如果在后续的指令中,需要从节点P向下递归,我们再检查P是否具有标记。若有标记,就根据标记信息更新P的两个子节点,同时为P的两个子节点增加标记,然后清除P的标记。

    也就是说,除了在修改指令中直接划分成的O(logN)个节点之外,对任意给点的修改都延迟到“在后续操作中递归进入他的父亲节点时”再执行。这样一来,每条查询或修改指令的时间复杂度都降低到了O(logN)。这些标记被称为“延迟标记”。延迟标记提供了线段树中从上往下传递信息的方式。这种“延迟”也是设计算法与解决问题的一个重要思路。

    附上代码

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+5;
    struct segment_tree{
    	int l,r;
    	long long sum,mark;
    }tree[maxn*4];
    long long a[maxn];
    int n,m;
    void pushup(int root){
    	tree[root].sum = tree[root<<1].sum+tree[root<<1|1].sum;
    }
    void pushdown(int root){
    	if(tree[root].mark){
    		tree[root<<1].sum += tree[root].mark*(tree[root<<1].r-tree[root<<1].l+1);
    		tree[root<<1|1].sum += tree[root].mark*(tree[root<<1|1].r-tree[root<<1|1].l+1);
    		tree[root<<1].mark += tree[root].mark;
    		tree[root<<1|1].mark += tree[root].mark;
    		tree[root].mark = 0;
    	}
    }
    void build(int L,int R,int root){
    	tree[root].l = L;
    	tree[root].r = R;
    	if(L == R){
    		tree[root].sum = a[L];
    		return;
    	}
    	int mid = (L+R)>>1;
    	build(L,mid,root<<1);
    	build(mid+1,R,root<<1|1);
    	pushup(root);
    }
    void update(int L,int R,int al,int ar,int root,long long w){
    	if(R < al || L > ar)return;
    	if(al <= L && R <= ar){
    		tree[root].sum += w*(R-L+1);
    		tree[root].mark += w;
    		return;
    	}
    	pushdown(root);
    	int mid = (L+R)>>1;
    	update(L,mid,al,ar,root<<1,w);
    	update(mid+1,R,al,ar,root<<1|1,w);
    	pushup(root);
    }
    long long query(int L,int R,int al,int ar,int root){
    	if(R < al || L > ar)return 0;
    	if(al <= L && R <= ar)return tree[root].sum;
    	pushdown(root);
    	int mid = (L+R)>>1;
    	return query(L,mid,al,ar,root<<1)+query(mid+1,R,al,ar,root<<1|1);
    }
    int main(){
    	cin>>n>>m;
    	for(int i = 1;i <= n;i++)scanf("%lld",&a[i]);
    	build(1,n,1);
    	for(int i = 1,op,x,y;i <= m;i++){
    		long long k;
    		scanf("%d",&op);
    		if(op == 1)scanf("%d%d%lld",&x,&y,&k),update(1,n,x,y,1,k);
    		if(op == 2)scanf("%d%d",&x,&y),printf("%lld\n",query(1,n,x,y,1));
    	}
    	return 0;
    }
    
    展开全文
  • C++线段树区间修改区间最大最小值模板 #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; #define ll long long #define endl "\n" const int MAX=1e5+5; struct node { ll sum,lz;//...
    #pragma GCC optimize(2)
    #include<bits/stdc++.h> 
    using namespace std;
    #define ll long long
    #define endl "\n"
    const int MAX=1e5+5;
    struct node
    {
    	ll sum,lz;//总和、lazy标记
    	ll mx,mn;//最大值max,最小值min
    }d[MAX<<2];
    ll n,m;
    ll a[MAX];
    void push_up(int p)
    {
    	d[p].sum=d[2*p].sum+d[2*p+1].sum;
    	d[p].mx=max(d[2*p].mx,d[2*p+1].mx);
    	d[p].mn=min(d[2*p].mn,d[2*p+1].mn);
    }
    void push_down(int s,int t,int mid,int p)
    {
    	if(d[p].lz==0)return ;
    		/*
    		d[2*p].sum=(t-s+1)*d[p].lz;
    		d[2*p].lz=d[p].lz;
    		d[2*p].mx=d[p].lz;
    		d[2*p].mn=d[p].lz;	
    		d[2*p+1].sum=(t-s)*d[p].lz;
    		d[2*p+1].lz=d[p].lz;
    		d[2*p+1].mx=d[p].lz;
    		d[2*p+1].mn=d[p].lz;
    		d[p].lz=0;	
    		*/
    		d[2*p].sum+=(mid-s+1)*d[p].lz;
    		d[2*p].lz+=d[p].lz;
    		d[2*p].mx+=d[p].lz;
    		d[2*p].mn+=d[p].lz;	
    		d[2*p+1].sum+=(t-mid)*d[p].lz;
    		d[2*p+1].lz+=d[p].lz;
    		d[2*p+1].mx+=d[p].lz;
    		d[2*p+1].mn+=d[p].lz;
    		d[p].lz=0;	
    }
    void build(int s,int t,int p)
    {
    	d[p].lz=0;
    	if(s==t){
    		d[p].sum=a[s];
    		d[p].mx=d[p].mn=a[s];
    		return;
    	}
    	int mid=(s+t)/2;
    	build(s,mid,2*p);
    	build(mid+1,t,2*p+1);
    	push_up(p);
    }
    
    void update(int l,int r,int c,int s,int t,int p)  //区间修改
    {
    	if(l<=s&&t<=r)
    	{
    		/*
    		d[p].sum=(t-s+1)*c;
    		d[p].lz=c;
    		d[p].mx=c;
    		d[p].mn=c;
    		*/	
    		d[p].sum+=(t-s+1)*c;
    		d[p].lz+=c;
    		d[p].mx+=c;
    		d[p].mn+=c;
    		return ;
    	}
    	int mid=(s+t)/2;
    	push_down(s,t,mid,p);
    	if(l<=mid)update(l,r,c,s,mid,2*p);
    	if(r>mid)update(l,r,c,mid+1,t,2*p+1);
    	push_up(p);
    }
    void update(int l,int r,int c)
    {
    	update(l,r,c,1,n,1);
    }
    ll getsum(int l,int r,int s,int t,int p)  //区间查询(区间求和):
    {
    	if(l<=s&&t<=r){
           return d[p].sum;
    	}
    	int mid=(s+t)/2;
    	push_down(s,t,mid,p);
    	ll sum=0;
    	if(l<=mid)sum+=getsum(l,r,s,mid,2*p);
    	if(r>mid)sum+=getsum(l,r,mid+1,t,2*p+1);
    	return sum;
    }
    ll getsum(int l,int r)
    {
    	return getsum(l,r,1,n,1);	
    }
    ll getmax(int l,int r,int s,int t,int p)  //区间查询最大值 
    {
    	if(l<=s&&t<=r){
    		return d[p].mx;
    	}
    	int mid=(s+t)/2;
    	push_down(s,t,mid,p);
    	ll ans=INT_MIN;
    	if(l<=mid)ans=max(ans,getmax(l,r,s,mid,2*p));
    	if(r>mid)ans=max(ans,getmax(l,r,mid+1,t,2*p+1));
    	return ans; 
    } 
    ll getmin(int l,int r,int s,int t,int p)  //区间查询最小值 
    {
    	if(l<=s&&t<=r){
    		return d[p].mn;
    	}
    	int mid=(s+t)/2;
    	push_down(s,t,mid,p);
    	ll ans=INT_MAX;
    	if(l<=mid)ans=min(ans,getmin(l,r,s,mid,2*p));
    	if(r>mid)ans=min(ans,getmin(l,r,mid+1,t,2*p+1));
    	return ans;
    }
    ll getmax(int l,int r)
    {
    	return getmax(l,r,1,n,1);
    }
    ll getmin(int l,int r)
    {
    	return getmin(l,r,1,n,1);
    }
    int main(){
        ios_base::sync_with_stdio(0);cin.tie(0);
    	
       return 0;
    } 
    
    
    
    展开全文
  • 线段树区间修改,区间查询模板题 #include <cstdio> #include <vector> #include <queue> #include <cstring> #include <cmath> #include <map> #include <set> #include...

    A Simple Problem with Integers
    线段树区间修改,区间查询模板题

    #include <cstdio>
    #include <vector>
    #include <queue>
    #include <cstring>
    #include <cmath>
    #include <map>
    #include <set>
    #include <string>
    #include <iostream>
    #include <algorithm>
    #include <iomanip>
    #include <stack>
    #include <queue>
    //#include<bits/stdc++.h>
    using namespace std;
    #define mod 1e9+7
    #define inf 0x3f3f3f3f
    const double PI = atan(1.0)*4.0;
    typedef long long ll;
    const int N=1e5+5;
    struct tree
    {
        ll l,r,lz,val;
    }node[4*N];
    ll a[N];
    void build(int now,int l,int r)
    {  node[now].lz=0;
        node[now].l=l;
        node[now].r=r;
        if(l==r)
        {
          node[now].val=a[l];
          return ;
        }
        ll mid=(l+r)>>1;
         build(now<<1,l,mid);
         build(now<<1|1,mid+1,r);
         node[now].val=node[now<<1].val+node[now<<1|1].val;
    
    }
    void pushdown(int now)
    { if(node[now].lz!=0)
        {node[now<<1].lz+=node[now].lz;
        node[now<<1|1].lz+=node[now].lz;
        ll mid=(node[now].l+node[now].r)>>1;
        node[now<<1].val+=node[now].lz*(mid-node[now].l+1);
        node[now<<1|1].val+=node[now].lz*(node[now].r-mid);
        node[now].lz=0;
        }
        return ;
    }
    void updata(int now,int l,int r,ll val)
    {
    
        if(node[now].l==l&&node[now].r==r)
        {
            node[now].val+=val*(r-l+1);
            node[now].lz+=val;
            return;
    
        }
    
            pushdown(now);
            ll mid=(node[now].l+node[now].r)>>1;
            if(l>mid)updata(now<<1|1,l,r,val);
            else
                if(r<=mid)updata(now<<1,l,r,val);
            else
            {
                updata(now<<1,l,mid,val);
                updata(now<<1|1,mid+1,r,val);
            }
            node[now].val=node[now<<1].val+node[now<<1|1].val;
    }
    ll query(int now,int l,int r)
    {
        if(node[now].l==l&&node[now].r==r)
        {
            return node[now].val;
        }
        pushdown(now);
         ll mid=(node[now].l+node[now].r)>>1;
         ll sum=0;
            if(l>mid)sum+=query(now<<1|1,l,r);
            else
                if(r<=mid)sum+=query(now<<1,l,r);
            else
            {
                sum+=query(now<<1,l,mid);
                sum+=query(now<<1|1,mid+1,r);
            }
    
          return sum;
    }
    int main()
    {  ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        //freopen("E:\\in.txt","r",stdin);
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        build(1,1,n);
        for(int i=1;i<=k;i++)
        {
            char p;ll x,y,z;
            cin>>p;
            if(p=='Q')
            {
                cin>>x>>y;
                ll sum=query(1,x,y);
                cout<<sum<<endl;
    
            }
            else
            {
                cin>>x>>y>>z;
                updata(1,x,y,z);
    
            }
        }
    
    
    }
    
    展开全文
  • 线段树区间修改 昨天学习了线段树这样一种极其重要的算法,在竞赛是具有广泛的运用。可以用线段树对桶等其他的算法和结构进行维护。 基本题目如下:   【题目描述】: 如题,已知一个数列,你需要进行下面两种...
  •  第一次学习线段树区间修改,没有拿到模板题而是直接拿到了变式,就当做自己的模板题了。学习了队长的写法,模板和找到的一些题解都不一样,但我觉得很好理解,结构易懂,但是就不知道如何转...
  • 洛谷P2574 XOR的艺术线段树 区间修改 区间求和询问 关于线段树的空间问题 线段树 一般来说都是要四倍空间的,当然你也可以动态开点 然后我这道题因为姿势不大妙 ,然后空间需要八倍才能过,然后一直RE 后来我...
  • 上两篇博文简单说了线段树线段树节点修改非常简单,不过区间修改有一定难度,不过也是线段树中的简单环节,接下来看一个实例。#1078 : 线段树区间修改时间限制:10000ms单点时限:1000ms内存限制:256MB描述对于小...
  • 题意: 给定N个数,初始化全部为1. 一种操作,区间修改。...简单的线段树区间修改操作应用题 具体实现见代码 #include using namespace std; const int maxn = 100000+5; struct node{ int
  • 线段树区间修改hdu1698

    2014-04-09 22:05:41
    最基本的线段树区间修改,设置延迟标记 #include #include #include #include using namespace std; const int maxn=100100; int n; struct IntevalTree { int sum[maxn]; int setv[maxn]; void build(int o,int...
  • 题目链接题目大意中文题目解决 线段树区间修改+求和查询的裸题 直接附上代码^_^ #include #include #include #include #include #include #include #include #include <se
  • ... 思路:很容易想到考查的是线段树区间修改,怎么做呢,其实只要对线段树模板的边界代码稍微修改下即可。在进行更新时,如果待更新区间覆盖了当前区间,那么这个当前区间有三种情况:还未进
  • 线段树区间修改+区间查询

    千次阅读 2017-08-04 20:45:33
    大致思路:线段树区间修改要比点修改难想一点。主要是多了一个延迟标记,目的是为了降低复杂度。但在询问的时候还需要把延迟标记逐个下放,还要更新原来的点,这就导致很难想了。 主要记住顺序: 要求区间修改 ...
  • 离散处理+线段树区间修改查询。题意:1e7的区间,按顺序对不同区间刷不同颜色(自己YY的),问最后整个区间有多少不同颜色。
  • 题目大意:维护一个长度为 N 的序列,支持区间修改、区间查询两种操作。 update on 2019.4.3 线段树分为指针式线段树和堆式线段树。指针式线段树的优点是空间较小,可以进行可持久化操作。堆式线段树的优点是可以...
  • UVA1232 - SKYLINE(线段树区间修改)

    千次阅读 2014-10-09 14:12:03
    UVA1232 - SKYLINE(线段树区间修改) 题目链接 题目大意:按照顺序盖楼,如果这个位置(当前要盖的楼覆盖范围内)要新建的楼的高度>=之前就有的最大高度,那么就+1.最后输出这个+1的总数。 解题思路:线段树...
  • poj3468线段树区间修改

    2017-02-16 14:32:17
    之前也听思雨姐姐说过也看过她写过,但自己始终没个影响,然后自己做了几天也算刚入这个门,会写一些比较基础的线段树了,之所以把这道题写下来是因为线段树的精华还是在于区间修改,也是最实用的部分。 线段树的...
  • Count the Colors 题目链接: F - Count the Colors ...就是普通的线段树区间修改,只需最后在进行一部Down操作即可,中间需要注意的就是做标记时,不能以add为0,要将其改为&gt;-1因为这个数据为0也是合法的...
  • 如果使用线段树来做,就会想到区间修改的update函数。但是这里可能会涉及到v是1或者a[j]是0的情况,所以用这种方法会超时,最多50分。 可以修改一下代码,使用点修改来做这道题。在main函数里面增加一个循环,用来...
  • 解题思路:这是一道线段树区间修改的模板题,我们理解好题意照做即可,要注意范围,利用long long来存储。 AC代码: #include<bits/stdc++.h> #define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量,a...
  • 这就是很简单的基本的线段树的基本操作,区间修改,区间查询,对区间内部信息打上laze标记,然后维护即可。 我自己做的时候太傻逼了。。。把区间修改写错了,对给定区间进行修改的时候,mid取的是节点的左右的中间...
  • 一道线段树区间修改模板题,用lazy标记来减少对子节点的更新操作,由于最后是求总区间的价值和,所以都不用写 query 了,看别人有的用 map 写的一点点代码可以过,以后研究下。  以下是代码: #include #include...
  • HDU 1698 Just a Hook(线段树区间修改

    千次阅读 2016-01-01 20:24:42
    题意: 输入一个n表示一段长度为n的区间,有n个...该题是最典型的线段树区间修改问题, 需要用到所谓的懒惰标记。 听起来挺难的,其实非常简单, 其原理如下: 因为修改很多值, 如果还是按照原来的更新方法, 每个结点
  • hdu 4902 Nice boat(线段树区间修改,输出最终序列)
  • 这是第一个入手线段树区间修改的问题,区间修改本要该一整个区间包括这些结点和子结点的值,那么会非常麻烦,这里学习到了可以使用到laze数组先记录下需要修改的次数,然后等到查询的时候一步步对子节点进行传递和...

空空如也

空空如也

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

线段树区间修改