首页 > 代码库 > 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数据范围内）
样例说明：
在这里提醒大家一点
如果你用的是Dev-c++的5.92版本的话，用%lld输入可能会发生运行时错误
这时候如果你确保你的程序百分百对的话，可以直接提交
如果你不放心自己的程序，可以把%lld改成%I64d（I是大写i）进行调试，这样就不会出错了
但是切记
提交到洛谷上的时候一定要写%lld！！！！！！
否则全部WA而不是RE
切记切记
（ps：cena评测系统也是%lld）
我的代码基本是由函数构成的
写法比较通俗易懂
大家可以参考一下
再教大家一个小技巧：
如果你想要大批量的吧int改为long long int 的话
可以使#define 语句
然后用查找替换功能
注意查找的时候 查找的是 int+空格
否则你的printf会变得非常美观（手动滑稽）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define lglg long long int 5 using namespace std; 6 const lglg MAXN=200001; 7 lglg n,m; 8 lglg ans=0; 9 struct node10 {11 lglg l,r,w,f;12 }tree[MAXN*4];13 inline void updata(lglg k)14 {15 tree[k].w=tree[k*2].w+tree[k*2+1].w;16 }17 inline void build(lglg k,lglg ll,lglg rr)18 {19 tree[k].l=ll;tree[k].r=rr;20 if(tree[k].l==tree[k].r)21 {22 scanf("%lld",&tree[k].w);23 return ;24 }25 lglg m=(ll+rr)/2;26 build(k*2,ll,m);27 build(k*2+1,m+1,rr);28 updata(k);29 }30 inline void down(lglg k)31 {32 tree[k*2].f+=tree[k].f;33 tree[k*2+1].f+=tree[k].f;34 tree[k*2].w+=(tree[k*2].r-tree[k*2].l+1)*tree[k].f;35 tree[k*2+1].w+=(tree[k*2+1].r-tree[k*2+1].l+1)*tree[k].f;36 tree[k].f=0;37 }38 inline void interval_change(lglg k,lglg ll,lglg rr,lglg v)39 {40 if(tree[k].l>=ll&&tree[k].r<=rr)41 {42 tree[k].w+=(tree[k].r-tree[k].l+1)*v;43 tree[k].f+=v;44 return ;45 }46 if(tree[k].f) down(k);47 lglg m=(tree[k].l+tree[k].r)/2;48 if(ll<=m) interval_change(k*2,ll,rr,v);49 if(rr>m) interval_change(k*2+1,ll,rr,v);50 updata(k);51 }52 inline void interval_ask(lglg k,lglg ll,lglg rr)53 {54 if(tree[k].l>=ll&&tree[k].r<=rr)55 {56 ans+=tree[k].w;57 return ;58 }59 if(tree[k].f) down(k);60 lglg m=(tree[k].l+tree[k].r)/2;61 if(ll<=m)62 interval_ask(k*2,ll,rr);63 if(rr>m)64 interval_ask(k*2+1,ll,rr);65 }66 int main()67 {68 scanf("%lld",&n);69 scanf("%lld",&m);70 build(1,1,n);71 while(m--)72 {73 lglg how;74 scanf("%lld",&how);75 if(how==1)//区间增加 76 {77 lglg x,y,v;78 scanf("%lld%lld%lld",&x,&y,&v);79 interval_change(1,x,y,v);80 }81 else//区间求和 82 {83 lglg x,y;84 ans=0;85 scanf("%lld%lld",&x,&y);86 interval_ask(1,x,y);87 printf("%lld\n",ans);88 }89 }90 return 0;91 }
P3372 【模板】线段树 1
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。