-
如果a ^ b=c，则c ^ a=b，c ^ b=a
-
a ^ b=b ^ a，(a ^ b) ^ c=a ^ (b ^ c)
-
a ^ b ^ b=a
-
0 ^ a=a，a ^ a=0
数据：
n ：数列长度
m ：询问次数
a[] : 原数列
c[] ：树状数组
函数 ：
a[x]修改为y
void add(int x,int y)
{
int i=x;
while(i<=n)
{
c[i]^=a[x]; //还原，性质3
c[i]^=y;
i+=lowbit(i);
}
a[x]=y;
}
//另一种写法
void add(int x,int y)
{
int w=a[x];
while(x<=n)
{
c[x]^=w;
c[x]^=y;
x+=lowbit(x);
} //因为x的值变了，所以a[x]=y写函数外面
} //一定要记得修改a[x]！！！
x的前缀和
int gs(int x)
{
int s=0;
while(x)
{
s^=c[x];
x-=lowbit(x);
}
return s;
}
初始化 ： 全0
输入
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
for(int j=i;j>i-lowbit(i);--j)
{
c[i]^=a[j]; //性质4
}
}
最终代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[114514],c[114514];
int lowbit(int x)
{
return x&-x;
}
void add(int x,int y)
{
int w=a[x];
while(x<=n)
{
c[x]^=w;
c[x]^=y;
x+=lowbit(x);
}
}
int gs(int x)
{
int s=0;
while(x)
{
s^=c[x]; //可见就是非常简单的把+换成^
x-=lowbit(x);
}
return s;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
for(int j=i;j>i-lowbit(i);--j)
{
c[i]^=a[j];
}
}
for(int i=1;i<=m;++i)
{
int k,x,y;
scanf("%d%d%d",&k,&x,&y);
if(k==0)
{
add(x,y);
a[x]=y; //因为忘了写导致变成18+，望周知
}
if(k==1)
{
int ans=gs(y)^gs(x-1);
printf("%d\n",ans);
}
}
}