[백준BOJ] 11658 구간 합 구하기3
https://www.acmicpc.net/problem/11658
11658번: 구간 합 구하기 3
첫째 줄에 표의 크기 N과 수행해야 하는 연산의 수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 w, x, y, c 또는 다섯 개의 정수 w, x1, y1, x2, y2 가 주어진다. w = 0인 경우는 (x, y)를 c로 바꾸는 연산이고, w = 1인 경우는 (x1, y1)부터 (x2, y2)의 합을 구해 출력하는
www.acmicpc.net
문제해설
"펜윅 트리"를 이용한 풀이가 가능합니다. "펜윅 트리"에 대해서 아직 모르시는 분들은 아래링크를 보고 공부하시면 될 것 같습니다.
https://www.acmicpc.net/blog/view/21
펜윅 트리 (바이너리 인덱스 트리)
블로그: 세그먼트 트리 (Segment Tree) 에서 풀어본 문제를 Fenwick Tree를 이용해서 풀어보겠습니다. Fenwick Tree는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다. Fenwick Tree를 구현하려면, 어떤 수 X를 이진수로 나타냈을 떄, 마지막 1의 위치를 알아야 합니다. 3 = 112 5 = 1012 6 = 1102 8 = 10002 9 = 10012 10 = 10102 11 = 10112 12
www.acmicpc.net
< update, query 함수 >
//변수
#define MAX_N 1025
int tree[MAX_N][MAX_N];
int tree_data[MAX_N][MAX_N];
int N, M, totalN;void update_tree(int row,int col, int value) {
while (col <= N) {
tree[row][col] += value;
col += (col & -col);
}
}int query(int row, int col) {
int ret = 0;
while (col >= 1) {
ret += tree[row][col];
col -= (col & -col);
}
return ret;
}update는 해당 row에 대해서 해주면 됩니다.
query또한 해당 row에 대해서 리턴 해주시면 됩니다.
( 처음엔 tree[MAN_N * MAX_N] 일차원 배열을 사용했는데 시간초과가 나더군요 ㅠㅠ..)
전체코드
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
//변수
#define MAX_N 1025
int tree[MAX_N][MAX_N];
int tree_data[MAX_N][MAX_N];
int N, M, totalN;
void update_tree(int row,int col, int value) {
while (col <= N) {
tree[row][col] += value;
col += (col & -col);
}
}
int query(int row, int col) {
int ret = 0;
while (col >= 1) {
ret += tree[row][col];
col -= (col & -col);
}
return ret;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
int data; cin >> data;
tree_data[i][j] = data;
update_tree(i, j, data);
}
}
for (int i = 0; i < M; i++) {
int tag; cin >> tag;
if (tag == 0) {
int row, col, value, diff;
cin >> row >> col >> value;
diff = value - tree_data[row][col];
update_tree(row,col, diff);
tree_data[row][col] = value;
}
else {
int row1, col1, row2, col2;
int ans = 0;
cin >> row1 >> col1 >> row2 >> col2;
for (int j = row1; j <= row2; j++) {
int ret2 = query(j, col2);
int ret1 = query(j,col1-1);
ans += ret2 - ret1;
}
cout << ans << "\n";
}
}
}