[ BOJ ] 11143 : Beads ( GOLD 1 ) / C

문제

A game consists of putting beads in boxes. The rules of the game are too complex to describe here, but all you need to know is that keeping track of the number of beans in adjacent boxes are very important to the outcome of the game.

You are asked by a friend to write a program to help him win the game every time. At the start of a game, all boxes are empty.

입력

The first line of the input consists of a single number T, the number of games played. Each game start with a line describing B, P and Q, the number of boxes, put requests and query requests, respectively.

Then follows P + Q lines with either P i a, saying a beads are put in box number i, or Q i j, a query request for the number of beads in boxes i through j, inclusive.

• 0 < T ≤ 100
• 0 < B ≤ 100000
• 0 < P ≤ 30000
• 0 < Q ≤ 30000
• 0 ≤ a ≤ 100
• 0 < i ≤ j ≤ B
• Note that boxes are 1-indexed.
• This is an I/O-heavy problem. For Java programmers, this means that you should use BufferedReader for input reading (not Scanner). It is also beneficial to build all output in a StringBuilder before printing in a single print statement.

출력

For each query request, output the number of beads in boxes a through b, inclusive, that are in the boxes at this point of the game.

풀이 과정

세그먼트 트리를 이용해 구간합을 구했다.

#include <stdio.h>

int arr[100000] = { 0, };
int tree[400000] = { 0, };

int init(int start, int end, int idx) {
	if (start == end) {
		arr[start] = 0;
		tree[idx] = 0;
		return tree[idx];
	}

	int mid = (start + end) / 2;
	tree[idx] = init(start, mid, idx * 2) + init(mid + 1, end, idx * 2 + 1);
	return tree[idx];
}

int interval_sum(int start, int end, int idx, int left, int right) {
	if (end < left || right < start) return 0;
	if (left <= start && end <= right) return tree[idx];

	int mid = (start + end) / 2;
	return interval_sum(start, mid, idx * 2, left, right) + interval_sum(mid + 1, end, idx * 2 + 1, left, right);
}

void update(int start, int end, int idx, int what, int value) {
	if (what < start || end < what) return;
	tree[idx] += value;
	if (start == end) return;

	int mid = (start + end) / 2;
	update(start, mid, idx * 2, what, value);
	update(mid + 1, end, idx * 2 + 1, what, value);
}

int main(void) {
	int test;
	scanf("%d", &test);
	for (int t = 0; t < test; t++) {
		int b, p, q;
		scanf("%d %d %d", &b, &p, &q);

		init(0, b - 1, 1);

		for (int i = 0; i < p + q; i++) {
			char mode;
			int n1, n2;
			getchar();
			scanf("%c %d %d", &mode, &n1, &n2);

			if (mode == 'P') {
				update(0, b - 1, 1, n1 - 1, n2);
				arr[n1 - 1] += n2;
			}
			else {
				printf("%d\n", interval_sum(0, b - 1, 1, n1 - 1, n2 - 1));
			}
		}
	}
	return 0;
}