线段树区间修改

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;
}

算法

更多相关内容

线段树区间修改区间查询

2022-02-17 20:15:10

维护序列的二叉树树上每个点对应序列上一段连续的区间 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;
}

收起

展开全文

排序算法数据结构 b树

一个简单的整数问题2(树状数组：区间查询&&区间修改)
2021-01-03 14:42:34

给定一个长度为N的数列A，以及M条指令，每条指令可能是以下两种之一： 1、“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。 2、“Q l r”，表示询问数列中第 l~r 个数的和。对于每个询问，输出一个整数表示...

收起

线段树（区间修改，区间查询）

2021-04-23 15:18:12

线段树的区间修改 本题如果用单点修改的思想会T，所以需要引入一个数组 l a z y lazy lazy ，优秀程序员必备 l a z y lazy lazy定义此为偷懒该数组意在储存 t r e e tree tree 数组的所有区间操作就是将原先每个...

线段树的区间修改

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

$l a z y$ 定义

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

$e g .$

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

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

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

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;
}

收起

展开全文

线段树