【我的板子】线段树（区间加、异或）_区间加区间异或

简述

线段树原理也懒得写了，我主要是来记板子的。
适用于：用O(logn)实现区间修改和查询问题
用法：我一般是弄个结构体数组，里面存需要查询的区间和、区间最大值、区间最小值、区间乘积、加标记，乘标记，异或标记等题目提到的东西。(有的板子也把当前节点包含的左右范围写出来，我，，不写）
注意：
1、申请空间一般是他给的数组大小的四倍。
2、只申请这一个树的空间也不行，还得有一个数组去存原数据。
3、pushdown的时候要注意：懒标记是对于孩子起作用的，对自己不起作用，而且懒标记下移给孩子之后，自己的懒标记要归0。
4、我一般传的参数比较多，当前节点，当前节点包含左右范围，需要修改的区间范围，更新的时候还有需要加/减/乘/除的大小。

例题+注释

洛谷题：XOR的艺术

一、题目描述

AKN 觉得第一题太水了，不屑于写第一题，所以他又玩起了新的游戏。在游戏中，他发现，这个游戏的伤害计算有一个规律，规律如下
拥有一个伤害串，是一个长度为 n 的只含字符 0 和字符 1 的字符串。规定这个字符串的首字符是第一个字符，即下标从 1 开始。
给定一个范围 [l,r]，伤害为伤害串的这个范围内中字符 1 的个数
会修改伤害串中的数值，修改的方法是把 [l, r] 中所有原来的字符 0 变成 1，将 1 变成 0。

AKN 想知道一些时刻的伤害，请你帮助他求出这个伤害。

输入格式

输入的第一行有两个用空格隔开的整数，分别表示伤害串的长度 n，和操作的个数 m。
输入第二行是一个长度为 n 的字符串 S，代表伤害串。
第 3 到第 (m+2) 行，每行有三个用空格隔开的整数 op,l,r。代表第 i 次操作的方式和区间，规则是：
若 op = 0，则表示将伤害串的 [l, r] 区间内的 0 变成 1，1 变成 0。
若 op = 1，则表示询问伤害串的 [l, r] 区间内有多少个字符 1。
输出格式
对于每次询问，输出一行一个整数，代表区间内 1 的个数。
题目分析
这个就只涉及区间中1的个数，所以结构体里面弄了一个sum来存线段树某节点包含的原数组范围中的1的个数，因为涉及区间修改，所以还要弄懒标记，这个题里面是1变0,0变1，我们发现，相当于对原数组某区间元素进行异或1变化，且异或偶数次相当于不变，异或奇数次相当于全取反，那么该区间里面1的个数就变为原来该区间0的个数，即为区间长度-原区间1的个数。

#include <bits/stdc++.h>
#define maxx 300020
#define ll long long
#define iof ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int a[200004];
struct node
{
    int sum;
    int lazy;
}A[800004];
int n,m;
void build(int l,int r,int nb)//当前下标的左右范围，当前下标
{
    A[nb].lazy=0;
    if(l==r){A[nb].sum=a[l];return ;}
    int mid=(l+r)>>1;
    build(l,mid,nb<<1);
    build(mid+1,r,nb<<1|1);
    A[nb].sum=A[nb<<1].sum+A[nb<<1|1].sum;
    return ;
}
void pushdown(int nb,int l,int r)//当前下标，当前下标的左右范围
{
    //看他父亲那标记要异或的是偶数次还是奇数次，偶数次就不变，奇数次就变为改
    int mid=(l+r)>>1;
    A[nb<<1].sum=(A[nb].lazy&1)?(mid-l+1-A[nb<<1].sum):A[nb<<1].sum;
    A[nb<<1|1].sum=(A[nb].lazy&1)?(r-mid-A[nb<<1|1].sum):A[nb<<1|1].sum;
    A[nb<<1].lazy+=A[nb].lazy;
    A[nb<<1|1].lazy+=A[nb].lazy;
    A[nb].lazy=0;
    return ;
}
void update(int nb,int l,int r,int L,int R)//当前下标，当前下标的实际左右，需修改区间左右（数值增加的时候这里再传一个参数k，表示该区间每个数都增加的大小）
{
    if(l>R||r<L)return ;
    if(l>=L&&r<=R)
    {
        A[nb].sum=r-l+1-A[nb].sum; 
        A[nb].lazy++;
       return ;
    }
    pushdown(nb ,l,r);
    int mid=(l+r)>>1;
    update(nb<<1,l,mid,L,R);
    update(nb<<1|1,mid+1,r,L,R);
    A[nb].sum=A[nb<<1].sum+A[nb<<1|1].sum;
    return ;
}
ll quary(int nb,int l,int r,int L,int R)//当前下标，当前节点左右，需查询区间左右
{
    if(l>R||r<L)return 0;
    if(l>=L&&r<=R)
    {
        return A[nb].sum;
    }
    pushdown(nb,l,r);
    int mid=(l+r)>>1;
    return  quary(nb<<1,l,mid,L,R)+quary(nb<<1|1,mid+1,r,L,R);
}
int main()
{
    iof;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        char x;cin>>x;
        a[i]=x-'0';//初始化原数组
    }
    build(1,n,1);//建树
    for(int i=1;i<=m;++i)
    {
        int op,l,r;cin>>op>>l>>r;
        if(op==0)update(1,1,n,l,r);//当前下标，当前节点左右，需修改区间左右
        else cout<<quary(1,1,n,l,r)<<endl;//当前下标，当前节点左右，需查询区间左右
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

二、推荐简单模板例题

区间内数值加并查询区间和模板
区间内数值加和乘并查询区间和模板