别来无恙【线段树模板】-育碧

豆嘉木

前言

（）

自上了高中并成为一名OIer起，我很久没上过这个论坛

毕竟在我印象里鱼C主要资源比较偏向语法学习

当然也很多高质量的精品文章，但不太可能像小甲鱼做的python和c++那样系统

一个月前我再次登上了鱼C

(在此浅浅吐槽一下)

诚然，鱼C是个很优秀的论坛(我的两千育碧足以证明我的忠心)

但是无处不在的AI让我感觉特别难受

互助板块里的AI就像个纸张

私以为这个AI也不见得能解决多少问题

还少了很多人情味

而且更重要的是现在的论坛让我感觉死气沉沉

(吐槽终)

AI禁区暂时对我而言是一片净土

但是这也太离谱了

论坛本身就是人人之间互相交流的平台，难道不是应该以真人交流为主？

可现在人人交流却只限于 AI禁区 这一个板块

应该开一个AI专区，而不是开一个AI禁区

不是我不能适应AI，我很支持AI，但是我认为论坛不应该让AI这么泛滥

正文

作为AI禁区-数据结构版的第一篇文章

在此奉上我的线段树模板(以 洛谷P3372 为样题)：

(先交个代码，后面有时间再补讲解)

(也有可能之后在算法区发后续内容，若如此我也会在这搞个传送门)

1. #include<bits/stdc++.h>
   
2. #define int ll
   
3. using namespace std;
   
4. using ll = long long;
   
5. const int MAXN = 1000007;
   
6. int n,m;
   
7. ll laz[5000007];
   
8. ll a[5000007],w[5000007];
   
9. 
   
10. void pushup(int u);
    
11. void build(const int u,int l, int r);
    
12. bool InRange(int L,int R,int l,int r);
    
13. bool OutofRange(int L,int  R,int l,int r);
    
14. ll query(int u,int L,int R,int l,int r);
    
15. void maketag(int u,int len, ll x);
    
16. void pushdown(int u,int L,int R);
    
17. void update(int u,int L, int R,int l,int r,ll x);
    
18. 
    
19. 
    
20. void pushup(int u){
    
21.         w[u]=w[u*2]+w[u*2+1];
    
22. }
    
23. 
    
24. void build(const int u, int l, int r){
    
25.         if(l==r){
    
26.                 w[u]=a[l];
    
27.                 return;
    
28.         }
    
29.         int mid = (l+r)/2;
    
30.         build(u*2,l,mid);
    
31.         build(u*2+1,mid+1,r);
    
32.         pushup(u);
    
33. }
    
34. 
    
35. bool InRange(int L, int R, int l, int r){
    
36.         return (L>=l)&&(R<=r);
    
37. }
    
38. 
    
39. bool OutofRange(int L, int R, int l, int r){
    
40.         return (L>r)||(R<l);
    
41. }
    
42. 
    
43. 
    
44. ll query(int u, int L, int R, int l, int r){ //cha2xun2
    
45. //        if(L>R)return 0;
    
46.         if(InRange(L,R,l,r)){ //包含于
    
47.                 return w[u];
    
48.         }
    
49.         else if(!OutofRange(L,R,l,r)){ //交集
    
50.                 int mid = (L+R)/2;
    
51.                 //printf("HERE!! , u=%lld, L=%lld,R=%lld,mid=%lld\n",u,L,R,mid);
    
52.                 if(L!=R)pushdown(u,L,R);
    
53.                 return query(u*2,L,mid,l,r)+query(u*2+1,mid+1,R,l,r);
    
54.         }
    
55.         else{
    
56.                 return 0;
    
57.         } //空集
    
58. }
    
59. 
    
60. void maketag(int u,int len,ll x){
    
61.         laz[u]+=x;
    
62.         w[u]+=len*x;
    
63. }
    
64. 
    
65. void pushdown(int u,int L,int R){
    
66.         int mid = (L+R)/2;
    
67.         maketag(u*2,mid-L+1,laz[u]);
    
68.         maketag(u*2+1,R-mid,laz[u]);
    
69.         laz[u]=0;
    
70. }
    
71. 
    
72. void update(int u,int L,int R,int l,int r,ll x){
    
73.         if(InRange(L,R,l,r)){
    
74.                 maketag(u,R-L+1,x);
    
75.         }
    
76.         else if(!OutofRange(L,R,l,r)){
    
77.                 int mid = (L+R)/2;
    
78.                 pushdown(u,L,R);
    
79.                 update(u*2,L,mid,l,r,x);
    
80.                 update(u*2+1,mid+1,R,l,r,x);
    
81.                 pushup(u);
    
82.         }
    
83. }
    
84. 
    
85. signed main(){
    
86.         scanf("%lld%lld",&n,&m);
    
87.         for(int i=1;i<=n;++i){
    
88.                 scanf("%lld",&a[i]);
    
89.         }
    
90.         build(1,1,n);
    
91.         while(m--){
    
92.                 int op,x,y;
    
93.                 ll k;
    
94.                 scanf("%lld",&op);
    
95.                 scanf("%lld%lld",&x,&y);
    
96.                 if(op==1){
    
97.                         scanf("%lld",&k);
    
98.                         update(1,1,n,x,y,k);
    
99.                 }else{
    
100.                         printf("%lld\n",query(1,1,n,x,y));
     
101.                 }
     
102.         }
     
103.         return 0;
     
104. }

复制代码

小甲鱼的二师兄

其实流量降低并不能全怪 AI，整个行业都进入了低谷期，希望早日熬过去吧

zhangchenyvn

放心，论坛本来就是为了人人交流而生，人人交流在论坛上是不会被取代的。况且，人人交流中产生的学习、友情是AI永远无法理解无法替代的。

AI确实有很多好处，可以解决很多问题，但是许多更重要的问题都是AI无法解决的。这就是AI的局限性，也许永远也无法打破。

小甲鱼的二师兄

zhangchenyvn 发表于 2024-5-12 16:14
放心，论坛本来就是为了人人交流而生，人人交流在论坛上是不会被取代的。况且，人人交流中产生的学习、友情 ...

同意

不二如是

有点难