区间异或的计算_区间异或和

区间异或

1.基础知识

​ 1.对于区间异或 我们可以 仿照 前缀和的思路 对于前缀和 我们假设 原始数组为$a[N]$ 那么前缀和 数组的公式可以写成
$$pret[i]=pret[i-1]+pret[i]$$
​ 而对于比如 求解 区间 [l,r]的和 我们可以由以下的公式求解
$$ans=pret[j]-pret[i-1];$$
​ 对于异或运算 我们可以类比 一下前缀和的加法运算 用一个前缀和数组 来记录整个的 异或 和

​ 但是 异或和 有一个问题 就是我们还原的时候应该怎么还原

​ 对于这个问题 我们可以证明一下 请看以下的三个公式
$$\begin{gathered} a\oplus b=c \\ 两边同时异或上b等式仍然成立 \\ a\oplus b\oplus b=c\oplus b \\ 异或满足结合律a\oplus (b\oplus b)=c\oplus b \end{gathered}$$
​ 这样我们就可以得到一个很神奇的结论
$$\begin{gathered} a\oplus b=ca=b\oplus c \\ 其实异或运算最重要的性质就是自己和自己异或等于0以及异或满足结合律 \\ 我们做题的思路也是源于此 \end{gathered}$$
​ 那么我们的 前缀和 取一个 $[l,r]$的 区间 我们就可 采用以下的公式

​ 然后 我们可以这么理解
$$\begin{gathered} pret[r]=a_1\oplus a_2\oplus a_3\oplus \cdots \oplus a_r \\ pret[l-1]=a_1\oplus a_2\cdots \oplus a_{l-1} \\ 我们要求解a_l\oplus a_{l+1}\dots a_r \\ 那么我们的pret[l-1]\oplus pret[r]那么就是ans \\ 我们完全可以看作他们两个异或是a_1和a_1结合等于0这样以此类推最后得到结果 \\ 所以异或的前缀和完美解决 \end{gathered}$$

2.例题

https://codeforces.com/contest/1872/problem/E

//变量ans代表所有为1 的数异或的结果 对于为0的数异或的结果 我们可以 让ans和整个区间做异或 因为 这样为1的会自己和自己异或
//对于改变操作 我们只需要 让ans和这个区间再做一次异或 这样相同的异或就会消掉 不同的 就会得到计算 
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+100;
int a[N];
long long int pret[N];
string s;
void solve()
{
    int n;
    cin>>n;
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }   
    cin>>s;
    long long int ans=0;
    for(int i=1;i<=s.length();i++)
    {
        if(s[i-1]=='1'){
            ans=ans^a[i];
        }
        pret[i]=pret[i-1]^a[i];


    }
    int q;
    cin>>q;
    while(q--)
    {
        int op;
        cin>>op;
        if(op==1){

            int l,r;
            cin>>l>>r;
            ans=ans^(pret[r]^pret[l-1]);


        }   
        else 
        {
            int x;
            cin>>x;
            if(x==1)
            cout<<ans<<" ";
            else 
            {
                int res=ans^pret[n]^pret[0];
                cout<<res<<" ";


            }


        }



    }
    




}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();



    }

}
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
78
79
80
81
82

​