c언어 1275번 커피숍2 (백준)

#include <stdio.h>

long long arr[100001] = {};
long long tree[100001] = {};
int n, q;

void update(int i, long long x) { //트리의 값을 수정합니다.
	while(i <= n) {
		tree[i] += x;
		i += i&(-i);
	}
}

long long sum(int i) { //구간합을 계산 후 반환합니다.
	long long ans = 0;
	while(i) {
		ans += tree[i];
		i -= i&(-i);
	}
	return ans;
}

int main(void) {
	scanf("%d %d", &n, &q); ///n, q 입력
	for(int i=1; i<=n; i++) { //n개의 요소들을 입력받습니다.
		scanf("%lld", &arr[i]);
		update(i, arr[i]);
	}
	
	while(q--) {
		int x, y, a, b;
		scanf("%d %d %d %d", &x, &y, &a, &b);
		if(x > y) {
			int tmp = x;
			x = y;
			y = tmp;
		}
		printf("%lld\n", sum(y)-sum(x-1)); //구간합을 출력합니다.
		update(a, b-arr[a]); //트리의 값을 수정합니다.
		arr[a] = b; //요소도 수정해 줍니다.
	}
}

풀이 : Fenwick tree

 

구간합을 푸는 문제중에선

1. 단일 합, 구간 수정

2, 구간 합, 단일 수정

3, 구간 합, 구간 수정

으로 나눌 수 있으며

 

이 문제의 경우는, 구간합을 출력하고, 단일 수정을 하므로

segment tree로 풀 수 있으나, 이 중 Fenwick tree 을 사용하면, 빠르게 구간합과, 단일 수정을 할 수 있다.

 

Fenwick tree는 이진법으로 볼 때, 그 수의 가장 낮은 1의 자릿수를 이용해서 만든 트리입니다.

update1

tree[1] = arr[1]

tree[2] = arr[1] + arr[2]

tree[3] = arr[3]

tree[4] = arr[1] + arr[2] + arr[3] + arr[4]

tree[5] = arr[5]

tree[6] = arr[5] + arr[6]

tree[7] = arr[7]

tree[8] = arr[1] + arr[2] + arr[3] + arr[4] + arr[5] + arr[6] + arr[7] + arr[8]

 

sum

sum(1) = tree[1]

sum(2) = tree[2] = arr[1] + arr[2]

sum(3) = tree[3] + tree[2] = arr[3] + arr[1] + arr[2]

sum(4) = tree[4] = arr[4] + tree[3] + tree[2] = arr[4] + arr[3] + arr[1] + arr[2]
sum(5) = tree[5] + tree[4] = arr[5] + arr[4] + arr[3] + arr[1] + arr[2]

sum(6) = tree[6] + tree[4] = arr[6] + arr[5] + arr[4] + arr[3] + arr[1] + arr[2]

sum(7) = tree[7] + tree[6] + tree[4] = arr[7] + arr[6] + arr[5] + arr[4] + arr[3] + arr[1] + arr[2]

sum(8) = tree[8] = tree[4] + tree[6] + tree[7] = arr[8] + arr[7] + arr[6] + arr[5] + arr[4] + arr[3] + arr[1] + arr[2]

 

Fenwick 트리로 구간합을 구할 수 있다!

 

 

과정

1. n, q을 입력받는다

2. n개의 요소를 입력받는다, 입력을 받을 때 마다 tree을 update한다. (tree배열의 모든 요소를 0으로 초기화 한다)

3. q만큼 query 처리 후 update을 반복 합니다.

3.1 x부터 y까지의 구간합을 출력해야하나, 만약 x>y라면 y부터 x까지의 구간합을 출력해야 합니다.

 

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

1275번: 커피숍2