BIT是最容易扩展到高维的数据结构了，对于一维(单点修改+区间查询)，我们是这样搞得……

#define lowbit(x) ((x)&(-(x)))
void update(int pos,int val)
{
	for(int i=pos;i<=n;i+=lowbit(i)) sum[i]+=val;
}
int query(int pos)
{
	int ret=0;
	for(int i=pos;i;i-=lowbit(i)) ret+=sum[i];
	return ret;
}
int getsum(int l,int r)
{
	return query(r)-query(l-1);
}

单点修改+区间查询

至于二维，容斥一下。

#define lowbit(x) ((x)&(-(x)))
void update(int x,int y,int val)
{
	for(int i=x;i<=n;i+=lowbit(i))
	{
		for(int j=y;j<=n;j+=lowbit(j))
		{
			f[i][j]+=val;
		}	
	}
}
int query(int x,int y)
{
	int ret=0;
	for(int i=x;i;i-=lowbit(i))
	{
		for(int j=y;j;j-=lowbit(j))
		{
			ret+=f[i][j];
		}
	}
	return ret;
}
int getsum(int x1,int y1,int x2,int y2)
{
	return query(x2,y2)+query(x2,y1-1)+query(x1-1,y2)-query(x1-1,y1-1);
}

区间修改+单点查询

和一维一样差分。

每次修改红色区域，用类似前缀和的思想。

$$update(x1,y1,1); update(x1,y2+1,-1); update(x2+1,y1,-1); update(x2+1,y2+1,1);$$

#define lowbit(x) ((x)&(-(x)))
void update(int x,int y,int val)
{
	for(int i=x;i<=n;i+=lowbit(i))
	{
		for(int j=y;j<=n;j+=lowbit(j))
		{
			f[i][j]+=val;
		}	
	}
}
int query(int x,int y)
{
	int ret=0;
	for(int i=x;i;i-=lowbit(i))
	{
		for(int j=y;j;j-=lowbit(j))
		{
			ret+=f[i][j];
		}
	}
	return ret%2;
}
void UP(int x1,int y1,int x2,int y2)
{
	update(x1,y1,1);
	update(x1,y2+1,-1);
	update(x2+1,y1,-1);
	update(x2+1,y2+1,1);
}