[C/C++] 백준 - 세그먼트 트리 문제

 

✏️ 세그먼트 트리 기본 개념 

https://pooreumjung.tistory.com/305

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

문제 풀기 전에 보시면 도움이 됩니다!

 

✏️ 문제 링크

 

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

2357번: 최솟값과 최댓값

 

✏️ 문제 설명

 

 

✏️ 문제 코드

#include<iostream>
#include<vector>
#include<cmath>
#include<limits.h>
using namespace std;

vector<long>treeMin;
vector<long>treeMax;
void setMin(int i);
void setMax(int i);
long getMin(int start, int end);
long getMax(int start, int end);
int main() {

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

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

	int length = N;
	int treeHeight = 0;
	while (length != 0) {
		length /= 2;
		treeHeight++;
	}
	int treeSize = int(pow(2, treeHeight + 1));
	int nodeLeftStatrIndex = treeSize / 2 - 1;
	treeMin.resize(treeSize + 1);
	treeMax.resize(treeSize + 1);
	fill(treeMin.begin(), treeMin.end(), LONG_MAX);

	for (int i = nodeLeftStatrIndex + 1; i <= N + nodeLeftStatrIndex; i++) {
		cin >> treeMin[i];
		treeMax[i] = treeMin[i];
	}
	
	setMin(treeSize - 1);
	setMax(treeSize - 1);


	for (int i = 0; i < M; i++) {
		int start, end;
		cin >> start >> end;
		start += nodeLeftStatrIndex;
		end += nodeLeftStatrIndex;
		cout << getMin(start, end) << " " << getMax(start, end) << '\n';
	}
}
void setMin(int i) {
	while (i != 1) {
		treeMin[i / 2] = min(treeMin[i / 2], treeMin[i]);
		i--;
	}
}
void setMax(int i) {
	while (i != 1) {
		treeMax[i / 2] = max(treeMax[i / 2], treeMax[i]);
		i--;
	}
}
long getMin(int start, int end) {
	long partMin = 1000000001;
	while (start <= end) {
		if (start % 2 == 1) {
			partMin = min(partMin, treeMin[start]);
			start++;
		}
		if (end % 2 == 0) {
			partMin = min(partMin, treeMin[end]);
			end--;
		}
		start /= 2;
		end /= 2;
	}
	return partMin;
}
long getMax(int start, int end) {
	long partMax = 0;
	while (start <= end) {
		if (start % 2 == 1) {
			partMax = max(partMax, treeMax[start]);
			start++;
		}
		if (end % 2 == 0) {
			partMax = max(partMax, treeMax[end]);
			end--;
		}
		start /= 2;
		end /= 2;
	}
	return partMax;

}

 

 

✏️ 문제 링크

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

1275번: 커피숍2

 

✏️ 문제 설명

✏️ 문제 코드

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

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

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

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

	int length = N;
	int treeHeight = 0;

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

	for (int i = nodeLeftStartIndex+1; i <= N+nodeLeftStartIndex; i++)
		cin >> tree[i];
	setTree(treeSize - 1);

	for (int i = 0; i < M; i++) {
		long x, y, a, b;
		cin >> x >> y >> a >> b;
		if (x > y)
			swap(x, y);
		long start = x + nodeLeftStartIndex;
		long end = y + nodeLeftStartIndex;
		cout << getSum(start, end) << '\n';
		int index = a + nodeLeftStartIndex;
		changeVal(index, b);
	}
}
void setTree(int i) {
	while (i > 1) {
		tree[i / 2] += tree[i];
		i--;
	}
}
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;
}
void changeVal(int index, long value) {
	long diff = value - tree[index];
	while (index > 0) {
		tree[index] += diff;
		index /= 2;
	}
}

 

 

✏️ 문제 링크

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

2268번: 수들의 합 7

 

✏️ 문제 설명

✏️ 문제 코드

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

vector<long>tree;
long getSum(int start, int end);
void changeVal(int index, long value);

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

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

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

	for (int i = 0; i < M; i++) {
		long a, b, c;
		cin >> a >> b >> c;
		if (a == 0) {
			if (b > c)
				swap(b, c);
			int start = b + nodeLeftStartIndex;
			int end = c + nodeLeftStartIndex;
			cout << getSum(start, end) << '\n';
		}
		else if (a == 1) {
			int index = b + nodeLeftStartIndex;
			changeVal(index, c);
		}
	}
}
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;
}