BOJ 11658: 구간 합 구하기 3 작성일 2020-02-28 https://www.acmicpc.net/problem/11658 2월동안 187문제 풀기(지난달 누적 87개) (70/187) 2차원 펜윅 트리 잘 구현만 하면 됨. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include <bits/stdc++.h> using namespace std; typedef long long LL; class Fenwick2D { int X, Y; vector<vector<LL>> tree; public: Fenwick2D(int x, int y): X(x+1), Y(y+1) { tree.resize(X, vector<LL>(Y)); } void update(int x, int y, int val) { for(int i = x; i < X; i += i & -i) for(int j = y; j < Y; j += j & -j) tree[i][j] += val; } LL query(int x, int y) { LL ans = 0; for(int i = x; i > 0; i -= i & -i) for(int j = y; j > 0; j -= j & -j) ans += tree[i][j]; return ans; } }; int main() { int N, M; scanf("%d %d", &N, &M); vector<vector<LL>> arr(N+1, vector<LL>(N+1)); Fenwick2D fwt(N,N); for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) { scanf("%lld", &arr[i][j]); fwt.update(i,j,arr[i][j]); } for(int i =0; i < M; i++) { int cmd, x, y, v, x1,y1,x2,y2; scanf("%d", &cmd); if(cmd == 0) { scanf("%d %d %d", &x, &y, &v); fwt.update(x,y,v-arr[x][y]); arr[x][y] = v; } else { scanf("%d %d %d %d", &x1, &y1, &x2, &y2); LL a = fwt.query(x1-1,y1-1); LL b = fwt.query(x1-1,y2); LL c = fwt.query(x2,y1-1); LL d = fwt.query(x2,y2); printf("%lld\n", d-b-c+a); } } }