今天植树节,来种一棵线段树。
题目链接:https://www.luogu.org/problemnew/show/P3372
题目描述
如题,已知一个数列,你需要进行下面两种操作:
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的结果。
输入输出样例
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
输出样例:
11
8
20
说明
时空限制:1000 ms , 128 M
数据规模:
对于30%的数据:N<=8,M<=10
对于70%的数据:N<=1000,M<=10000
对于100%的数据:N<=100000,M<=100000
样例说明:
题解
一般来说,拿到这道题的第一个反应应该是硬模,然后一看数据,发现撑不过 O(100000*100000)。‘
于是,我们就有了线段树这种神奇的东西。至于线段树呢,就是下面这种神奇的东西 ↓
对于线段树中的每一个子节点而言,他们都储存着一段子序列,而对于每一个叶子节点而言,他们储存的是单个的信息元素,而每一个父节点都是他两个子节点的整合。
本题是线段树改段求段的模板题,也就是区间修改与区间查询。线段树还有点修改等其他功能,欲知推荐推荐一篇博文:
一、建树与维护
1.建树
从根开始,往下建树。根的掌管范围为1~n ( l=1,r=n )。当一个节点掌管着不止一个信息元素时,便让他的左儿子掌管1~mid (mid=(l+r)/2),右儿子掌管 mid+1~r 。当 l==r (叶子节点)时,则直接赋值。
2.维护
若一个节点有左右儿子,则它的值等于它左儿子的值加上它右儿子的值。
建树代码 ↓
void bt(int l,int r){
len++;int now=len;
tr[now].l=l;tr[now].r=r;tr[now].lc=tr[now].rc=-1;tr[now].c=tr[now].lz=0;//l,r为左右边界,lc为左儿子,rc为右儿子,c为值,lz为lazy tag
if(l<r)
{
int mid=(l+r)/2;
tr[now].lc=len+1;bt(l,mid);
tr[now].rc=len+1;bt(mid+1,r);
tr[now].c=tr[tr[now].lc].c+tr[tr[now].rc].c;
}
else if(l==r) tr[now].c=a[l];
}
二、区间修改与查询
1.修改在进行区间修改的时候,我们引入一个概念:lazy tag (懒标记,简称 lazy)。它的作用是向下延迟修改,但因已修改自身的值,在向上传递信息时返回的结果是正确的。
if(tr[now].l==l && tr[now].r==r){ tr[now].c+=(r-l+1)*k; tr[now].lz+=k; return;}
由于我们这样的记录方式,在我们每次修改的时候都需向下推一次 lazy(pushdown 操作)。推的时候我们先修改lazy的值,再分别修改左右儿子的值(倒过来也没有影响)。
与最后再对线段树进行维护。
pushdown ↓
void pushdown(int now){ int lc=tr[now].lc,rc=tr[now].rc; tr[lc].lz+=tr[now].lz; tr[rc].lz+=tr[now].lz; tr[lc].c+=(tr[lc].r-tr[lc].l+1)*tr[now].lz; tr[rc].c+=(tr[rc].r-tr[rc].l+1)*tr[now].lz; tr[now].lz=0;}
区间修改代码 ↓
void change(int now,int l,int r,int k){ if(tr[now].l==l && tr[now].r==r) { tr[now].c+=(r-l+1)*k; tr[now].lz+=k; return; } if(tr[now].lz) pushdown(now); int lc=tr[now].lc,rc=tr[now].rc; int mid=(tr[now].l+tr[now].r)/2; if(r<=mid) change(lc,l,r,k); else if(mid+1<=l) change(rc,l,r,k); else { change(lc,l,mid,k); change(rc,mid+1,r,k); } tr[now].c=tr[lc].c+tr[rc].c;}
2.查询
与修改差不多,要注意的是每找到一个节点就往下推一次 lazy。
区间查询代码 ↓
ll findsum(int now,int l,int r){ if(tr[now].l==l && tr[now].r==r) return tr[now].c; if(tr[now].lz) pushdown(now); int lc=tr[now].lc,rc=tr[now].rc; int mid=(tr[now].l+tr[now].r)/2; if(r<=mid) return findsum(lc,l,r); else if(mid+1<=l) return findsum(rc,l,r); else return findsum(lc,l,mid)+findsum(rc,mid+1,r);}
最后,标程 ↓
#include<cstdio>#include<cstdlib>#define ll long longstruct node{int l,r,lc,rc;ll c,lz;}tr[400010];int a[100010];int n,m,len=0;void bt(int l,int r){ len++;int now=len; tr[now].l=l;tr[now].r=r;tr[now].lc=tr[now].rc=-1;tr[now].c=tr[now].lz=0; if(l<r) { int mid=(l+r)/2; tr[now].lc=len+1;bt(l,mid); tr[now].rc=len+1;bt(mid+1,r); tr[now].c=tr[tr[now].lc].c+tr[tr[now].rc].c; } else if(l==r) tr[now].c=a[l];}void pushdown(int now){ int lc=tr[now].lc,rc=tr[now].rc; tr[lc].lz+=tr[now].lz; tr[rc].lz+=tr[now].lz; tr[lc].c+=(tr[lc].r-tr[lc].l+1)*tr[now].lz; tr[rc].c+=(tr[rc].r-tr[rc].l+1)*tr[now].lz; tr[now].lz=0;}void change(int now,int l,int r,int k){ if(tr[now].l==l && tr[now].r==r) { tr[now].c+=(r-l+1)*k; tr[now].lz+=k; return; } if(tr[now].lz) pushdown(now); int lc=tr[now].lc,rc=tr[now].rc; int mid=(tr[now].l+tr[now].r)/2; if(r<=mid) change(lc,l,r,k); else if(mid+1<=l) change(rc,l,r,k); else { change(lc,l,mid,k); change(rc,mid+1,r,k); } tr[now].c=tr[lc].c+tr[rc].c;}ll findsum(int now,int l,int r){ if(tr[now].l==l && tr[now].r==r) return tr[now].c; if(tr[now].lz) pushdown(now); int lc=tr[now].lc,rc=tr[now].rc; int mid=(tr[now].l+tr[now].r)/2; if(r<=mid) return findsum(lc,l,r); else if(mid+1<=l) return findsum(rc,l,r); else return findsum(lc,l,mid)+findsum(rc,mid+1,r);}int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); bt(1,n); for(int i=1;i<=m;i++) { int p,x,y; scanf("%d %d %d",&p,&x,&y); if(p==1) { ll z; scanf("%lld",&z); change(1,x,y,z); } if(p==2) printf("%lld\n",findsum(1,x,y)); }}
(温馨提示:记得开 long long)