[C++] 백준2042 구간 합 구하기

#include <iostream>
using namespace std;
using ll = long long;	// 정수 범위 밖이므로 long long 타입을 사용한다.

int N, M, K;
ll arr[1000001]{};
ll seg[2097153]{};

void init(int s, int e, int n) {
    // start 와 end 의 위치가 일치하면 input[start] 값을 넣어준다.
    if (s == e) {
		seg[n] = arr[s];
		return;
	}
	int m = (s + e) >> 1;
	init(s, m, n * 2);	init(m + 1, e, n * 2 + 1);
	seg[n] = seg[n * 2] + seg[n * 2 + 1];
}

// start, end, 찾아야하는 곳(index), 바뀐 값(value), 시작노드
void change(int s, int e, int i, ll v, int n) {
	// 바꿀 곳을 찾은 경우
	if (s == e) {
		seg[n] = v;
		return;
	}

	// shift 연산으로 *2 의 의미이므로, m은 현재 노드의 왼쪽 자식 노드가 된다.
	int m = (s + e) >> 1;


	// 만약 찾아야 하는 곳이 왼쪽 자식노드보다 작거나 같다면 왼쪽 자식 노드쪽으로 이동한다.
	if (i <= m)	
		change(s, m, i, v, n * 2);
	// 아니라면 오른쪽 자식 노드 쪽으로 이동한다.
	else	
		change(m + 1, e, i, v, n * 2 + 1);

	// 재귀함수가 종료되고 리턴할 때마다, 노드의 합을 자식 노드의 합으로 업데이트 한다.
	seg[n] = seg[n * 2] + seg[n * 2 + 1];
}

// start, end, left, right, 시작노드
ll find(int s, int e, int l, int r, int n) {
	// Case3 - 범위 밖인 경우 
	// 찾아야하는 구간(l~r)과 현재 구간(s~e)이 포함되지 않을때
	if (l > r || l > e || r < s)	
		return 0;
	// Case2 - 포함되는 경우
	// 찾아야하는 구간(l~r)내에 현재 구간(s~e)이 포함될 때
	if (l <= s && e <= r)	
		return seg[n];
	// Case 1, 4 - 다시 탐색을 진행하는 경우
	// 찾아야하는 구간(l~r)이 현재 구간(s~e)에 포함되거나, 부분적으로 겹치는 경우
	int m = (s + e) >> 1;
	return find(s, m, l, r, n * 2) + find(m + 1, e, l, r, n * 2 + 1);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> M >> K;

	for (int i = 1; i <= N; i++)	
		cin >> arr[i];

	// 세그먼트 트리를 처음 생성한다.
	init(1, N, 1);

	for (int i = 0; i < M + K; i++) {
		ll a, b, c;
		cin >> a >> b >> c;
		if (a == 1)	change(1, N, b, c, 1);
		else	cout << find(1, N, b, c, 1) << '\n';
	}
}

 

✔️ C++의 비트 시프트 연산자

. 왼쪽 시프트 연산자(<<) 는 첫번째 피연산자의 비트를 이동하고, 두 번째 피 연산자는 이동할 자리의 수를 결정합니다. 정수 a를 정수 b로 왼쪽 시프트 하는 것은 (a<<b)로 표시되는 정수 a에 2^b를 곱하는 것과 같다.

. 오른쪽 시프트 연산자 (a>>b)의 경우, 정수 a를 2^b로 나누는 것과 같다.