[2167] 2차원 배열의 합

• 입력: 배열의 가로 n, 세로 m, 배열의 값 n*m, 쿼리 수 k, 두 개의 좌표 (i, j), (x, y)
• 출력: (i, j) ~ (x, y) 부터 더한 값
• 알고리즘: 세그먼트 트리, 동적 계획법
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> #include <cmath> using namespace std; int init(int start, int end, int node, vector<int> &arr, vector<int> &tree) { if (start == end) return tree[node] = arr[start]; else return tree[node] = init(start, (start + end) / 2, node * 2, arr, tree) + init((start + end) / 2 + 1, end, node * 2 + 1, arr, tree); } int sum(vector<int> &tree, int node, int start, int end, int left, int right) { if (left > end || right < start) return 0; if (left <= start && end <= right) return tree[node]; return sum(tree, node * 2, start, (start + end) / 2, left, right) + sum(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right); } void update(vector<int> &tree, int node, int start, int end, int index, int diff) { if (index < start || index > end) return; tree[node] = tree[node] + diff; if (start != end) { update(tree, node * 2, start, (start + end) / 2, index, diff); update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, diff); } } int main() { freopen("input.txt", "r", stdin); int N, M, K; scanf("%d%d", &N, &M); int h = (int)ceil(log2(M)); int tree_size = (1 << (h + 1)); vector<vector<int> > arr(N, vector<int>(M)), tree(N, vector<int>(tree_size)); for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) scanf("%d", &arr[i][j]); for(int i=0; i<N; i++) init(0, M - 1, 1, arr[i], tree[i]); int test_case; scanf("%d", &test_case); while (test_case--) { int i, j, x, y; scanf("%d%d%d%d", &i, &j, &x, &y); int total_sum = 0; for (int k = i - 1; k <= x - 1; k++) total_sum += sum(tree[k], 1, 0, M - 1, j - 1, y - 1); printf("%d\n", total_sum); } return 0; }

각 행을 세그먼트 트리로 계산한 후, 입력된 쿼리만큼 더한다.

• 문제 출처: https://www.acmicpc.net/problem/2167