二维树状数组

单点增加，范围查询

int tree[MAXN][MAXM];
int nums[MAXN][MAXM];
int n,m;
int lowbit(int i) {
    return i & -i;
}

void add(int x, int y, int v) {
    for (int i = x; i <= n; i += lowbit(i)) {
        for (int j = y; j <= m; j += lowbit(j)) {
            tree[i][j] += v;
        }
    }
}

// 从(1,1)到(x,y)这个部分的累加和
int sum(int x, int y) {
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        for (int j = y; j > 0; j -= lowbit(j)) {
            ans += tree[i][j];
        }
    }
    return ans;
}

// 实际二维数组的位置是(x,y)
// 树状数组上的位置是(x,y)
// 题目说的是单点更新，转化成单点增加(老值-新值)即可
// 不要忘了在nums中把老值改成新值
void update(int x, int y, int v) {
    add(x, y, v - nums[x][y]);
    nums[x][y] = v;
}

// 实际二维数组的位置是(x,y)
// 树状数组上的位置是(x, y)
int sumRegion(int a, int b, int c, int d) {
    return sum(c, d) - sum(a-1, d) - sum(c, b-1) + sum(a, b);
}

范围增加，单点查询(P4514)

// 维护信息 : d[i][j]
int tree1[MAXN][MAXM];
// 维护信息 : d[i][j] * i
int tree2[MAXN][MAXM];
// 维护信息 : d[i][j] * j
int tree3[MAXN][MAXM];
// 维护信息 : d[i][j] * i * j
int tree4[MAXN][MAXM];

int n, m;

int lowbit(int i) {
    return i & -i;
}

void add(int x, int y, int v) {
    int v1 = v;
    int v2 = x * v;
    int v3 = y * v;
    int v4 = x * y * v;
    for (int i = x; i <= n; i += lowbit(i)) {
        for (int j = y; j <= m; j += lowbit(j)) {
            tree1[i][j] += v1;
            tree2[i][j] += v2;
            tree3[i][j] += v3;
            tree4[i][j] += v4;
        }
    }
}

// 以(1,1)左上角，以(x,y)右下角
int sum(int x, int y) {
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        for (int j = y; j > 0; j -= lowbit(j)) {
            ans += (x + 1) * (y + 1) * tree1[i][j] - (y + 1) * tree2[i][j] - (x + 1) * tree3[i][j] + tree4[i][j];
        }
    }
    return ans;
}

void add(int a, int b, int c, int d, int v) {
    add(a, b, v);
    add(a, d + 1, -v);
    add(c + 1, b, -v);
    add(c + 1, d + 1, v);
}

int range(int a, int b, int c, int d) {
    return sum(c, d) - sum(a - 1, d) - sum(c, b - 1) + sum(a - 1, b - 1);
}