首页 > 代码库 > 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 51 5 4 2 32 2 41 2 3 22 3 41 1 5 12 1 4
输出样例#1：
11820
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^，保证在int64/long long数据范围内）
样例说明：
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>using namespace std;struct TreeNodeType{ long long int l,r,dis,flag;};struct TreeNodeType tree[100000*4+15];long long int n,m,a,b,x,s1,s2,if_,s;void tree_up(int now){ tree[now].dis=tree[now<<1].dis+tree[now<<1|1].dis; }void tree_down(int now){ tree[now*2].flag+=tree[now].flag; tree[now*2+1].flag+=tree[now].flag; tree[now*2].dis+=tree[now].flag*(tree[now*2].r-tree[now*2].l+1); tree[now*2+1].dis+=tree[now].flag*(tree[now*2+1].r-tree[now*2+1].l+1); tree[now].flag=0; }void tree_build(int now,int l,int r){ tree[now].l=l;tree[now].r=r; if(tree[now].l==tree[now].r) { cin>>tree[now].dis; return ; } long long int mid=(tree[now].l+tree[now].r)/2; tree_build(now*2,l,mid); tree_build(now*2+1,mid+1,r); tree_up(now);}void tree_change(long long int k,long long int l,long long int r,long long int x){ if(tree[k].l==l&&tree[k].r==r) { tree[k].dis+=x*(tree[k].r-tree[k].l+1); tree[k].flag+=x; return ; } if(tree[k].flag) tree_down(k); long long int mid=(tree[k].l+tree[k].r)/2; if(l>mid) tree_change(k*2+1,l,r,x); else if(r<=mid) tree_change(k*2,l,r,x); else { tree_change(k*2,l,mid,x); tree_change(k*2+1,mid+1,r,x); } tree_up(k);}long long int tree_find(long long int now,long long int l,long long int r){ if(tree[now].l==l&&tree[now].r==r) return tree[now].dis; long long int mid=(tree[now].l+tree[now].r)/2; if(tree[now].flag) tree_down(now); if(l>mid) return tree_find(now*2+1,l,r); else if(r<=mid) return tree_find(now*2,l,r); return tree_find(now*2+1,mid+1,r)+tree_find(now*2,l,mid);}int main(){ cin>>n; cin>>m; tree_build(1,1,n); for(long long int i=1;i<=m;i++) { cin>>if_; if(if_==1) { cin>>a>>b>>x; tree_change(1,a,b,x); } else { cin>>s1>>s2; long long int sb=tree_find(1,s1,s2); cout<<sb<<endl; } } return 0; }
P3372 【模板】线段树 1
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。