发布时间：2024-08-23

树状数组

二维树状数组

• 实现区间加与区间查询
• $b_{i,j}$ 表示二维差分
• 总和： $\sum_{i=1}^x \sum_{j=1}^y \sum_{ii=1}^x \sum_{jj=1}^y b_{ii,jj}=\sum_{i=1}^x \sum_{j=1}^y b_{i,j}(x-i+1)(y-j+1)= (xy+x+y+1)\sum b_{i,j}-(x+1) \sum j \cdot b_{i,j}-(y+1) \sum i \cdot b_{i,j}+\sum i \cdot j \cdot b_{i,j}$
• 维护四个数组即可

int b[N][N],c[N][N],d[N][N],e[N][N];
//c:j*b[i][j]
//d:i*b[i][j]
//e:i*j*b[i][j]
void solve(){
    char ch;
    int n,m;
    cin>>ch>>n>>m;
    auto add=[&](int x,int y,int val,auto &arr){
        for(int i=x;i<=n;i+=i&-i){
            for(int j=y;j<=m;j+=j&-j)arr[i][j]+=val;
        }
    };
    auto query=[&](int x,int y,auto &arr){
        int ans=0;
        if(x==0||y==0)return 0;
        for(int i=x;i;i&=i-1){
            for(int j=y;j;j&=j-1)ans+=arr[i][j];
        }
        return ans;
    };
    auto query_ans=[&](int x,int y){
        return (x+y+1+x*y)*query(x,y,b)-(x+1)*query(x,y,c)-(y+1)*query(x,y,d)+query(x,y,e);
    };
    auto getsum=[&](int x1,int y1,int x2,int y2){
        return query_ans(x2,y2)-query_ans(x2,y1-1)-query_ans(x1-1,y2)+query_ans(x1-1,y1-1);
    };
    auto ADD=[&](int x,int y,int val){
        add(x,y,val,b);
        add(x,y,val*y,c);
        add(x,y,val*x,d);
        add(x,y,val*x*y,e);
    };
    while(cin>>ch){
        int x1,x2,y1,y2,nums;
        cin>>x1>>y1>>x2>>y2;
        if(ch=='L'){
            cin>>nums;
            ADD(x2+1,y2+1,nums);
            ADD(x1,y2+1,-nums);
            ADD(x2+1,y1,-nums);
            ADD(x1,y1,nums);
        }
        else{
            cout<<getsum(x1,y1,x2,y2)<<"\n";
        }
    }
}

区间所有子区间异或和

• 1 i j把a[i]修改为j
• 2 l r询问区间内所有子区间的异或和
• 结论：
  • 如果l,r区间奇偶性不同，所有数出现偶数次，答案为0
  • 否则与l,r同奇偶的数产生贡献
• 两个树状数组维护

struct BIT{
    vector<int> c;
    int n;
    BIT(){}
    BIT(int n):n(n){
        c=vector<int> (n+1);
    }
    void add(int x,int y){
        for(int i=x;i<=n;i+=i&-i)c[i]^=y;
    }
    int query(int x){
        int ans=0;
        for(int i=x;i;i&=i-1){
            ans^=c[i];
        }
        return ans;
    }
} t[2];
void solve(){
    int n,q;
    cin>>n>>q;
    vector<int> a(n+1);
    for(int i=0;i<2;i++)t[i]=BIT(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        t[i&1].add(i,a[i]);
    }
    while(q--){
        int op,x,y;
        cin>>op>>x>>y;
        if(op==1){
            t[x&1].add(x,a[x]^y);
            a[x]=y;
        }
        else{
            if(x%2!=y%2)cout<<"0\n";
            else cout<<(t[x&1].query(x-1)^t[x&1].query(y))<<"\n";
        }
    }
}

二维区间异或和

• 操作：区间异或，查询区间异或和
• 结论：$b_{i,j}$ 只对与它奇偶性相同的下标有贡献

int t[2][2][1010][1010];
int n,m;
void add(int x,int y,int val){
    for(int i=x;i<=n;i+=i&-i){
        for(int j=y;j<=n;j+=j&-j)t[x&1][y&1][i][j]^=val;
    }
}
int query(int x,int y){
    int ans=0;
    for(int i=x;i;i&=i-1){
        for(int j=y;j;j&=j-1)ans^=t[x&1][y&1][i][j];
    }
    return ans;
}
void solve(){
    cin>>n>>m;
    while(m--){
        int op,x1,y1,x2,y2,val;
        cin>>op>>x1>>y1>>x2>>y2;
        if(op==1){
            cout<<(query(x2,y2)^query(x2,y1-1)^query(x1-1,y2)^query(x1-1,y1-1))<<"\n";
        }
        else{
            cin>>val;
            add(x2+1,y2+1,val);
            add(x1,y2+1,val);
            add(x2+1,y1,val);
            add(x1,y1,val);
        }
    }
}