这里是几道线段树的入门题目，难度多在（普及+提高-）附近，如果对模板掌握的好的话可以直接跳过这里。

1、开关

特殊的懒标记。

题目中每个节点都是开关，只有开或者关两种状态，很容易想到如果对一个序列连续操作两次，等于没有操作，所以在区间更新时用到异或的操作。

用一个bool型的数存储每个节点的懒标记，对懒标记进行更新就是把这个数取反。把懒标记与1异或，如果懒标记的数是1，因为二进制下相等，所以得到0；如果0与1异或，二进制下不相等，得到1。这样就起到了取反的操作。

下一个要解决的问题，是区间修改。

其实很好想，区间里的开关，不是开就是关，题目要求打开的开关数，如果区间修改就把打开的开关数变成此时关闭的开关数就行了。

区间的总开关数-区间打开的开关数=区间关闭的开关数

双倍经验：P2574 XOR的艺术

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=2e5+10;
 4 int n,m;
 5 struct tree
 6 {
 7     int l,r;
 8     int sum;
 9     int teg;//懒标记(没有用bool型) 
10 }s[maxn*4];
11 void pushup(int pos){s[pos].sum=s[pos*2].sum+s[pos*2+1].sum;}
12 void build(int pos,int l,int r)
13 {
14     s[pos].l=l;s[pos].r=r;s[pos].sum=s[pos].teg=0;//开关初始全是关的 
15     if(l==r)    return;
16     int mid=(l+r)/2;
17     build(pos*2,l,mid);build(pos*2+1,mid+1,r);
18 }//标准的建树操作 
19 void pushdown(int pos)
20 {
21     if(s[pos].teg)//如果懒标记为true
22     {
23         s[pos].teg=0;
24         s[pos*2].teg^=1;s[pos*2+1].teg^=1;//左右子树的懒标记对1异或 
25         s[pos*2].sum=s[pos*2].r-s[pos*2].l+1-s[pos*2].sum;
26         s[pos*2+1].sum=s[pos*2+1].r-s[pos*2+1].l+1-s[pos*2+1].sum;//更新方法同change 
27     }
28 }
29 void change(int pos,int l,int r)
30 {
31     if(s[pos].l>=l&&s[pos].r<=r)
32     {
33         s[pos].sum=(s[pos].r-s[pos].l+1)-s[pos].sum;//区间开个数变成区间关个数 
34         s[pos].teg^=1;//懒标记与1异或 
35         return ;
36     }
37     pushdown(pos);//懒标记下传 
38     int mid=(s[pos].l+s[pos].r)/2;
39     if(mid>=l)  change(pos*2,l,r);if(mid<r) change(pos*2+1,l,r);
40     pushup(pos);//更新节点值 
41 }
42 int ask(int pos,int l,int r)
43 {
44     if(s[pos].l>=l&&s[pos].r<=r)    return s[pos].sum;
45     pushdown(pos);
46     int mid=(s[pos].l+s[pos].r)/2,val=0;
47     if(l<=mid)   val+=ask(pos*2,l,r);
48     if(r>mid)   val+=ask(pos*2+1,l,r);
49     return val;
50 }//和模板完全一直的区间查询 
51 int main()
52 {
53     cin>>n>>m;build(1,1,n);
54     while(m--)
55     {
56         int opt,x,y;
57         cin>>opt>>x>>y;
58         if(!opt)    change(1,x,y);
59         else    cout<<ask(1,x,y)<<endl;//按照题目要求进行操作 
60     }
61     return 0;代码

代码

2、守墓人 

纯模板线段树。

维护区间和。

支持区间和单点修改和查询

3、忠诚

也是纯模板线段树。

维护区间最值。

支持区间最值查询。

其实线段树的黄题大多数都是不需要思维的模板题，所以只需要熟悉最基本的操作就行，无需过多刷题。

————THE END

 by AIskeleton 2021/12/22