c언어 2268번 수들의 합 7 (백준)

#include <stdio.h>
typedef long long int ll;
ll a[1000000]={}; //숫자 담기
ll tree[4000000]; //트리 배열

ll init(int s, int e, int node) { //트리 배열 초기화 (segment tree 초기화)
	if(s==e) return tree[node] = a[s];
	int mid = (s+e)/2;
	return tree[node] = init(s, mid, node*2) + init(mid+1, e, node*2+1);
} 

ll sum(int s, int e, int node, int l, int r) { //구간합 구하기
	if(s > r || e < l) return 0; //찾는 범위가 아니면 0 리턴
	if(l<=s && e <= r) return tree[node]; //이 부분은 찾는 범위라면, 그 때 트리값을 리턴
	int mid = (s+e)/2; //찾는 범위와, 현재 트리의 범위가 완전히 포개지지 않았을 경우
	return sum(s, mid, node*2, l, r) + sum(mid+1, e, node*2+1, l, r);
}

void update(int s, int e, int node, int index, int dif) { //단일 값 바꾸기
	if(index < s || index > e) return; //범위 이탈할 시 리턴
	tree[node] += dif; //관련 노드들은 다 수정함
	if(s==e) return; //더이상 하위노드가 없다면 리턴
	int mid = (s+e)/2;
	update(s, mid, node*2, index, dif);
	update(mid+1, e, node*2+1, index, dif);
} 

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m);
	init(0, n-1, 1);
	
	while(m--) {
		int b, c, d;
		scanf("%d %d %d", &b, &c, &d);
		if(b==1) { //수정하기
			update(0, n-1, 1, c-1, d-a[c-1]);
			a[c-1] = d;
		}
		else { //구간합 출력하기
            if(d<c) {
                int tmp = c;
                c = d;
                d = tmp;
                }
			printf("%lld\n", sum(0, n-1, 1, c-1, d-1));
		}
	}
}

풀이 : segment tree

 

1. 세그먼트 트리를 초기화 할 함수, 구간합 구하는 함수, 단일 요소를 수정하는 함수를 만듭니다.

2. n, m 입력

3. 1을 입력받았으면 특정 요소의 값을 원하는 값으로 수정

4. 0을 입력받았으면 구간합을 구한 다음 출력

 

 

 

#include <stdio.h>
//펜윅 트리
int a[1000001]={}, n; //요소를 담을 배열과, n
long long int tree[1000001]; //트리를 담을 변수

long long int sum(int i) { //구간합 구하기
	long long int ans = 0;
	while(i) {
		ans += tree[i];
		i -= (i&-i);
	}
	return ans;
}

void update(int i, int dif) { //단일 요소 수정하기
	while(i<=n) {
		tree[i] += dif;
		i += (i&-i);
	}
}

int main(void) {
	int m, b, c, d, t;
	scanf("%d %d", &n, &m);
	while(m--) {
		scanf("%d %d %d", &b, &c, &d);
		if(b) { //단일 요소 수정하기
			update(c, d-a[c]);
			a[c] = d;
		} else { //구간합 구한 뒤 출력하기
			if(c>d) {
				t = c;
				c = d;
				d = t;
			}
			printf("%lld\n", sum(d)-sum(c-1));
		}
	}
}

풀이 : Fenwick Tree

 

단일 요소 수정, 단위 구간합 출력의 경우에는

단순히 일반적인 segment tree보다, 용량과 속도면에서 우위는 Fenwick Tree을 사용하는 것도 좋습니다.

 

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

2268번: 수들의 합 7