主要要理解异或的运算性质,找到规律后用树状数组可以很容易解决
首先找规律发现当l,r奇偶性相同,有贡献的就是l,l+2,l+4…r,因为其他的都是出现偶数次,因为a^a=0,所以偶数次异或结果也为0.当奇偶性不同是,都是偶数,就是0。
然后更新,树状数组只能加,不能减,修改一个数字,先要把原来地方的数字变成0,对应异或操作就是异或自己,然后0^a=a,就是异或要变成的值,完成修改
关于查询,我们仍然可以用前缀和思想,查询l-r,就是q(r)^q(l-1) <==> (把q(r)拆成两部分,s[a-b]表示,区间a-b的异或结果)s[l-r]^s[0-l-1]^s[0-l-1],然后异或满足交换律,后面两个一样异或结果就是0,然后0^a=a,就是得s[l-r]我们想要的值
所以本题我们要维护两个树状数组,一个维护奇数序列,一个维护偶数序列
#include<iostream>
#include<cstring>
#include<algorithm>
#define lowbit(x) x&-x
//#define int long long
#define x first
#define y second
using namespace std;
const int N = 2e5+10;
int tr1[N],tr2[N];
int w[N];
int n,m;
void add(int tr[],int x,int v){
for(int i=x;i<=n;i+=lowbit(i))tr[i]^=v;
}
int query(int tr[],int x){
int res=0;
for(int i=x;i;i-=lowbit(i))res^=tr[i];
return res;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
if(i&1)add(tr1,i,w[i]);
else add(tr2,i,w[i]);
}
while(m--){
int op,a,b;scanf("%d%d%d",&op,&a,&b);
if(op==1){
if(a&1)add(tr1,a,w[a]),add(tr1,a,b),w[a]=b;
else add(tr2,a,w[a]),add(tr2,a,b),w[a]=b;
}else{
if((a&1)==(b&1)){
if(a&1)cout<<(query(tr1,b)^query(tr1,a-1))<<'\n';
else cout<<(query(tr2,b)^query(tr2,a-1))<<'\n';
}else puts("0");
}
}
return 0;
}