线段树在n较小、操作较多的情况下效率很高。虽然如此，如果直接暴力进行修改的话还是会TLE得很惨。于是一个叫做懒标记的东西应运而生。
懒标记
why优秀：在修改一个节点时，若此点已经被懒标记所标记，我们就将此点懒标记取消，标记左右子节点传递下去，当被更新或者被查询时再更新节点，节约了根本不会被用到的花费。这也是线段树作为“树”优秀的地方。
开始学习
洛谷已经为我们排好了对线段树的逐层深度学习XD
P3372 【模板】线段树 1
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int maxn=1e5,maxm=1e5; 5 typedef long long ll; 6 void read(int &x) 7 { 8 char c=getchar(); 9 while(c<'0' or c>'9')c=getchar(); 10 x=c-'0',c=getchar(); 11 while(c>='0' and c<='9'){ 12 x*=10,x+=c-'0',c=getchar(); 13 } 14 } 15 int a[maxn*10]; 16 struct node{ 17 ll l,r,sum,tag; 18 }e[maxn*6]; 19 int n,m,k; 20 inline ll ls(ll ro){return ro<<1;} 21 inline ll rs(ll ro){return ro<<1|1;} 22 inline void push_up(ll ro) 23 { 24 e[ro].sum=e[ls(ro)].sum+e[rs(ro)].sum; 25 } 26 inline void push_down(ll ro) 27 { 28 e[ls(ro)].sum+=e[ro].tag*(e[ls(ro)].r-e[ls(ro)].l+1); 29 e[rs(ro)].sum+=e[ro].tag*(e[rs(ro)].r-e[rs(ro)].l+1); 30 e[ls(ro)].tag+=e[ro].tag; 31 e[rs(ro)].tag+=e[ro].tag; 32 e[ro].tag=0; 33 } 34 35 void build(ll ro,ll l,ll r) 36 { 37 e[ro].l=l,e[ro].r=r; 38 if(l==r) 39 { 40 e[ro].sum=a[l]; 41 return; 42 } 43 e[ro].tag=0; 44 ll mid=(l+r)>>1; 45 build(ls(ro),l,mid); 46 build(rs(ro),mid+1,r); 47 push_up(ro); 48 } 49 50 void update(ll ro,ll l,ll r) 51 { 52 if(e[ro].l>=l and r>=e[ro].r) 53 { 54 e[ro].sum+=k*(e[ro].r-e[ro].l+1); 55 e[ro].tag+=k; 56 return; 57 } 58 push_down(ro); 59 ll mid=(e[ro].l+e[ro].r)>>1; 60 if(l<=mid)update(ls(ro),l,r); 61 if(r> mid)update(rs(ro),l,r); 62 push_up(ro); 63 } 64 65 ll check(ll ro,ll l,ll r) 66 { 67 if(l<=e[ro].l and r>=e[ro].r)return e[ro].sum; 68 push_down(ro); 69 int mid=(e[ro].l+e[ro].r)>>1; 70 ll ans=0; 71 if(l<=mid)ans+=check(ls(ro),l,r); 72 if(r> mid)ans+=check(rs(ro),l,r); 73 return ans; 74 } 75 signed main() 76 { 77 read(n);read(m); 78 for(int i=1;i<=n;i++) 79 read(a[i]); 80 build(1,1,n); 81 int casee,l,r; 82 for(int i=1;i<=m;i++) 83 { 84 read(casee); 85 switch(casee) 86 { 87 case(1):{ 88 read(l);read(r);read(k); 89 update(1,l,r); 90 break; 91 } 92 case(2):{ 93 read(l);read(r); 94 printf("%lld\n",check(1,l,r)); 95 break; 96 } 97 } 98 } 99 return 0; 100 }
P3373 【模板】线段树 2
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int maxn=1e5; 5 typedef long long ll; 6 int n,m,p,a[maxn],k; 7 struct tree{ 8 ll l,r,val,add,tag; 9 }e[maxn*4]; 10 inline void read(int &x) 11 { 12 char c=getchar(); 13 while(c<'0' or c>'9')c=getchar(); 14 x=c-'0',c=getchar(); 15 while(c>='0' and c<='9')x*=10,x+=c-'0',c=getchar(); 16 } //这个快读读不了负数 XD 17 inline ll ls(int ro){return ro<<1;} 18 inline ll rs(int ro){return ro<<1|1;} 19 20 inline void lazy_add(ll ro) 21 { 22 e[ls(ro)].add=(e[ls(ro)].add*e[ro].tag+e[ro].add)%p; 23 e[rs(ro)].add=(e[rs(ro)].add*e[ro].tag+e[ro].add)%p; 24 //给子节点加上懒标记，add需要乘tag才能保证不变，再加上add 25 } 26 27 inline void lazy_tag(ll ro) 28 { 29 e[ls(ro)].tag=(e[ls(ro)].tag*e[ro].tag)%p; 30 e[rs(ro)].tag=(e[rs(ro)].tag*e[ro].tag)%p; 31 //相同，乘标记挺正常 32 } 33 34 inline void push_down(ll ro) 35 { 36 e[ls(ro)].val=(e[ls(ro)].val*e[ro].tag+e[ro].add*(e[ls(ro)].r-e[ls(ro)].l+1))%p; 37 e[rs(ro)].val=(e[rs(ro)].val*e[ro].tag+e[ro].add*(e[rs(ro)].r-e[rs(ro)].l+1))%p; 38 //分析：给子节点的值乘上乘标记值，再加上加标记在它区间元素个数的和； 39 lazy_tag(ro); 40 lazy_add(ro); 41 e[ro].add=0,e[ro].tag=1;//别忘了清除懒标记 42 } 43 44 inline void push_up(ll ro) 45 { 46 e[ro].val=(e[ls(ro)].val+e[rs(ro)].val)%p;//给爷加和 因为这个题只需要输出和所以这样做，并不普遍 47 } 48 49 void build(ll ro,ll l ,ll r) 50 { 51 e[ro].l=l,e[ro].r=r; 52 e[ro].tag=1,e[ro].add=0; 53 if(l==r){e[ro].val=a[l];return;}//赋值 54 int mid=(l+r)>>1; 55 build(ls(ro),l,mid); 56 build(rs(ro),mid+1,r); 57 push_up(ro); 58 e[ro].val%=p;//膜一下 59 } 60 61 //更新乘 62 void update_tag(ll ro,ll l ,ll r) 63 { 64 if(e[ro].l>=l and e[ro].r<=r) 65 { 66 e[ro].val=(e[ro].val*k)%p; 67 e[ro].tag=(e[ro].tag*k)%p; 68 e[ro].add=(e[ro].add*k)%p; 69 return ; 70 } 71 push_down(ro); 72 int mid=(e[ro].l+e[ro].r)>>1; 73 if(l<=mid)update_tag(ls(ro),l,r); 74 if(r> mid)update_tag(rs(ro),l,r); 75 push_up(ro); 76 } 77 78 //更新和 79 void update_add(ll ro,ll l,ll r) 80 { 81 if(e[ro].l>=l and e[ro].r<=r) 82 { 83 e[ro].add=(e[ro].add+k)%p; 84 e[ro].val=(e[ro].val+k*(e[ro].r-e[ro].l+1))%p;//注意这个是改区间和 85 return ; 86 } 87 push_down(ro); 88 int mid=(e[ro].l+e[ro].r)>>1; 89 if(l<=mid)update_add(ls(ro),l,r); 90 if(r> mid)update_add(rs(ro),l,r); 91 push_up(ro); 92 } 93 94 ll query(ll ro,ll l,ll r) 95 { 96 if(e[ro].l>=l and e[ro].r<=r) 97 return e[ro].val; 98 push_down(ro); 99 int mid=(e[ro].l+e[ro].r)>>1; 100 int ans=0; 101 if(l<=mid) ans+=query(ls(ro),l,r); 102 if(r> mid) ans+=query(rs(ro),l,r); 103 return ans%p; 104 } 105 int main() 106 { 107 read(n);read(m);read(p); 108 for(int i=1;i<=n;i++)read(a[i]); 109 build(1,1,n); 110 int casee,l,r; 111 while(m--) 112 { 113 read(casee); 114 switch(casee) 115 { 116 case(1):{ 117 read(l);read(r);read(k); 118 update_tag(1,l,r); 119 break; 120 } 121 case(2):{ 122 read(l);read(r);read(k); 123 update_add(1,l,r); 124 break; 125 } 126 case(3):{ 127 read(l);read(r); 128 printf("%lld\n",query(1,l,r)); 129 break; 130 } 131 } 132 } 133 return 0; 134 }
P6242 【模板】线段树 3
我不会XD
有待更新
（其实和2一样就是复杂一点）