세그먼트 트리

만약 문제를 읽는데
1: 배열이 등장하고,
2: 연속된 부분수열로 무언가를 수행하고
3: 연속된 부분 수열의 구간이 계속 바뀐다면
세그먼트 트리 문제일 확률이 높습니다.

세그먼트 트리로만 풀 수 있는 문제는 없지만, 세그먼트 트리를 활용하면 쉽게 풀리는 문제가 존재합니다.

누적합을 쓰면 안되는 유형

원소에 대한 갱신이 일어나는 경우

세그먼트 트리에서 세그먼트가 의미하는 것

많이 계산할 유형에 대해서 미리 계산함.
절반씩 나눠서 조각으로 만들고 해당 조각 내 원소의 총합을 저장함.
궁금한 구간의 쿼리가 들어올 경우 미리 만들어놓은 조각을 합쳐서 쿼리와 동일한 구간을 만든다.

조각이 많이 생기면 어떡하나요?
생각보다 조각이 많이 생기지 않습니다. 조각의 개수는 최대 2~4배까지 생성됩니다. 마지막 층에는 길이 1짜리 조각이 데이터 개수 만큼 생성이 됩니다. 위로 올라갈 수록 조각의 수는 1/2배가 됩니다.
n, n/2, n/4, ..., 1개처럼 1/2가 공비인 수열의 총합이기 때문에 대부분의 케이스에서 데이터가 개수를n으로 할 때, 4배에서 2배 정도 사이의 조각이 생성됩니다.

부모 노드의 대표값은 자식 노드의 대표값을 활용해서 계산할 수 있음

원소의 값이 바뀐다면?
루트노드부터 시작하여 대표값을 변경합니다. 이후 루트에서 리프노드에 도달하는 경로를 찾는다. 리프노드에서 경로를 따라 루트노드까지 다시 이동하면서 각 노드의 대표값을 수정합니다.

특정 구간의 합을 구할 경우?


// 세그먼트 트리 초기화
public static void init(int node, int nodeLeft, int nodeRight) {
	if (nodeLeft == nodeRight) {
		maxTree[node] = a[nodeLeft];
		minTree[node] = a[nodeLeft];
		return;
	}

	int mid = (nodeLeft + nodeRight) / 2;

	init(
			node * 2,
			nodeLeft,
			mid
	);

	init(
			node * 2 + 1,
			mid + 1,
			nodeRight
	);

	maxTree[node] = Math.max(maxTree[node * 2], maxTree[node * 2 + 1]);
	minTree[node] = Math.min(minTree[node * 2], minTree[node * 2 + 1]);
}

노드의 왼쪽구간과 오른쪽 구간이 같은 경우는 현재 노드가 리프 노드인 상황입니다. 최소 트리, 최대 트리, 총합트리 모두 구간이 1인 경우의 대표값은 자기 자신이므로 바로 값을 초기화하면됩니다.

if (nodeLeft == nodeRight) {
	maxTree[node] = a[nodeLeft];
	minTree[node] = a[nodeLeft];
	return;
}

구간을 분할할 때는 절반씩 나누어 분배합니다.

int mid = (nodeLeft + nodeRight) / 2;

init(
		node * 2,
		nodeLeft,
		mid
);

init(
		node * 2 + 1,
		mid + 1,
		nodeRight
);

왼쪽 자식과 오른쪽 자식의 대표값 계산이 끝났으므로, 현재 노드의 대표값을 계산해야합니다.

maxTree[node] = Math.max(maxTree[node * 2], maxTree[node * 2 + 1]);
minTree[node] = Math.min(minTree[node * 2], minTree[node * 2 + 1]);

특정 원소가 변경될 경우?



public static void update(int node, int nodeLeft, int nodeRight, int queryIndex, int value) {
	if (queryIndex < nodeLeft || nodeRight < queryIndex) {
		return;
	}

	if (nodeLeft == nodeRight) {
		maxTree[node] = value;
		minTree[node] = value;
		return;
	}

	int mid = (nodeLeft + nodeRight) / 2;

	update(
			node * 2,
			nodeLeft,
			mid,
			queryIndex,
			value
	);

	update(
			node * 2 + 1,
			mid + 1,
			nodeRight,
			queryIndex,
			value
	);

	maxTree[node] = Math.max(maxTree[node * 2], maxTree[node * 2 + 1]);
	minTree[node] = Math.min(minTree[node * 2], minTree[node * 2 + 1]);
}

update 함수에 들어오는 인자는 5개입니다.
queryIndex 위치의 값을 value 로 변경해야합니다.
node는 현재 탐색중인 노드를 의미하며 nodeLeft와 nodeRight는 현재 노드가 담당하고 있는 구간이 됩니다.

내가 담당하고 있지 않는 구간의 업데이트일 경우

if (queryIndex < nodeLeft || nodeRight < queryIndex) {
	return;
}

하위 노드에 대해서 먼저 업데이트 처리를 진행해봅니다.


int mid = (nodeLeft + nodeRight) / 2;

update(
		node * 2,
		nodeLeft,
		mid,
		queryIndex,
		value
);

update(
		node * 2 + 1,
		mid + 1,
		nodeRight,
		queryIndex,
		value
);

자식 노드를 이용해서 현재 노드의 대표값을 업데이트합니다.

maxTree[node] = Math.max(maxTree[node * 2], maxTree[node * 2 + 1]);
minTree[node] = Math.min(minTree[node * 2], minTree[node * 2 + 1]);

특정 구간에서 변경이 일어날 경우

public static int queryMax(int node, int nodeLeft, int nodeRight, int queryLeft, int queryRight) {
	if (queryRight < nodeLeft || nodeRight < queryLeft) {
		return 0;
	}

	if (queryLeft <= nodeLeft && nodeRight <= queryRight) {
		return maxTree[node];
	}

	int mid = (nodeLeft + nodeRight) / 2;
	int leftMax = queryMax(
			node * 2,
			nodeLeft,
			mid,
			queryLeft,
			queryRight
	);
	int rightMax = queryMax(
			node * 2 + 1,
			mid + 1,
			nodeRight,
			queryLeft,
			queryRight
	);

	return Math.max(leftMax, rightMax);
}

case1. 완전히 안겹치는 경우 = 업데이트할 필요 없는 경우
쿼리의 최대범위 < 현대 노드의 최소 범위
현재 노드의 최대 범위 <쿼리의 최소 범위

if (queryRight < nodeLeft || nodeRight < queryLeft) {
	return 0;
}

이 때 아무값이나 반환하면 안되고, 내가 구하고자하는 연산의 항등원 반환해야합니다.
더하거나 뺄 경우에는 0
최대값을 계산할 경우에는 -무한대나 문제 범위의 최소값

case2. 궁금한 구간이 현재 노드에서 전부 커버하는 경우

if (queryLeft <= nodeLeft && nodeRight <= queryRight) {
	return maxTree[node];
}

case3. 그 외 경우

int mid = (nodeLeft + nodeRight) / 2;
int leftMax = queryMax(
		node * 2,
		nodeLeft,
		mid,
		queryLeft,
		queryRight
);
int rightMax = queryMax(
		node * 2 + 1,
		mid + 1,
		nodeRight,
		queryLeft,
		queryRight
);

return Math.max(leftMax, rightMax);

하위 노드를 찾아보면서 진행합니다.

비재귀 형식 vs 재귀형식
비재귀 형식 구현 (바텀업)은 특정 원소를 바꾸는 연산을 구현할 수 있지만, 특정 구간의 원소 전체를 변경하는 연산은 구현할 수 없습니다.