直接上干货首先是定义：
const int maxn=100005,maxq=100005; int n,q; long long a[maxn]; struct tree { long long sum,lazy; long long _max,_min; bool v; int l,r; }t[4*maxn];
这里开了4倍结点大小的，用的时候建议改成3，因为啥呢，我们是根据满二叉树（这里虽然是完全二叉树）的最后一层结点数量来确定整个树的结点数量，如果最后一层的结点数量为n，那么整个树的结点数量是2倍还多，开3还是比较合适的，如果比较极限的话，有必要看一下到底开多少
然后是建树：
void buildtree(int l,int r,int o) { t[o].l=l,t[o].r=r; if(t[o].l==t[o].r) { t[o].sum=t[o]._max=t[o]._min=a[l]; return; } int ch=o*2; int m=(l+r)/2; buildtree(l,m,ch); buildtree(m+1,r,ch+1); t[o].sum=t[ch].sum+t[ch+1].sum; t[o]._max=max(t[ch]._max,t[ch+1]._max); t[o]._min=min(t[ch]._min,t[ch+1]._min); }
我们要维护什么，就要在建树的时候加以体现
然后是释放懒标记，这里其实是有一定难度的，因为你要根据实际的情况来调整你释放懒标记的策略，比如说打了重置标记和没打重置标记的时候，释放懒标记的情况就是不一样的，具体问题具体分析
这里是线段树最大的难点
void release(int o) { if(t[o].lazy==0&&t[o].v==0) return; int ch=o*2; int flag=1; if(t[o].v) { t[o].sum=(t[o].r-t[o].l+1)*t[o].lazy; t[o]._max=t[o]._min=t[o].lazy; if(t[o].l!=t[o].r) { t[ch].lazy=t[ch+1].lazy=t[o].lazy; t[ch].v=t[ch+1].v=true; } t[o].v=false; flag=0; } if(flag) { t[o].sum+=(t[o].r-t[o].l+1)*t[o].lazy; t[o]._max+=t[o].lazy; t[o]._min+=t[o].lazy; if(t[o].l!=t[o].r) { t[ch].lazy+=t[o].lazy; t[ch+1].lazy+=t[o].lazy; } } t[o].lazy=0; }
接下来我们给出区间重置的函数，其本质就是打重置标记：
void reset(int l,int r,long long x,int o) { int ch=o*2; if(t[o].l==l&&t[o].r==r) { t[o].lazy=x; t[o].v=true; release(o); return; } release(o); int m=(t[o].l+t[o].r)/2; if(r<=m) { reset(l,r,x,ch); release(ch+1); } if(l>m) { reset(l,r,x,ch+1); release(ch); } if(l<=m&&r>m) { reset(l,m,x,ch); reset(m+1,r,x,ch+1); } t[o].sum=t[ch].sum+t[ch+1].sum; t[o]._max=max(t[ch]._max,t[ch+1]._max); t[o]._min=min(t[ch]._min,t[ch+1]._min); }
接下来我们给出修改区间的函数，在这里区间重置的影响在处理懒标记的时候就处理好了，不用考虑相互作用，如果相互作用的话，难度直接爆炸
void change(int l,int r,long long x,int o) { int ch=o*2; if(t[o].l==l&&t[o].r==r) { t[o].lazy+=x; release(o); return; } release(o); int m=(t[o].l+t[o].r)/2; if(r<=m) { change(l,r,x,ch); release(ch+1); } if(l>m) { change(l,r,x,ch+1); release(ch); } if(l<=m&&r>m) { change(l,m,x,ch); change(m+1,r,x,ch+1); } t[o].sum+=(r-l+1)*x; t[o]._max=max(t[ch]._max,t[ch+1]._max); t[o]._min=min(t[ch]._min,t[ch+1]._min); }
查询区间和，查询区间最大值以及查询区间最小值大同小异
long long query(int l,int r,int o) { int ch=o*2; release(o); if(t[o].l==l&&t[o].r==r) return t[o].sum; int m=(t[o].l+t[o].r)/2; if(r<=m) return query(l,r,ch); if(l>m) return query(l,r,ch+1); if(l<=m&&r>m) return query(l,m,ch)+query(m+1,r,ch+1); } long long get_max(int l,int r,int o) { int ch=o*2; release(o); if(t[o].l==l&&t[o].r==r) return t[o]._max; int m=(t[o].l+t[o].r)/2; if(r<=m) return get_max(l,r,ch); if(l>m) return get_max(l,r,ch+1); if(l<=m&&r>m) return max(get_max(l,m,ch),get_max(m+1,r,ch+1)); } long long get_min(int l,int r,int o) { int ch=o*2; release(o); if(t[o].l==l&&t[o].r==r) return t[o]._min; int m=(t[o].l+t[o].r)/2; if(r<=m) return get_min(l,r,ch); if(l>m) return get_min(l,r,ch+1); if(l<=m&&r>m) return min(get_min(l,m,ch),get_min(m+1,r,ch+1)); }
所有的重置和修改都是从头一直往下改，改到对应的区间就打上懒标记，其后的实现逻辑交给释放懒标记处理，所以我们在查询的时候只要释放了懒标记，之前所有的影响都可以忽略不计
下面给出完整的线段树模板，对于更复杂的线段树问题，将单独开文章进行描述
1 //aininot260 区间修改，区间重置，查询区间和，查询区间最值 2 #include<iostream> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 const int maxn=100005,maxq=100005; 7 int n,q; 8 long long a[maxn]; 9 struct tree 10 { 11 long long sum,lazy; 12 long long _max,_min; 13 bool v; 14 int l,r; 15 }t[4*maxn]; 16 void buildtree(int l,int r,int o) 17 { 18 t[o].l=l,t[o].r=r; 19 if(t[o].l==t[o].r) 20 { 21 t[o].sum=t[o]._max=t[o]._min=a[l]; 22 return; 23 } 24 int ch=o*2; 25 int m=(l+r)/2; 26 buildtree(l,m,ch); 27 buildtree(m+1,r,ch+1); 28 t[o].sum=t[ch].sum+t[ch+1].sum; 29 t[o]._max=max(t[ch]._max,t[ch+1]._max); 30 t[o]._min=min(t[ch]._min,t[ch+1]._min); 31 } 32 void release(int o) 33 { 34 if(t[o].lazy==0&&t[o].v==0) 35 return; 36 int ch=o*2; 37 int flag=1; 38 if(t[o].v) 39 { 40 t[o].sum=(t[o].r-t[o].l+1)*t[o].lazy; 41 t[o]._max=t[o]._min=t[o].lazy; 42 if(t[o].l!=t[o].r) 43 { 44 t[ch].lazy=t[ch+1].lazy=t[o].lazy; 45 t[ch].v=t[ch+1].v=true; 46 } 47 t[o].v=false; 48 flag=0; 49 } 50 if(flag) 51 { 52 t[o].sum+=(t[o].r-t[o].l+1)*t[o].lazy; 53 t[o]._max+=t[o].lazy; 54 t[o]._min+=t[o].lazy; 55 if(t[o].l!=t[o].r) 56 { 57 t[ch].lazy+=t[o].lazy; 58 t[ch+1].lazy+=t[o].lazy; 59 } 60 } 61 t[o].lazy=0; 62 } 63 void reset(int l,int r,long long x,int o) 64 { 65 int ch=o*2; 66 if(t[o].l==l&&t[o].r==r) 67 { 68 t[o].lazy=x; 69 t[o].v=true; 70 release(o); 71 return; 72 } 73 release(o); 74 int m=(t[o].l+t[o].r)/2; 75 if(r<=m) 76 { 77 reset(l,r,x,ch); 78 release(ch+1); 79 } 80 if(l>m) 81 { 82 reset(l,r,x,ch+1); 83 release(ch); 84 } 85 if(l<=m&&r>m) 86 { 87 reset(l,m,x,ch); 88 reset(m+1,r,x,ch+1); 89 } 90 t[o].sum=t[ch].sum+t[ch+1].sum; 91 t[o]._max=max(t[ch]._max,t[ch+1]._max); 92 t[o]._min=min(t[ch]._min,t[ch+1]._min); 93 } 94 void change(int l,int r,long long x,int o) 95 { 96 int ch=o*2; 97 if(t[o].l==l&&t[o].r==r) 98 { 99 t[o].lazy+=x; 100 release(o); 101 return; 102 } 103 release(o); 104 int m=(t[o].l+t[o].r)/2; 105 if(r<=m) 106 { 107 change(l,r,x,ch); 108 release(ch+1); 109 } 110 if(l>m) 111 { 112 change(l,r,x,ch+1); 113 release(ch); 114 } 115 if(l<=m&&r>m) 116 { 117 change(l,m,x,ch); 118 change(m+1,r,x,ch+1); 119 } 120 t[o].sum+=(r-l+1)*x; 121 t[o]._max=max(t[ch]._max,t[ch+1]._max); 122 t[o]._min=min(t[ch]._min,t[ch+1]._min); 123 } 124 long long query(int l,int r,int o) 125 { 126 int ch=o*2; 127 release(o); 128 if(t[o].l==l&&t[o].r==r) 129 return t[o].sum; 130 int m=(t[o].l+t[o].r)/2; 131 if(r<=m) 132 return query(l,r,ch); 133 if(l>m) 134 return query(l,r,ch+1); 135 if(l<=m&&r>m) 136 return query(l,m,ch)+query(m+1,r,ch+1); 137 } 138 long long get_max(int l,int r,int o) 139 { 140 int ch=o*2; 141 release(o); 142 if(t[o].l==l&&t[o].r==r) 143 return t[o]._max; 144 int m=(t[o].l+t[o].r)/2; 145 if(r<=m) 146 return get_max(l,r,ch); 147 if(l>m) 148 return get_max(l,r,ch+1); 149 if(l<=m&&r>m) 150 return max(get_max(l,m,ch),get_max(m+1,r,ch+1)); 151 } 152 long long get_min(int l,int r,int o) 153 { 154 int ch=o*2; 155 release(o); 156 if(t[o].l==l&&t[o].r==r) 157 return t[o]._min; 158 int m=(t[o].l+t[o].r)/2; 159 if(r<=m) 160 return get_min(l,r,ch); 161 if(l>m) 162 return get_min(l,r,ch+1); 163 if(l<=m&&r>m) 164 return min(get_min(l,m,ch),get_min(m+1,r,ch+1)); 165 } 166 int main() 167 { 168 cin>>n>>q; 169 for(int i=1;i<=n;i++) 170 cin>>a[i]; 171 buildtree(1,n,1); 172 while(q--) 173 { 174 string x; 175 cin>>x; 176 if(x=="add") 177 { 178 int y,z,w; 179 cin>>y>>z>>w; 180 change(y,z,w,1); 181 } 182 if(x=="sum") 183 { 184 int y,z; 185 cin>>y>>z; 186 cout<<query(y,z,1)<<endl; 187 } 188 if(x=="set") 189 { 190 int y,z,w; 191 cin>>y>>z>>w; 192 reset(y,z,w,1); 193 } 194 if(x=="max") 195 { 196 int y,z; 197 cin>>y>>z; 198 cout<<get_max(y,z,1)<<endl; 199 } 200 if(x=="min") 201 { 202 int y,z; 203 cin>>y>>z; 204 cout<<get_min(y,z,1)<<endl; 205 } 206 } 207 return 0; 208 }