CF242E XOR on Segment （拆位线段树）

题目链接
题目大意：

总体思路：
这题是动态的区间修改和区间求和，毫无疑问要用到线段树进行操作。但是普通的线段树无法进行区间异或操作。
通常遇见异或问题一般两种思路。
1、做异或前缀和。
2、就是拆位。01Trie就是这种思想的一个体现。
我们可以发现异或运算的两个性质：
1、 0、1异或0，原来的数保持不变
2、 0、1异或1，原来的数翻转
于是这题可以用20棵线段树分别维护每一个位置上的数。这样就变成了维护一个01串，操作就是区间异或0和1，区间询问1的个数，这是个经典的区间翻转问题。后面差不多就是一个裸的线段树了，注意细节就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
int x;
int ch,l,r;
struct ty{
    int l,r;
    int val;//记录区间1的个数 
    int lazy;
    ty():l(0),r(0),val(0),lazy(0){} 
};
int g[25][100005];
ty tr[25][100005*4];//每一位建立20棵线段树 
void pushup(int i,int u){
    tr[i][u].val=tr[i][u<<1].val+tr[i][u<<1|1].val;
    return ;
}
void build(int i,int u,int l,int r){
    tr[i][u].l=l; tr[i][u].r=r;
    if(l==r){
        //if(i==0){
            //cout<<"g["<<i<<"]["<<l<<"]="<<g[i][l]<<"\n";
        //}
        tr[i][u].val=g[i][l];
        //cout<<"l="<<l<<" r="<<r<<"\n";
        //cout<<"tr["<<i<<"]["<<u<<"].val="<<tr[i][u].val<<"\n";
        return ;
    }
    int mind=(l+r)>>1;
    build(i,u<<1,l,mind);
    build(i,u<<1|1,mind+1,r);
    pushup(i,u);
    //cout<<"l="<<l<<" r="<<r<<"\n";
    //cout<<"tr["<<i<<"]["<<u<<"].val="<<tr[i][u].val<<"\n";
    return ;
}
void pushdown(int i,int u){
    if(tr[i][u].lazy){
        tr[i][u<<1].val=(tr[i][u<<1].r-tr[i][u<<1].l+1)-tr[i][u<<1].val;//进行区间翻转操作
        tr[i][u<<1|1].val=(tr[i][u<<1|1].r-tr[i][u<<1|1].l+1)-tr[i][u<<1|1].val;
        tr[i][u<<1].lazy^=1; tr[i][u<<1|1].lazy^=1;
        tr[i][u].lazy=0;
    }
    return ;
}
int query(int i,int u,int l,int r){
    if(tr[i][u].l>=l&&tr[i][u].r<=r){
        return tr[i][u].val;
    }
    pushdown(i,u);
    int mind=(tr[i][u].l+tr[i][u].r)>>1;
    int cnt=0;
    if(l<=mind) cnt+=query(i,u<<1,l,r);
    if(r>mind) cnt+=query(i,u<<1|1,l,r);
    return cnt;
}
void modify(int i,int u,int l,int r,int x){
    if(tr[i][u].l>=l&&tr[i][u].r<=r){
        tr[i][u].val=(tr[i][u].r-tr[i][u].l+1)-tr[i][u].val;
        tr[i][u].lazy^=1;
        return ; 
    }
    pushdown(i,u);
    int mind=(tr[i][u].l+tr[i][u].r)>>1;
    if(l<=mind) modify(i,u<<1,l,r,x);
    if(r>mind) modify(i,u<<1|1,l,r,x);
    pushup(i,u);
    return ;
}
int main(){
    scanf(" %d",&n);
    for(int i=1;i<=n;i++){
        scanf(" %d",&x);
        for(int j=0;j<=19;j++){
            int t=x>>j&1;
            g[j][i]=t;
        }
    } 
    for(int i=0;i<=19;i++) build(i,1,1,n);
    scanf(" %d",&m);
    for(int i=1;i<=m;i++){
        scanf(" %d %d %d",&ch,&l,&r);
        if(ch==1){
            ll ans=0;
            for(int j=0;j<=19;j++) {
                ans+=query(j,1,l,r)*(1ll<<j);
                //cout<<query(j,1,l,r)<<"\n";
            }
            printf("%lld\n",ans);
        }
        else{
            scanf(" %d",&x);
            for(int j=0;j<=19;j++){
                int t=x>>j&1;
                if(t==0) continue;
                modify(j,1,l,r,1);
            }
        }
    }
    return 0;
}