树状数组 POJ-2155 Matrix 题目链接：[ POJ - 2155 ] 题目大意 对一个n∗n的矩阵： 格式C x1 y1 x2 y2，表示将左上角为(x1,y1)，右下角为(x2,y2)的矩阵全部取反，即0变1，1变0. Q x y，表示查询位置(x,y)的值. 设询问次数为t，则10^3, 1 ≤ t ≤ 10^5, 数据组数 ≤ 10. 题解 树状数组模板题，此题建立完整的二维树状数组板子 代码如下 #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<string> #include<vector> using namespace std; typedef long long ll; ll a[1010][1010]; ll t, m, n; inline ll lowbit(ll x) { return x & -x; } ll sum(ll x, ll y) { ll res = 0; for (ll i = x; i > 0; i -= lowbit(i)) for (ll j = y; j > 0; j -= lowbit(j)) res += a[i][j]; return res; } void add(ll x, ll y, ll v) { for (ll i = x; i <= n; i += lowbit(i)) for (ll j = y; j <= n; j += lowbit(j)) a[i][j] += v; } int main(void) { cin >> t; while (t--) { memset(a, 0, sizeof(a)); scanf("%lld%lld", &n, &m); getchar(); char ch; ll x1, y1, x2, y2; while (m--) { scanf("%c %lld %lld", &ch, &x1, &y1); if (ch == 'Q') printf("%lld\n", sum(x1, y1) % 2); if (ch == 'C') { scanf("%lld%lld", &x2, &y2); add(x1, y1, 1); add(x2 + 1, y1, 1); add(x1, y2 + 1, 1); add(x2 + 1, y2 + 1, 1); } getchar(); } if (t) cout << endl; } return 0; }

树状数组 POJ-3468 A Simple Problem with Integers 题目链接：[ POJ - 3468 ] 题目大意 给一个长度为n的数列，有Q次操作Q代表查询区间 a b之间的累加和，操作C代表将a-b区间的所有数加上c 题解 树状数组模板题，此题建立完整的一维树状数组板子 代码如下 #include<iostream> #include<algorithm> #include<cstdio> #include<string> #include<vector> using namespace std; typedef long long ll; ll n, m, k; inline ll lowbit(ll x) { return x & -x; } struct BIT { ll a[500050]; void add(ll x, ll v) { for (x; x > 0; x -= lowbit(x)) a[x] += v; } void addinv(ll x, ll v) { for (ll i = x; i <= n; i += lowbit(i)) a[i] += x * v; } ll Sum(ll x) { ll res = 0; for(x; x <= n; x += lowbit(x)) res += a[x]; return res; } ll Suminv(ll x) { ll res = 0; for (x; x > 0; x -= lowbit(x)) res += a[x]; return res; } }bit, bitinv; ll sum(ll x) { if (x) return bit.Sum(x) * x + bitinv.Suminv(x - 1); else return 0; } void add(ll l, ll r, ll c) { bit.add(r, c); bitinv.addinv(r, c); if (l > 1) { bit.add(l - 1, -c); bitinv.addinv(l - 1, -c); } } int main(void) { scanf("%lld%lld", &n, &m); for (ll i = 1; i <= n; i++) { scanf("%lld", &k); add(i, i, k); } getchar(); char ch; ll l, r, c; while (m--) { scanf("%c %lld %lld", &ch, &l, &r); if (ch == 'Q') printf("%lld\n", sum(r) - sum(l - 1)); if (ch == 'C') { scanf("%lld", &c); add(l, r, c); } getchar(); } return 0; }