题目链接

https://ac.nowcoder.com/acm/problem/15172

题目大意

矩阵由0，1构成，n行n列；m次询问，操作数为1时，对某个坐标处的数值翻转，即0变1，1变0；操作数为2时，求一个坐标为子矩阵左上角坐标，另一个坐标为子矩阵右上角坐标的子矩阵和并输出。

解题思路

我的思路:

二维数组a，表示每个灯泡的状态；二维数组c，为树状数组。
a[i][j]表示第i行第j个灯泡的状态，c[i][j]表示第i行所处的树状数组，举例：c[1]表示第一行树状数组首地址，也就是每行有独立的树状数组存储。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
bool a[N][N];
int c[N][N];
int n,m;
int lowbit(int x){
    return x&(-x);
}
void update(int x,int y){
    int f;
    if(a[x][y]) f=-1;//进入前为亮，翻转后，变为灭，所以c数组要进行-1操作
    else f=1;
    a[x][y]^=1;//取反；在输入阶段，也是对a数组的赋值
    while(y<=n){
        c[x][y]+=f;
        y+=lowbit(y);
    }
}
int getsum(int x,int y){
    int sum=0;
    while(y>0){
        sum+=c[x][y];
        y-=lowbit(y);
    }
    return sum;
}
int main(){
    cin>>n>>m;
    //init
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            bool tmp;
            cin>>tmp;
            if(tmp) update(i,j);
        }
    for(int i=1;i<=m;i++){
        int op;
        cin>>op;
        if(op==1){
            int x,y;
            cin>>x>>y;
            update(x,y);
        }
        else{
            int sum=0;
            int x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            if(x1>x2) swap(x1,x2);//对于本题的数据而言可有可无
            if(y1>y2) swap(y1,y2);//同上
            for(int i=x1;i<=x2;i++)//每行累加
                sum+=getsum(i,y2)-getsum(i,y1-1);
            cout<<sum<<endl;
        }
    }
}

大佬思路

一维数组，a，c还是一样的意义，通过二维数组转变为一维数组，其实本质还是不变的。
输出结果，还是要每行累加。
注意列序号不能从0开始了，行序号可以从0开始，因为在通过前缀和求一段区间的和的时候，假如区间左端点包含0，那么答案应该为（右端点位置）的值-（左端点-1位置）的值，但是不存在数组索引不存在-1，稍微注意一下。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+50;
int a[N];
int c[N];
int n,m;
int lowbit(int x){
    return x&-x;
}
void update(int x,int add){
    while(x<=n*n){
        c[x]+=add;
        x+=lowbit(x);
    }
}
int getsum(int x){
    int sum=0;
    while(x>0){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int endans(int s,int b){
    return getsum(b)-getsum(s-1);
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=1;j<=n;j++){
            cin>>a[i*n+j];
            if(a[i*n+j]==1) update(i*n+j,1); 
        }

    for(int i=1;i<=m;i++){
        int op;
        cin>>op;
        if(op==1){
            int x,y;
            cin>>x>>y;
            if(a[(x-1)*n+y]==1) {a[(x-1)*n+y]=0;update((x-1)*n+y,-1);}
            else {a[(x-1)*n+y]=1;update((x-1)*n+y,1);}
        }
        else{
            int ans=0;
            int x1,x2,y1,y2;
            cin>>x1>>y1>>x2>>y2;
            if(x1>x2) swap(x1,x2);
            if(y1>y2) swap(y1,y2);
            for(int i=x1-1;i<x2;i++)
                ans+=endans(i*n+y1,i*n+y2);
            cout<<ans<<endl;
        }
    }
}