一维BIT（单点更新，区间求和）：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring> using namespace std; const int N = ;
typedef long long LL;
inline int lowbit(int x) { return x & -x;}
struct BIT {
LL s[N], sz;
void init(int n) { sz = n; for (int i = ; i <= n; i++) s[i] = ;}
void add(int x, LL v) { for (x <= ? : x; x <= sz; x += lowbit(x)) s[x] += v;}
LL sum(int x) { LL r = ; for ( ; x > ; x -= lowbit(x)) r += s[x]; return r;}
LL sum(int x, int y) { return sum(y) - sum(x - );}
} bit; int main() {
//freopen("in", "r", stdin);
int n, m, T;
scanf("%d", &T);
for (int cas = ; cas <= T; cas++) {
scanf("%d", &n);
bit.init(n);
int x, y;
char op[];
for (int i = ; i <= n; i++) {
scanf("%d", &x);
bit.add(i, x);
}
printf("Case %d:\n", cas);
while (~scanf("%s", op) && op[] != 'E') {
scanf("%d%d", &x, &y);
if (op[] == 'A') bit.add(x, y);
if (op[] == 'S') bit.add(x, -y);
if (op[] == 'Q') printf("%lld\n", bit.sum(x, y));
}
}
return ;
}
一维BIT（区间求和，区间更新）：
d[i]=a[i]-a[i-1]（查分数组）
sigma{a[i]}=(n+1)*sigma{d[i]}-sigma{d[i]*i}
3468 -- A Simple Problem with Integers
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring> using namespace std; const int N = ;
typedef long long LL;
inline int lowbit(int x) { return x & -x;}
struct BIT {
LL s[N], sz;
void init(int n) { sz = n; for (int i = ; i <= n; i++) s[i] = ;}
void add(int x, LL v) { for (x <= ? : x; x <= sz; x += lowbit(x)) s[x] += v;}
LL sum(int x) { LL r = ; for ( ; x > ; x -= lowbit(x)) r += s[x]; return r;}
} ; struct BIT2 {
BIT a, b;
void init(int n) { a.init(n), b.init(n);}
void add(int x, LL d) { a.add(x, d), b.add(x, x * d);}
void add(int x, int y, LL d) { add(x, d), add(y + , -d);}
LL sum(int x) { return (x + ) * a.sum(x) - b.sum(x);}
LL sum(int x, int y) { return sum(y) - sum(x - );}
} bit; int main() {
//freopen("in", "r", stdin);
int n, m;
while (~scanf("%d%d", &n, &m)) {
bit.init(n);
int x, y, z;
char op[];
for (int i = ; i <= n; i++) {
scanf("%d", &x);
bit.add(i, i, x);
}
while (m--) {
scanf("%s", op);
if (op[] == 'Q') {
scanf("%d%d", &x, &y);
printf("%lld\n", bit.sum(x, y));
}
if (op[] == 'C') {
scanf("%d%d%d", &x, &y, &z);
bit.add(x, y, z);
}
}
}
return ;
}
二维BIT（子矩阵修改，单点查询）：
简单容斥一下，
add(a,b,c,d)=add(c,d)^add(c,b-1)^add(a-1,d)^add(a-1,b-1)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio> using namespace std; const int N = ;
inline int lowbit(int x) { return x & -x;}
struct BIT2D {
bool s[N][N];
int sz;
void init(int n) {
sz = n;
for (int i = ; i <= n; i++) for (int j = ; j <= n; j++) s[i][j] = ;
}
void add(int x, int y) {
int t = y;
for ( ; x > ; x -= lowbit(x)) {
for (y = t; y > ; y -= lowbit(y)) {
s[x][y] ^= ;
}
}
}
void add(int a, int b, int c, int d) {
if (a > c) swap(a, c);
if (b > d) swap(b, d);
add(c, d), add(c, b - ), add(a - , d), add(a - , b - );
}
bool sum(int x, int y) {
int t = y;
bool ret = ;
for (x > ? x : ; x <= sz; x += lowbit(x)) {
for (y = t > ? t : ; y <= sz; y += lowbit(y)) {
ret ^= s[x][y];
}
}
return ret;
}
} bit; int main() {
//freopen("in", "r", stdin);
int T, n, m;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
bit.init(n);
char op[];
int a, b, c, d;
while (m--) {
scanf("%s", op);
if (op[] == 'C') {
scanf("%d%d%d%d", &a, &b, &c, &d);
bit.add(a, b, c, d);
}
if (op[] == 'Q') {
scanf("%d%d", &a, &b);
printf("%d\n", bit.sum(a, b));
}
}
if (T) puts("");
}
}
二维BIT（单点更新，子矩阵查询）：
类似上一题，
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio> using namespace std; const int N = ;
inline int lowbit(int x) { return x & -x;}
struct BIT2D {
int s[N][N];
int sz;
void init(int n) {
sz = n;
for (int i = ; i <= n; i++) for (int j = ; j <= n; j++) s[i][j] = ;
}
void add(int x, int y, int d) {
int t = y;
for (x = x > ? x : ; x <= sz; x += lowbit(x)) {
for (y = t > ? t : ; y <= sz; y += lowbit(y)) {
s[x][y] += d;
}
}
}
int sum(int x, int y) {
int t = y;
int ret = ;
for (; x > ; x -= lowbit(x)) {
for (y = t; y > ; y -= lowbit(y)) {
ret += s[x][y];
}
}
return ret;
}
int sum(int a, int b, int c, int d) {
if (a > c) swap(a, c);
if (b > d) swap(b, d);
return sum(c, d) - sum(c, b - ) - sum(a - , d) + sum(a - , b - );
}
} bit; int main() {
//freopen("in", "r", stdin);
int op, n;
while (~scanf("%d", &op)) {
while (op != ) {
if (op == ) {
scanf("%d", &n);
bit.init(n);
}
int a, b, c, d;
if (op == ) {
scanf("%d%d%d", &a, &b, &c);
a++, b++;
bit.add(a, b, c);
}
if (op == ) {
scanf("%d%d%d%d", &a, &b, &c, &d);
a++, b++, c++, d++;
printf("%d\n", bit.sum(a, b, c, d));
}
scanf("%d", &op);
}
}
return ;
}
二维BIT（子矩阵更新，子矩阵查询）：
a[i][j]——(i,j)-(n,m)增量（差分矩阵）
S[i][j]——(1,1)-(i,j)求和
S[x][y]=sigma{a[i][j]*(x-i+1)*(y-j+1)}=sigma{a[i][j]*(x+1)*(y+1)-(y+1)*a[i][j]*i-(x+1)*a[i][j]*j+a[i][j]*i*j}
令A[x][y]=sigma{a[i][j]}，B[x][y]=sigma{a[i][j]*i}，C[x][y]=sigma{a[i][j]*j}，D[x][y]=sigma{a[i][j]*i*j}。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring> using namespace std; const int N = ;
typedef int LL;
inline int lowbit(int x) { return x & -x;}
struct BIT {
LL s[N][N];
int n, m;
void init(int s1, int s2) {
n = s1, m = s2;
for (int i = ; i <= n; i++) for (int j = ; j <= m; j++) s[i][j] = ;
}
void add(int x, int y, int d) {
int t = y > ? y : ;
for (x = x > ? x : ; x <= n; x += lowbit(x)) {
for (y = t; y <= m; y += lowbit(y)) {
s[x][y] += d;
}
}
}
LL sum(int x, int y) {
LL ret = ;
int t = y > ? y : ;
for ( ; x > ; x -= lowbit(x)) {
for (y = t; y > ; y -= lowbit(y)) {
ret += s[x][y];
}
}
return ret;
}
} ; struct BIT2 {
BIT A, B, C, D;
void init(int n, int m) { A.init(n, m), B.init(n, m), C.init(n, m), D.init(n, m);}
void add(int x, int y, LL k) { // add (x,y)-(n,m)
A.add(x, y, k), B.add(x, y, k * x), C.add(x, y, k * y), D.add(x, y, k * x * y);
}
void add(int a, int b, int c, int d, int k) {
if (a > c) swap(a, c);
if (b > d) swap(b, d);
add(a, b, k), add(a, d + , -k), add(c + , b, -k), add(c + , d + , k);
}
LL sum(int x, int y) { // sum (1,1)-(x,y)
return (x + ) * (y + ) * A.sum(x, y) - (y + ) * B.sum(x, y) - (x + ) * C.sum(x, y) + D.sum(x, y);
}
LL sum(int a, int b, int c, int d) {
if (a > c) swap(a, c);
if (b > d) swap(b, d);
return sum(c, d) - sum(c, b - ) - sum(a - , d) + sum(a - , b - );
}
} bit; int main() {
//freopen("in", "r", stdin);
char op[];
int a, b, c, d, e;
while (~scanf("%s", op)) {
if (op[] == 'X') {
scanf("%d%d", &a, &b);
bit.init(a, b);
}
if (op[] == 'L') {
scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
bit.add(a, b, c, d, e);
}
if (op[] == 'k') {
scanf("%d%d%d%d", &a, &b, &c, &d);
printf("%d\n", bit.sum(a, b, c, d));
}
}
return ;
}
二维BIT（子矩阵更新，子矩阵查询）：
就是为了做这题，把一维和二维的BIT都做了一遍，原理同上题。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring> using namespace std; const int N = ;
typedef long long LL;
inline int lowbit(int x) { return x & -x;}
struct BIT {
LL s[N][N];
int n, m;
void init(int s1, int s2) {
n = s1, m = s2;
for (int i = ; i <= n; i++) for (int j = ; j <= m; j++) s[i][j] = ;
}
void add(int x, int y, LL d) {
int t = y > ? y : ;
for (x = x > ? x : ; x <= n; x += lowbit(x)) {
for (y = t; y <= m; y += lowbit(y)) {
s[x][y] ^= d;
}
}
}
LL sum(int x, int y) {
LL ret = ;
int t = y > ? y : ;
for ( ; x > ; x -= lowbit(x)) {
for (y = t; y > ; y -= lowbit(y)) {
ret ^= s[x][y];
}
}
return ret;
}
} ; struct BIT2 {
BIT A, B, C, D;
void init(int n, int m) { A.init(n, m), B.init(n, m), C.init(n, m), D.init(n, m);}
void add(int x, int y, LL k) { // add (x,y)-(n,m)
A.add(x, y, k);
//cout << x << ' ' << y << ' ' << k << "??" << endl;
if (x & ) B.add(x, y, k);
if (y & ) C.add(x, y, k);
if (x & y & ) D.add(x, y, k);
}
void add(int a, int b, int c, int d, LL k) {
if (a > c) swap(a, c);
if (b > d) swap(b, d);
add(a, b, k), add(a, d + , k), add(c + , b, k), add(c + , d + , k);
}
LL sum(int x, int y) { // sum (1,1)-(x,y)
LL ret = D.sum(x, y);
if ((x ^ ) & (y ^ ) & ) ret ^= A.sum(x, y);
if ((y ^ ) & ) ret ^= B.sum(x, y);
if ((x ^ ) & ) ret ^= C.sum(x, y);
return ret;
}
LL sum(int a, int b, int c, int d) {
if (a > c) swap(a, c);
if (b > d) swap(b, d);
return sum(c, d) ^ sum(c, b - ) ^ sum(a - , d) ^ sum(a - , b - );
}
} bit; int main() {
//freopen("in", "r", stdin);
int n, m, op;
int a, b, c, d;
LL e;
scanf("%d%d", &n, &m);
bit.init(n, n);
while (m--) {
scanf("%d", &op);
if (op == ) {
scanf("%d%d%d%d", &a, &b, &c, &d);
printf("%d\n", bit.sum(a, b, c, d));
}
if (op == ) {
scanf("%d%d%d%d%lld", &a, &b, &c, &d, &e);
//cout << a << ' ' << b << ' ' << c << ' ' << d << ' ' << e << endl;
bit.add(a, b, c, d, e);
}
}
return ;
}
二维BIT（单点更新，子矩阵查询）：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring> using namespace std; const int N = ;
inline int lowbit(int x) { return x & -x;}
struct BIT {
int s[N][N], n;
void init(int sz) {
n = sz;
for (int i = ; i <= n; i++) for (int j = ; j <= n; j++) s[i][j] = ;
}
void add(int x, int y, int d) {
int t = y > ? y : ;
for (x = x > ? x : ; x <= n; x += lowbit(x)) {
for (y = t; y <= n; y += lowbit(y)) {
s[x][y] += d;
}
}
}
int sum(int x, int y) {
int t = y, ret = ;
for ( ; x > ; x -= lowbit(x)) {
for (y = t; y > ; y -= lowbit(y)) {
ret += s[x][y];
}
}
return ret;
}
int sum(int a, int b, int c, int d) {
if (a > c) swap(a, c);
if (b > d) swap(b, d);
return sum(c, d) - sum(c, b - ) - sum(a - , d) + sum(a - , b - );
}
int get(int x, int y) {
return sum(x, y, x, y);
}
} bit; int main() {
//freopen("in", "r", stdin);
int T, n;
scanf("%d", &T);
for (int cas = ; cas <= T; cas++) {
bit.init();
printf("Case %d:\n", cas);
int a, b, c, d, e;
char s[];
scanf("%d", &n);
while (n--) {
scanf("%s", s);
if (s[] == 'S') {
scanf("%d%d%d%d", &a, &b, &c, &d);
a++, b++, c++, d++;
if (a > c) swap(a, c);
if (b > d) swap(b, d);
printf("%d\n", bit.sum(a, b, c, d) + (c - a + ) * (d - b + ));
}
if (s[] == 'A') {
scanf("%d%d%d", &a, &b, &c);
a++, b++;
bit.add(a, b, c);
}
if (s[] == 'D') {
scanf("%d%d%d", &a, &b, &c);
a++, b++;
c = min(c, bit.get(a, b) + );
bit.add(a, b, -c);
}
if (s[] == 'M') {
scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
a++, b++, c++, d++;
e = min(e, bit.get(a, b) + );
bit.add(a, b, -e);
bit.add(c, d, e);
}
}
}
return ;
}
——written by Lyon