//暴力做法 枚举每个子区间 O(n^3)
//优化1 利用前缀异或和快速求出区间异或和 O(n^2) 
//优化2 处理位运算的常用方法：拆位法  常用的思想：贡献法思想

下面详见优化2：

1.拆位贡献法 

 

 

2.实战真题1 

题目链接：1.异或和之和 - 蓝桥云课

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{int n;cin>>n;vector<int>a(n);for(int i=0; i<n; i++){cin>>a[i];}int result=0;for(int i=20; i>=0; i--) //遍历位数 {int s=0,n0=1,n1=0; //s表示前缀和，n0表示偶数个数（保证奇数本身占1），n1奇数个数 for(int j=0; j<n; j++){int bit=(a[j]>>i)&1; //按位&，逐位判断0或1，计算贡献 s+=bit;  if(s%2) //奇数 {result+=(1<<i)*n0; //合法个数(2^n0)*合法区间 n1++;}else{result+=(1<<i)*n1;n0++;}}}cout<<result<<endl;return 0;
}

3.实战真题2 

初步掌握之和再练习一道题，题目链接： 19.区间异或的和 - 蓝桥云课

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
signed main()
{int n;cin>>n;vector<int>a(n);for(int i=0; i<n; i++){cin>>a[i];}int result=0;for(int i=30; i>=0; i--) //遍历位数 {int s=0,n0=1,n1=0; //s表示前缀和，n0表示偶数个数（保证奇数本身占1），n1奇数个数 for(int j=0; j<n; j++){int bit=(a[j]>>i)&1; //按位&，逐位判断0或1，计算贡献 s+=bit;  if(s%2) //奇数 {result+=((1<<i)*n0)%mod; //合法个数(2^n0)*合法区间 n1++;}else{result+=((1<<i)*n1)%mod;n0++;}}}cout<<result<<endl;return 0;
}