精华内容
下载资源
问答
  • 线段树区间修改
    2021-05-08 19:59:08

    区间修改区间查询里面用到了一个lazy tag方法

    具体的意思就是: 要修改某区间(L,R)的值时,不修改到底,而是修改到L<=begin&&R>=end时,直接对begin到end区间的和进行修改,修改后在次节点做一个标记add[node]=x(x为修改值),如果add[node]不为零,说明我并没有将此节点的更改向下延伸到叶子节点。至于什么时候向下更新到叶子结点,则是到区间查询查询到此节点时进行更新。如果有重复的区间修改到此节点,把此节点得影响全部积攒到add数组。

    #include <iostream>
    #include <cmath>
    #include <algorithm>
    #include <stdio.h>
    #include <cstring>
    #define ll long long
    using namespace std;
    
    ll N,Q;
    
    ll a[100005],Tree[400005];
    ll add[400005];//lazytag核心数组
    void push_down(int node,int len){//更新函数
    	if(add[node]){
    		add[node<<1]+=add[node];
    		add[node<<1|1]+=add[node];
    		Tree[node<<1]+=(len-(len>>1))*add[node];
    		Tree[node<<1|1]+=(len>>1)*add[node];
    		add[node]=0;
    	}
    }
    
    
    void build(int node,int begin,int end){
    	if(begin==end){
    		Tree[node]=a[begin];
    		return;
    	}
    	int mid=(begin+end)/2;
    	build(node*2,begin,mid);
    	build(node*2+1,mid+1,end);
    	Tree[node]=Tree[node*2]+Tree[node*2+1];
    }
    
    void update(int node,int begin,int end,int L,int R,ll x){
    	if(L<=begin&&R>=end){
    		Tree[node]+=(end-begin+1)*x;
    		add[node]+=x;
    		return;
    	}
    	push_down(node,end-begin+1);
    	int mid=(begin+end)/2;
    	if(L<=mid){
    		update(node*2,begin,mid,L,R,x);
    	}
    	if(R>mid){
    		update(node*2+1,mid+1,end,L,R,x);
    	}
    	Tree[node]=Tree[node*2]+Tree[node*2+1];
    }
    
    ll query(int node,int begin,int end,int L,int R){
    	if(L<=begin&&R>=end){
    		return Tree[node];
    	}
    	push_down(node,end-begin+1);
    	int mid=(begin+end)/2;
    	ll sum1=0,sum2=0;
    	if(L<=mid){
    		sum1=query(node*2,begin,mid,L,R);
    	}
    	if(R>mid){
    		sum2=query(node*2+1,mid+1,end,L,R);
    	}
    	return sum1+sum2;
    }
    
    
    
    int main(){
    	while(cin>>N>>Q){
    		memset(Tree,0,sizeof(Tree));
    		memset(add,0,sizeof(add));
    		for(int i=1;i<=N;i++){
    			scanf("%lld",&a[i]);
    		}
    		build(1,1,N);
    		char C;
    		while(Q--){
    			getchar();
    			scanf("%c",&C);
    			if(C=='C'){
    				int a,b;ll c;
    				scanf("%d%d%lld",&a,&b,&c);
    				update(1,1,N,a,b,c);
    			}
    			else if(C=='Q'){
    				int a,b;
    				scanf("%d%d",&a,&b);
    				printf("%lld\n",query(1,1,N,a,b));
    			}	
    		}
    	}
    	return 0;
    }

     

    更多相关内容
  • 维护序列的二叉树 树上每个点对应序列上一段连续的区间 ls/rs:k的左/右儿子 Mid=(l+r)/2 若点x对应[l,r],则ls对应[l,mid],rs对应...当我们在查询和修改中遇到一个有懒标记的点k时,由于其子树内部的值还未被更

    维护序列的二叉树

    树上每个点对应序列上一段连续的区间

    ls/rs:k的左/右儿子

    Mid=(l+r)/2

    若点x对应[l,r],则ls对应[l,mid],rs对应[mid+1,r]

    根节点对应整个序列[1,n]

    叶节点对应的区间为[l,l],即序列上一个点

    1.区间加法

    考虑用lazy数组标记,当我们需要对点k所对应的区间加v时,我们不递归k的左右子树更新其内部值,而是选择lazy[k]+=v,代表这段区间已经加过v了。当我们在查询和修改中遇到一个有懒标记的点k时,由于其子树内部的值还未被更新,我们需要将懒标记的影响下传到子树中,并将懒标记清空。

    void add(int k,int l,int r,int v){
    	s[k] += (r-l+1)*v;
    	lazy[k] += v;
    	return;
    }
    void pushdown(int k,int l,int r){
    	add(ls,l,mid,lazy[k]);
    	add(rs,mid+1,r,lazy[k]);
    	lazy[k] = 0;
    	return;
    }

    2.区间乘法

    用两个lazy数组,表示加和成,其余的部分一样

    void add(int k,int l,int r,int v1,int v2){//表示先乘v2再加v1
    	s[k] = (s[k]*v2 + v1*(r-l+1))%mod;
    	lazy1[k] = (lazy1[k]*v2 + v1)%mod;
    	lazy2[k] = (lazy2[k]*v2)%mod;
    	return;
    }
    void pushdown(int k,int l,int r){
    	add(ls,l,mid,lazy1[k],lazy2[k]);
    	add(rs,mid+1,r,lazy1[k],lazy2[k]);
    	lazy1[k] = 0;
    	lazy2[k] = 1; //注意要清成1
    	return;
    }

    最后放上有加法和乘法的总代码

    #include<bits/stdc++.h>
    #define int long long
    #define ll long long
    #define ls (k<<1)
    #define rs (k<<1|1)
    #define mid (l+r>>1)
    using namespace std;
    inline int read(){
    	int x=0,f=1;char ch=getchar();
    	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
    	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48) ; ch=getchar();}
    	return x*f;
    }
    const int M = 500010;
    int n,m,mod;
    int s[M*4],lazy1[M*4],lazy2[M],a[M];//jia cheng
    void build(int k,int l,int r){
    	lazy2[k] = 1;
    	if(l == r){s[k] = a[l];return;}
    	build(ls,l,mid);
    	build(rs,mid+1,r);
    	s[k] = (s[ls]+s[rs])%mod;
    	return;
    }
    void add(int k,int l,int r,int v1,int v2){
    	s[k] = (s[k]*v2 + v1*(r-l+1))%mod;
    	lazy1[k] = (lazy1[k]*v2 + v1)%mod;
    	lazy2[k] = (lazy2[k]*v2)%mod;
    	return;
    }
    void pushdown(int k,int l,int r){
    	add(ls,l,mid,lazy1[k],lazy2[k]);
    	add(rs,mid+1,r,lazy1[k],lazy2[k]);
    	lazy1[k] = 0;
    	lazy2[k] = 1;
    	return;
    }
    void pushup(int k,int l,int r){s[k] = (s[ls] + s[rs])%mod;}
    int query(int k,int l,int r,int x,int y){
    	if(x<=l && y>=r) return s[k];
    	pushdown(k,l,r);
    	int res = 0;
    	if(x<=mid) res += query(ls,l,mid,x,y);
    	if(y>mid) res += query(rs,mid+1,r,x,y);
    	return res%mod;
    }
    void modify(int k,int l,int r,int x,int y,int v1,int v2){
    	if(x<=l && y>=r){add(k,l,r,v1,v2);return;}
    	pushdown(k,l,r);
    	if(x<=mid) modify(ls,l,mid,x,y,v1,v2);
    	if(y>mid) modify(rs,mid+1,r,x,y,v1,v2);
    	pushup(k,l,r);
    	return;
    }
    signed main(){
    	n=read();m=read();mod=read();
    	for(register int i(1) ; i<=n ; i=-~i) a[i] = read();
    	build(1,1,n);
    	for(register int i(1) ; i<=m ; i=-~i){
    		int op;
    		op=read();
    		if(op == 1){
    			int x,y,k;
    			x=read();y=read();k=read();
    			modify(1,1,n,x,y,0,k);
    		}
    		if(op == 2){
    			int x,y,k;
    			x=read();y=read();k=read();
    			modify(1,1,n,x,y,k,1);
    		}
    		if(op == 3){
    			int x,y;
    			x=read();y=read();
    			printf("%lld\n",query(1,1,n,x,y)%mod);
    		}
    	}
    	return 0;
    }

     

     

    展开全文
  • 给定一个长度为N的数列A,以及M条指令,每条指令可能是以下两种之一: 1、“C l r d”,表示把 A[l],A[l+1],…,A[r] 都加上 d。 2、“Q l r”,表示询问 数列中第 l~r 个数的和。 对于每个询问,输出一个整数表示...
  • 线段树的区间修改 本题如果用单点修改的思想会T,所以需要引入一个数组 l a z y lazy lazy , 优秀程序员必备 l a z y lazy lazy定义 此为偷懒 该数组意在储存 t r e e tree tree 数组的所有区间操作 就是将原先每个...

    线段树的区间修改

    本题如果用单点修改的思想会T,所以需要引入一个数组 l a z y lazy lazy 优秀程序员必备

    l a z y lazy lazy定义

    此为偷懒
    该数组意在储存 t r e e tree tree 数组的所有区间操作
    就是将原先每个子节点的操作先集合到一个节点上,等到更新到某一个子区间时,用 p u s h − d o w n push-down pushdown 函数将父节点的 l a z y lazy lazy 下发到该节点上 。(左右子节点都需要下发)
    t r e e tree tree 数组则继续进行原先的操作 。

    e g . eg. eg.

    若题目要求区间 [ i , j ] [i,j] [i,j] 的每一个数加上 v a l val val

    lazy[pos] += val;
    tree[pos] += val * (r - l + 1);
    

    ————————
    l a z y 转 移 函 数 lazy转移函数 lazy

    inline void js(int pos, int l, int r, int k)
    {
        lazy[pos] += k;
        tree[pos] += k * (r - l + 1);
    }
    inline void push_down(int pos, int l, int r)
    {
        int mid = (l + r) >> 1;
        js(lw, l, mid, lazy[pos]);
        js(rw, mid + 1, r, lazy[pos]);
        lazy[pos] = 0;
    }//lazy转移函数
    

    区 间 修 改 函 数 区间修改函数

    inline void update(int pos, int left, int right, int l, int r, int val)
    {
        if (left <= l && r <= right)//判断是否为于目标区间之内
        {
            lazy[pos] += val;
            tree[pos] += val * (r - l + 1);
            return;
        }
        push_down(pos, l, r);
        int mid = (l + r) >> 1;
        if (left <= mid)
            update(lw, left, right, l, mid, val);
        if (right > mid)
            update(rw, left, right, mid + 1, r, val);
        push_up(pos);
    }//区间修改函数
    

    区间查询请参考区间查询

    模板

    #include <bits/stdc++.h>
    using namespace std;
    #define lw pos << 1
    #define rw pos << 1 | 1
    
    #define int long long
    
    const int maxn = 1e6 + 5;
    int n, m;
    int tree[maxn << 2], lazy[maxn << 2];
    inline void push_up(int pos)
    {
        tree[pos] = tree[lw] + tree[rw];
    }
    inline void js(int pos, int l, int r, int k)
    {
        lazy[pos] += k;
        tree[pos] += k * (r - l + 1);
    }
    inline void push_down(int pos, int l, int r)
    {
        int mid = (l + r) >> 1;
        js(lw, l, mid, lazy[pos]);
        js(rw, mid + 1, r, lazy[pos]);
        lazy[pos] = 0;
    }
    inline void build(int pos, int l, int r)
    {
        lazy[pos] = 0;
        if (l == r)
        {
            cin >> tree[pos];
            return;
        }
        int mid = (l + r) >> 1;
        build(lw, l, mid);
        build(rw, mid + 1, r);
        push_up(pos);
    }
    inline void update(int pos, int left, int right, int l, int r, int val)
    {
        if (left <= l && r <= right)
        {
            lazy[pos] += val;
            tree[pos] += val * (r - l + 1);
            return;
        }
        push_down(pos, l, r);
        int mid = (l + r) >> 1;
        if (left <= mid)
            update(lw, left, right, l, mid, val);
        if (right > mid)
            update(rw, left, right, mid + 1, r, val);
        push_up(pos);
    }
    inline int query(int pos, int L, int R, int l, int r)
    {
    
        if (L <= l && r <= R)
        {
            return tree[pos];
        }
    
        int mid = (l + r) >> 1;
        int sum = 0;
        push_down(pos, l, r);
    
        if (L <= mid)
        {
            sum += query(lw, L, R, l, mid);
        }
        if (R > mid)
        {
            sum += query(rw, L, R, mid + 1, r);
        }
    
        return sum;
    }
    signed main()
    {
        cin >> n >> m;
        build(1, 1, n);
        for (int i = 1, q, q1, q2, q3; i <= m; i++)
        {
            cin >> q >> q1 >> q2;
            if (q == 1)
            {
                cin >> q3;
                update(1, q1, q2, 1, n, q3);
            }
            else if (q == 2)
            {
                cout << query(1, q1, q2, 1, n) << endl;
            }
        }
        return 0;
    }
    
    展开全文
  • 题意:给一个数组,进行区间修改和求和操作。 线段树区间修改,直接放线段树咬,但是很多的细节需要注意。 千万不能upate(L,mid,2*k,val);update(mid+1,R,2*k+1,val).会改变目标区间的值。 比如n=10,修改区间(3...

    题意:给一个数组,进行区间修改和求和操作。

    线段树区间修改,直接放线段树咬,但是很多的细节需要注意。

    千万不能upate(L,mid,2*k,val);update(mid+1,R,2*k+1,val).会改变目标区间的值。

    比如n=10,修改区间(3,6)

    1,左边:目标区间变为(3,5),树的区间为(1,5)

        右边:目标区间变为(6,6)树的区间变为(6,10)

    2, 左边:①左边:目标区间(3,3)树的区间(1,3)②右边:目标区间(4,5)树的区间(4,5)

    (到目前为止都很正常,接下来右边的就不对了)

    右边:①左边:目标区间(6,8)(这个时候就不对了,因为原来的目标区间是(3,6)而现在到了8了)。树的区间(6,8)

    ②右边:没有

    #pragma warning(disable:4996)
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<climits>
    #include<algorithm>
    #include<vector>
    #include<cmath>
    #include<queue>
    #include<set>
    using namespace std;
    typedef long long ll;
    const int MAXN = 100005;
    struct node
    {
    	ll sum, lz, l, r;
    };
    node tree[MAXN<<2];
    //建立线段树,没有坑,没有细节
    void build(ll L, ll R, ll k)
    {
    	tree[k].l = L;tree[k].r = R;
    	if (L == R)
    	{
    		scanf("%lld", &tree[k].sum);
    		tree[k].lz = 0;
    		return;
    	}
    	ll mid = (L + R) / 2;
    	build(L, mid, 2 * k);
    	build(mid + 1, R, 2 * k + 1);
    	tree[k].sum = tree[2 * k].sum + tree[2 * k + 1].sum;
    }
    //要加上父亲结点的lazy标记,左右区间的元素个数要数对
    void pushdown(ll k)
    {
    	if (tree[k].lz)
    	{
    		tree[2*k].lz+=tree[k].lz;
    		tree[2 * k + 1].lz += tree[k].lz;
    		ll mid = (tree[k].l + tree[k].r) / 2;
    		//左区间元素个数mid-tree[2*k].l+1
    		tree[2 * k].sum += (mid - tree[2 * k].l + 1) * tree[k].lz;
    		//右区间tree[2*k+1].r-mid
    		tree[2 * k + 1].sum += (tree[2 * k + 1].r - mid) * tree[k].lz;
    		tree[k].lz = 0;
    	}
    }
    void update(ll L, ll R, ll k, ll val)
    {
    	if (tree[k].l >= L && tree[k].r <= R)
    	{
    		tree[k].sum += (tree[k].r - tree[k].l + 1) * val;
    		tree[k].lz += val;
    		return;
    	}
    	pushdown(k);
    	ll mid = (tree[k].l + tree[k].r) / 2; 
    	//不能是upate(L,mid,2*k,val);update(mid+1,R,2*k+1,val)会出错
    	//看起来好像差不多,但是这样做,会使(L,R)改变
    	if (L <= mid)update(L, R, 2 * k, val);
    	if(R>mid) update(L, R, 2 * k + 1, val);
    	tree[k].sum = tree[2 * k].sum + tree[2 * k + 1].sum;
    }
    ll query(ll L, ll R, ll k)
    {
    	if (tree[k].l >= L && tree[k].r <= R)
    	{
    		return tree[k].sum;
    	}
    	//记得pushdown,不然会少算很多
    	pushdown(k);
    	ll ans = 0, mid;
    	mid = (tree[k].l + tree[k].r) / 2;
    	if (L <= mid)ans += query(L, R, 2 * k);
    	if (R > mid)ans += query(L, R, 2 * k + 1);
    	return ans;
    }
    //debug的函数,查看每一个数字的值
    /*void find(int k)
    {
    	if (tree[k].l == tree[k].r)
    	{
    		printf("%lld ", tree[k].sum);
    		return;
    	}
    	pushdown(k);
    	int mid = (tree[k].l + tree[k].r) / 2;
    	find(2 * k);
    	find(2 * k + 1);
    	//printf("\n");
    }*/
    int main()
    {
    	ll n, m, i, j;
    	char s[2];
    	while (scanf("%lld%lld", &n, &m) == 2)
    	{
    		build(1, n, 1);
    		ll t1, t2, t3,ans;
    		while (m--)
    		{
    			scanf("%s", s);
    			if (s[0] == 'Q')	
    			{
    				scanf("%lld%lld", &t1, &t2);
    				ans = query(t1, t2, 1);
    				printf("%lld\n", ans);
    			}
    			else
    			{
    				scanf("%lld%lld%lld", &t1, &t2, &t3);
    				update(t1, t2, 1, t3);
    			}
    		}
    		//find(1);
    	}
    	return 0;
    }
    

     

    展开全文
  • 树状数组:区间修改,区间查询树状数组 :区间修改,区间查询树状数组:区间修改,区间查询 一、树状数组是什么? 新手请参考 ————》》————》》————》》 树状数组 数据结构详解与模板(可能是最详细的了)...
  • 那么每次区间修改的复杂度是O(log2n),一共有Q次操作,总复杂度是O(nlog2n)。做lazy操作的子区间,需要记录状态(tag),在下面的代码中使用add[]实现。 #include<stdio.h> using namespace std; const int maxn...
  • 一、线段树简介 线段树本质上是一个二叉树,除了叶子节点之外,其余的父亲节点都有两个儿子;学过数据结构中的二叉树都知道,儿子节点与父亲节点下标的关系;(设父亲节点下标为p,则...线段树的基本操作有:单点修改,区间修改
  • 区间修改,单点查询四. 区间修改,区间查询 前言 最近在复习算法的时候,刷到了一些针对于区间问题,所以在此记录。 注:此文章默认会使用树状数组,不会的可以参考这一篇文章:树状数组详解 一. 单点修改,单点...
  • 区间修改和单点查询 引入(洛谷 P3372 【模板】线段树 1) 已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上 kkk。 2.求出某区间每一个数的和。 这是线段树的模板题,然而我们要用树状数组去做它!...
  • 它功能强大,支持区间求和,区间最大值,区间修改,单点修改等操作。 线段树的思想和分治思想很相像。 线段树的每一个节点都储存着一段区间[L…R]的信息,其中叶子节点L=R。它的大致思想是:将一段大区间平均地...
  • 树状数组的区间查询和区间修改的思考【不包含一维树状数组的基本知识】区间查询与修改的总体思想(以入门的角度理解) 区间查询与修改的总体思想(以入门的角度理解) 树状数组单纯地最多只设计区间影响,没有涉及区间...
  • 树状数组之区间修改,区间查询 原理 我们先开俩数组; 原数组:a [i], 每一个元素的值 差分数组:b [i], 下标 i 的元素存放 a[i]-a[i-1] 的差值,b[1]=a[1] 我们可以得到下面的公式: 于是,我们得到了一个 重要公式...
  • 洛谷 P2048 主席树+区间修改

    千次阅读 2018-10-21 23:02:21
    建立主席树对于第i颗线段树来说,区间(l,r)表示左端点是l-r的点,右端点是i的区间情况,对此第i颗线段树由i-1颗转移过来时只需要对当前线段树进行(1,i)区间都加上a[i]的值,那么这个操作就可以做区间更新,之后就是维护...
  • 区间修改+区间查询

    千次阅读 2018-07-23 11:13:46
    典型的区间修改+区间查询 题目如下: 链接:https://www.nowcoder.com/acm/contest/135/I 来源:牛客网   题目描述  Apojacsleam喜欢数组。  他现在有一个n个元素的数组a,而他要对a[L]-a[R]进行M次操作: ...
  • C++ 区间修改

    2020-06-05 15:13:41
    c++的区间修改 题目描述: 有一个 N× M 的矩阵 A, 操作 add(x1,y1,x2,y2 , k)表示对矩阵 A 的(x1,y1) 到(x2,y2)区域内的每个 数都加上 k。 有 P 个 add 操作, 输出 P 个 add 操作后的矩阵 A。 输入格式: 第一...
  • 2.区间修改,单点查询 3.区间修改,区间查询 区间修改,区间查询 Description 给定数列 a[1],a[2],…,a[n],你需要依次进行q个操作,操作有两类: 1 l r x:给定l,r,x,对于所有的i∈[l,r],将a[i]加上x(换言之,将...
  • 最一般树状数组能做到的操作...那么,如何同时做到区间求和,区间修改呢? 有人可能会说了,如果是区间求和区间修改的话,直接写线段树不就好了吗? 但是,从代码长度来看(dalao请无视),显然使用树状数组在考...
  • 线段树是一种二叉搜索树,线段树将一段区间划分为若干个单位区间,每一个结点对应着原线段区间的一段,线段树维护的问题需要满足区间加法 例题:https://www.luogu.com.cn/problem/P3372 线段树的建树 typedef ...
  • 区间修改:O(logn) #include <stdio.h> #include <stdlib.h> /* 线段树节点 * l:节点左区间 * r:节点右区间 * cnt:节点的长度 * sum:区间和 * lazy:懒标记 */ struct node { int l, r, cnt; long ...
  • 如何区间修改: 首先,我们不能进行线段树上的pushdown操作。因为这样做会让公共节点的值被修改。导致其他版本的线段树在查询时出现错误。 对于每一次区间修改操作,我们让落在L<l&&r<=R区间上的新开...
  • 单点修改+区间修改和查询 例题+代码 目录 【线段树】 【引入】 【概述】 【单点修改和查询】 【建树】 【单点修改】 【区间查询最小值】 【区间查询区间和】 【区间修改和查询】 【延迟标记】 【标记下...
  • 线段树区间修改 昨天学习了线段树这样一种极其重要的算法,在竞赛是具有广泛的运用。可以用线段树对桶等其他的算法和结构进行维护。 基本题目如下:   【题目描述】: 如题,已知一个数列,你需要进行下面两种...
  • 今日学习在线编程题:区间修改
  • 树状数组 区间修改区间查询

    千次阅读 2018-08-21 17:02:48
    在这道题因为数据类型卡了我1...树状数组 区间修改+区间查询 实在是喜欢树状数组啊!好理解,更重要是好写啊!这次写写区间修改区间查询哈 首先还是上次区间修改单点查询用过的差分思想,我们先搞一个c数组作为差...
  • 在普通线段树上进行区间修改时我们引入了一个lazy数组,而在可持久化线段树上我们引入了lazy数组标记永久化,在普通线段树上有一个pushdown操作,会用lazy数组来更sum数组的值,而在可持久化线段树上则不会通过lazy...
  • 一维树状数组的区间修改与区间查询。 简要题意: 维护二维数组的矩阵加与矩阵查。 很显然,如果你用 二维线段树 的话,常数较大,加上要开 long long\text{long long}long long,很可能会 MLE + ...
  • 思考如何维护一个区间的值,想到了差分 对一个查分数组做一次前缀和可以得到每个位置的值 再对每个位置累加一下就是一个区间的值 公式化的讲,就是 设差分数组为ccc 则每个位置的值 vali=∑j=1icjval_i=\sum\...
  • 数组数组区间修改+区间查询 在之前整理树状数组笔记时,已经将单点修改以及区间查询写的很清楚了。树状数组本质上就是一个可以在线 快速查询前缀和,并可以快速更新数值并维护的数据结构。我们喜欢用树状数组是因为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 210,257
精华内容 84,102
关键字:

区间修改

友情链接: umat.zip