11658번: 구간 합 구하기 3

https://www.acmicpc.net/problem/11658


$O((n^2+m){\lg n}^2)$

2D 펜윅 트리를 구현한다.

#include<cstdio>
int n, m, mx[1025][1025], bit[1025][1025];
void update(int x, int y, int s) {
    for (; x <= n; x += x&-x)
        for (int j = y; j <= n; j += j&-j) bit[x][j] += s;
}
int sum(int x, int y) {
    int s = 0;
    for (; x; x -= x&-x)
        for (int j = y; j; j -= j&-j) s += bit[x][j];
    return s;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) scanf("%d", mx[i] + j), update(i, j, mx[i][j]);
    for (int i = 0, w, a, b, c, d; i < m; i++) {
        scanf("%d%d%d%d", &w, &a, &b, &c);
        if (w) {
            scanf("%d", &d);
            printf("%d\n", sum(c, d) - sum(a - 1, d) - sum(c, b - 1) + sum(a - 1, b - 1));
        }
        else update(a, b, c - mx[a][b]), mx[a][b] = c;
    }
    return 0;
}