Algorithm 공부 #21 - 세그먼트 트리

 

Algorithm 공부 #21 - 세그먼트 트리

 

 

세그먼트 트리(Segmant Tree)

  ● 주어진 제이터의 구간 합과 데이트 업데이트를 빠르게 수행하기 위한 알고리즘

  ● 트리 초기화 / 질의값 구하기(구간 합 구하기, 최대, 최소) / 데이터 업데이트하기의 과정으로 나뉨

  ● 트리 초기화하기

      1. 데이터의 개수가 2^k일때 start_index=2^k

      2. 2^k+1 인덱스부터 리프노드를 제외한 나머지 노드의 값을 채우기

      3. 구간 합일 때 : A[N] = A[2N] + A[2N+1] / 최대 : A[N] = max(A[2N], A[2N+1) 

                                 최소 : A[N] =min(A[2N],A[2N+1])

  ● 질의값 구하기

      1. 질의 인덱스를 세그먼트 트리 인덱스로 변환 => 세그먼트 트리 index = 주어진 질의 인덱스 + (2^k) - 1

      2. start_index % 2 == 1이라면 해당 노드 선택

      3. end_index % 2 == 0이라면 해당 노드 선택

      4. start_index depth 변경 : start_index = (start_index + 1) / 2

      5. end_index depth 변경 : end_index = (end_index - 1) / 2

      6. 2~5를 반복하다가 end_index < start_index가 되면 종료

      ※ 2~3에서 해당 노드를 선택했다는 것은 해당 노드의 부모의 범위가 질의 범위를 넘어가서 제외한다는 의미

 

  ● 데이터 업데이트하기 

       1. 구간 합일때 : 원래 데이터와 변경 데이터의 차이만큼 부모 노드로 올라가면서 변경

       2. 최댓값일때 : 변경 데이터와 자신과 같은 부모를 지니고 있는 다른 자식 노드와 비교해 부모 데이터가

                                바뀌지 않으면 업데이트하지 않는다.

       3. 최솟값일때 : 변경 데이터와 자신과 같은 부모를 지니고 있는 다른 자식 노드와 비교해 부모 데이터가

                                바뀌지 않으면 업데이트하지 않는다

 

 

백준 2042번 구간 합 구하기

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

2042번: 구간 합 구하기

 

#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

vector<long>tree; // 트리 배열
long getSum(int start, int end); // 구간 합 함수
void changeVal(int index, long value); // 트리 변경 함수
void setTree(int i); // 트리 초기화 함수
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, K;
	cin >> N >> M >> K;

	int treeHeight = 0;
	long length = N;

	while (length != 0) { // 트리의 높이 구하기
		length /= 2;
		treeHeight++;
	}

	int treeSize = int(pow(2, treeHeight + 1));
	int leftNodeStartIndex = treeSize / 2 - 1; // 트리를 채울 시작점 구하기
	tree.resize(treeSize + 1); // 트리 크기 조절

	for (int i = leftNodeStartIndex + 1; i <= leftNodeStartIndex + N; i++) {
		cin >> tree[i];
	}
	
	setTree(treeSize - 1); // 트리 업데이트

	for (int i = 0; i < M + K; i++) {
		long a, b, c;
		cin >> a >> b >> c;

		if (a == 1) {
			int index = b + leftNodeStartIndex;
			changeVal(index, c);
		}
		else if (a == 2) {
			long start = b + leftNodeStartIndex;
			long end = c + leftNodeStartIndex;
			cout << getSum(start, end) << '\n';
		}
	}
}
void setTree(int i) {
	while (i != 0) {
		tree[i / 2] += tree[i];
		i--;
	}
}
void changeVal(int index, long value) {
	long diff = value - tree[index];

	while (index > 0) {
		tree[index] += diff;
		index /= 2;
	}
}
long getSum(int start, int end) {
	
	long sum = 0;

	while (start <= end) {
		if (start % 2 == 1) {
			sum += tree[start];
			start++;
		}
		if (end % 2 == 0) {
			sum += tree[end];
			end--;
		}
		start /= 2;
		end /= 2;
	}
	return sum;
}

 

 

 

백준 10868번 최솟값

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

10868번: 최솟값

 

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

vector<long>tree;
void setTree(int i);
long getMin(long s, long e);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	int treeHeight = 0;
	int length = N;
	while (length != 0) {
		length /= 2;
		treeHeight++;
	}
	int treeSize = int(pow(2, treeHeight + 1));
	int leftNodeStartIndex = treeSize / 2 - 1;
	tree.resize(treeSize + 1);

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

	setTree(treeSize - 1);
	for (int i = 0; i < M; i++) {
		int start, end;
		cin >> start >> end;
		long s = leftNodeStartIndex + start;
		long e = leftNodeStartIndex + end;
		cout << getMin(s, e) << '\n';
	}
}
void setTree(int i) {
	while (i != 1) {
		tree[i / 2] = min(tree[i],tree[i-1]);
		i-=2;
	}
}
long getMin(long s, long e) {
	long nodeMin = 1000000001;
	while (s <= e) {
		if (s % 2 == 1) {
			nodeMin = min(nodeMin, tree[s]);
			s++;
		}
		if (e % 2 == 0) {
			nodeMin = min(nodeMin, tree[e]);
			e--;
		}
		s /= 2;
		e /= 2;
	}
	return nodeMin;
}

 

 

 

백준 11505번 구간 곱 구하기

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

11505번: 구간 곱 구하기

 

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

vector<long>tree;
void changeVal(int index, long value);
long getMul(int start, int end);
void setTree(int i);
int main() {

	int N, M, K;
	cin >> N >> M >> K;



	int treeHeight = 0;
	int length = N;

	while (length != 0) {
		length /= 2;
		treeHeight++;
	}

	int treeSize = int(pow(2, treeHeight + 1));
	int nodeLeftStartIndex = treeSize / 2 - 1;
	tree.resize(treeSize + 1);

	fill(tree.begin(), tree.end(), 1);
	for (int i = nodeLeftStartIndex + 1; i <= nodeLeftStartIndex + N; i++)
		cin >> tree[i];
	setTree(treeSize - 1);
	for (int i = 0; i < M + K; i++) {
		long a, s, e;
		cin >> a >> s >> e;
		if (a == 1) {
			int start = s + nodeLeftStartIndex;
			changeVal(start, e);
		}
		else if (a == 2) {
			long start = s + nodeLeftStartIndex;
			long end = e + nodeLeftStartIndex;
			cout << getMul(start, end) << '\n';
		}
	}
}
void changeVal(int index, long value) {
	tree[index] = value;
	while (index > 1) {
		index /= 2;
		tree[index] = tree[index * 2] %1000000007 * tree[index * 2 + 1] % 1000000007;
	}

}
long getMul(int start, int end) {
	long mul = 1;
	while (start <= end) {
		if (start % 2 == 1) {
			mul = mul * tree[start] % 1000000007;
			start++;
		}
		if (end%2==0) {
			mul = mul * tree[end] % 1000000007;
			end--;
		}
		start /= 2;
		end /= 2;
	}
	return mul;
}
void setTree(int i) {
	while (i != 1) {
		tree[i / 2] = (tree[i] * tree[i / 2]) % 1000000007;
		i--;
	}
}