区间修改矩阵与查询（树状数组）

题意&＃xff1a;

给定矩阵大小&＃xff0c;一开始全部元素都为0。操作1将一块区域取反&＃xff1b;操作2回答区域有多少个1.

做法&＃xff1a;

树状数组维护二维差分&＃xff0c;将区间操作变为单点操作。

是差分数组。

差分数组的前缀和就是单点的值&＃xff0c;而这里求的是区间的值&＃xff0c;那就是差分数组前缀和后&＃xff0c;变为单点的值&＃xff0c;单点的前缀和才是区间的值。就是下面这个式子了。这个式子的意思是的前缀和。

为了方便维护&＃xff0c;拆分为这四个式子。

类比一维的树状数组&＃xff0c;表示右端点为&＃xff0c;长为的区间和。

二维的那就是&＃xff0c;表示右下角为&＃xff0c;高&＃xff0c;宽的区间的区间和。

所以树状数组也就能进行二维的快速单点修改&＃xff0c;区间查询了。

单点修改&＃xff0c;需要改四个树状数组&＃xff1a;

void point_add(int x, int y, int val)
{add(1, x, y, val);add(2, x, y, val * x);add(3, x, y, val * y);add(4, x, y, val * x * y);
}

 而一次区间加&＃xff0c;需要转化为四个单点修改。至于为什么是四个点&＃xff0c;可以看这个博客&＃xff1a;二维差分

point_add(x1, y1, val);
point_add(x1, y2 &＃43; 1, -val);
point_add(x2 &＃43; 1, y1, -val);
point_add(x2 &＃43; 1, y2 &＃43; 1, val);

单点查询&＃xff0c;查的是的前缀和&＃xff1a;

int point_que(int x, int y)
{int ans &＃61; 0;ans &＃43;&＃61; que(1, x, y) * (x &＃43; 1) * (y &＃43; 1);ans -&＃61; que(2, x, y) * (y &＃43; 1);ans -&＃61; que(3, x, y) * (x &＃43; 1);ans &＃43;&＃61; que(4, x, y);return ans;
}

区间查询太简单&＃xff0c;就是二维前缀和&＃xff0c;这里不放了。

放一下这题的代码&＃xff1a;

#include
#define int long long
using namespace std;
const int mod &＃61; 2, N &＃61; 1000 &＃43; 5;
int c[5][N][N];
int n, m;
void add(int k, int x, int y, int val)
{for (int i &＃61; x; i <&＃61; n; i &＃43;&＃61; i & -i)for (int j &＃61; y; j <&＃61; m; j &＃43;&＃61; j & -j){c[k][i][j] &＃43;&＃61; val;c[k][i][j] %&＃61; mod;}
}
int que(int k, int x, int y)
{int sum &＃61; 0;for (int i &＃61; x; i; i -&＃61; i & -i)for (int j &＃61; y; j; j -&＃61; j & -j) sum &＃43;&＃61; c[k][i][j];return sum % mod;
}
void point_add(int x, int y, int val)
{add(1, x, y, val);add(2, x, y, val * x);add(3, x, y, val * y);add(4, x, y, val * x * y);
}
int point_que(int x, int y)
{int ans &＃61; 0;ans &＃43;&＃61; que(1, x, y) * (x &＃43; 1) * (y &＃43; 1);ans -&＃61; que(2, x, y) * (y &＃43; 1);ans -&＃61; que(3, x, y) * (x &＃43; 1);ans &＃43;&＃61; que(4, x, y);return ans;
}
signed main()
{scanf("%lld%lld", &n, &m);int q;cin>>q;int op;while (q--){cin>>op;if (op &＃61;&＃61; 1){int x1, y1, x2, y2, val;val &＃61; 1;scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);point_add(x1, y1, val);point_add(x1, y2 &＃43; 1, -val);point_add(x2 &＃43; 1, y1, -val);point_add(x2 &＃43; 1, y2 &＃43; 1, val);}else{int x1, y1, x2, y2;scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);int ans &＃61; 0;ans &＃43;&＃61; point_que(x2, y2);ans -&＃61; point_que(x1 - 1, y2);ans -&＃61; point_que(x2, y1 - 1);ans &＃43;&＃61; point_que(x1 - 1, y1 - 1);printf("%lld\n", (ans % mod &＃43; mod) % mod);}}return 0;
}