首页 > 代码库 > 线段树区间修改 P3372 【模板】线段树 1
线段树区间修改 P3372 【模板】线段树 1
题目描述
如题,已知一个数列,你需要进行下面两种操作:
1.将某区间每一个数加上x
2.求出某区间每一个数的和
输入输出格式
输入格式:
第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数,表示一个操作,具体如下:
操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k
操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和
输出格式:
输出包含若干行整数,即为所有操作2的结果。
输入输出样例
输入样例#1:
5 5 1 5 4 2 3 2 2 4 1 2 3 2 2 3 4 1 1 5 1 2 1 4
输出样例#1:
11 8 20
说明
时空限制:1000ms,128M
数据规模:
对于30%的数据:N<=8,M<=10
对于70%的数据:N<=1000,M<=10000
对于100%的数据:N<=100000,M<=100000
(数据已经过加强^_^,保证在int64/long long数据范围内)
样例说明:
线段树区间修改一般有两种,一种是区间每个数加上某数,一种是区间每个数都乘上某数,两种本质上都是一样的。这题用的是第一种修改。
线段树的区间修改是用一种延迟标记的思想,也叫lazy-tag思想,其思想通俗点讲就是将当前节点标记,需要访问其子节点时,传递延迟标记,并消除此节点标记。
代码:
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define ll long long using namespace std; int gi() { int x=0,y=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) y=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return x*y; } ll gl() { ll x=0,y=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) y=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return x*y; } ll a[100045],tree[400045],lazy[400045]; void tag(int rt,int l,int r) { if(l==r) return; if(lazy[rt]) { int m=(l+r)>>1; tree[rt*2]+=lazy[rt]*(m-l+1); tree[rt*2+1]+=lazy[rt]*(r-m); lazy[rt*2]+=lazy[rt]; lazy[rt*2+1]+=lazy[rt]; lazy[rt]=0; } } void update(int rt,int l,int r,int L,int R,ll change) { if(L<=l&&R>=r) { tree[rt]+=change*(r-l+1); lazy[rt]+=change; return; } tag(rt,l,r); int m=(r+l)>>1; if(L<=m)update(rt*2,l,m,L,R,change); if(R>m)update(rt*2+1,m+1,r,L,R,change); tree[rt]=tree[rt*2]+tree[rt*2+1]; } ll query(int rt,int l,int r,int L,int R) { tag(rt,l,r); if(L<=l&&R>=r) return tree[rt]; int m=(l+r)>>1; ll ans=0; if(L<=m) ans+=query(rt*2,l,m,L,R); if(R>m) ans+=query(rt*2+1,m+1,r,L,R); return ans; } int main() { int n=gi(),m=gi(),p,x,y; ll k; for(int i=1;i<=n;i++) update(1,1,100045,i,i,gl()); for(int i=1;i<=m;i++) { p=gi(); if(p==1) { x=gi(),y=gi(),k=gl(); update(1,1,100045,x,y,k); } else { x=gi(),y=gi(); printf("%lld\n",query(1,1,100045,x,y)); } } return 0; }
线段树区间修改 P3372 【模板】线段树 1
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。