给n个数， 两种操作， 一种是求区间内的数的和， 一种是将区间内的数异或x。
异或x没有什么思路， 单个异或肯定超时， 区间异或也没有办法做....后来才知道可以按位建线段树， 这样建20棵线段树就可以。
每一次异或， 对于给定的x， 如果x的第i位是1， 那么就将第i棵线段树在给定的区间内0，1翻转， 这是很基础的操作。
对于区间求和操作， 我们可以求出给定的区间， 从高位到低位， 每一位依次有多少个1， 然后就可以直接求出来， 感觉不好表达....具体看代码。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define pb(x) push_back(x) 4 #define ll long long 5 #define mk(x, y) make_pair(x, y) 6 #define lson l, m, rt<<1 7 #define mem(a) memset(a, 0, sizeof(a)) 8 #define rson m+1, r, rt<<1|1 9 #define mem1(a) memset(a, -1, sizeof(a)) 10 #define mem2(a) memset(a, 0x3f, sizeof(a)) 11 #define rep(i, a, n) for(int i = a; i<n; i++) 12 #define ull unsigned long long 13 typedef pair<int, int> pll; 14 const double PI = acos(-1.0); 15 const double eps = 1e-8; 16 const int mod = 1e9+7; 17 const int inf = 1061109567; 18 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; 19 const int maxn = 1e5+5; 20 int sum[maxn<<2][21], XOR[maxn<<2][21], a[25]; 21 void pushUp(int rt, int pos) { 22 sum[rt][pos] = sum[rt<<1][pos] + sum[rt<<1|1][pos]; 23 } 24 void pushDown(int rt, int m, int pos) { 25 if(XOR[rt][pos]) { 26 sum[rt<<1][pos] = (m-(m>>1)) - sum[rt<<1][pos]; 27 sum[rt<<1|1][pos] = (m>>1)-sum[rt<<1|1][pos]; 28 XOR[rt<<1][pos] ^= 1; 29 XOR[rt<<1|1][pos] ^= 1; 30 XOR[rt][pos] = 0; 31 } 32 } 33 void update(int L, int R, int l, int r, int rt, int pos) { 34 if(L<=l&&R>=r) { 35 XOR[rt][pos] ^= 1; 36 sum[rt][pos] = r-l+1-sum[rt][pos]; 37 return ; 38 } 39 pushDown(rt, r-l+1, pos); 40 int m = l+r>>1; 41 if(L<=m) 42 update(L, R, lson, pos); 43 if(R>m) 44 update(L, R, rson, pos); 45 pushUp(rt, pos); 46 } 47 int query(int L, int R, int l, int r, int rt, int pos) { 48 if(L<=l&&R>=r) { 49 return sum[rt][pos]; 50 } 51 pushDown(rt, r-l+1, pos); 52 int m = l+r>>1, ret = 0; 53 if(L<=m) 54 ret += query(L, R, lson, pos); 55 if(R>m) 56 ret += query(L, R, rson, pos); 57 return ret; 58 } 59 int main() 60 { 61 int n, x, m, y, sign, z; 62 cin>>n; 63 mem(XOR); 64 for(int i = 1; i<=n; i++) { 65 scanf("%d", &x); 66 for(int j = 0; j<21; j++) { 67 if((1<<j)&x) { 68 update(i, i, 1, n, 1, j); 69 } 70 } 71 } 72 cin>>m; 73 while(m--) { 74 scanf("%d", &sign); 75 if(sign==1) { 76 ll tmp = 0; 77 scanf("%d%d", &x, &y); 78 for(int i = 20; i>=0; i--) { 79 tmp = 1ll*tmp*2+query(x, y, 1, n, 1, i); //query是求这个区间里每一位有多少个1 80 } 81 cout<<tmp<<endl; 82 } else { 83 scanf("%d%d%d", &x, &y, &z); 84 for(int j = 0; j<20; j++) { 85 if(z&(1<<j)) { //如果给出的x第j位是1， 那么就将区间内第j棵线段树翻转 86 update(x, y, 1, n, 1, j); 87 } 88 } 89 } 90 } 91 return 0; 92 }