본문 바로가기

세그먼트 트리

BOJ)10868 최소값 문제:icpc.me/10868 N개의 정수가 있을 때 a번째 부터 b번째 수 중에 가장 작은 수를 찾는 문제이다. 문제는 쿼리가 M(10만)개 이므로 O(N)의 시간에 최솟값을 찾으려고 할 경우 총 O(N*M)의 시간이 걸려 TL을 받을 것이다. 따라서 세그먼트 트리를 이용하여 O(logN)의 시간에 최솟값을 탐색해서 O(MlogN)의 시간에 문제를 해결해야 한다. 12345678910111213141516171819202122232425262728293031323334#include #include #define MAX_N 100000#define INF 1900000000using namespace std;int n, m, seg[4 * MAX_N], a, b;int update(int pos, in.. 더보기
BOJ)2357 최소값과 최대값 문제:icpc.me/2357 N(100000)개의 정수 중에서 a번째 수부터 b번째 수까지 중에서 최솟값과 최댓값을 출력하는 문제이다. 문제가 되는건 쿼리의 수가 M(10만)으로 최솟값과 최댓값을 O(N)의 방법으로 선형 탐색을 한다면 총 O(N*M)의 시간이 걸린다는 것이다. 그러므로 우리는 세그먼트 트리를 이용하여 최솟값과 최댓값을 O(log N)의 시간 복잡도에 해결하여 총 O(MlogN)의 시간에 문제를 해결 할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #define MAX_N 100000#define INF 1900000000us.. 더보기
BOJ)2042 구간 합 구하기 문제: icpc.me/2042 값의 갱신이 빈번하게 일어 날 때 구간 합을 구하는 문제이다. 구간에 대한 합은 파셜섬을 이용한다면 O(N)에 해결할 수 있지만 값의 갱신이 빈번하게 일어 난다면 갱신이 일어 날 때 마다 O(N)의 시간이 걸리므로 총 O(N*M)의 시간복잡도를 가지게 될 것이다. 문제에서 N이 100만 M이 만이므로 시간을 초과할 것이다. 따라서 문제를 해결하기 위하여 세그먼트 트리를 이용하여 갱신과 구간 합 출력을 O(logN)에 해결해줘서 O((M+K)logN)의 시간에 문제를 해결 할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637#include #include using namespace std;type.. 더보기
BOJ)12846 무서운 아르바이트 문제: icpc.me/12846 알바를 한 기간동안 임금이 가장 적은날을 기준으로 급여를 받을 때 최대 이익을 출력하는 문제이다. 유명한 문제인 히스토그램에서 가장 큰 직사각형과 같은 문제로 해석해도 된다. 세그먼트 트리를 이용하여 최솟값의 위치를 저장한 후 가장 작은 위치를 기준으로 왼쪽 오른쪽을 보며 답을 비교해 나간다. 히스토그램에서 가장 큰 직사각형 문제는 스택으로도 풀 수 있으니 이곳을 참고하도록 하자 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include typedef long long ll;using namespac.. 더보기
BOJ)12844 XOR 문제: icpc.me/12844 특정 구간에 XOR을 하거나 구간을 XOR한 값을 출력하는 문제이다. N,M이 50만이므로 구간에 대한 쿼리를 빠르게 처리 하기 위해 세그먼트 트리를 사용해야 한다. 이때 한 지점에 대해서가 아닌 구간에 대한 업데이트가 이루어지므로 lazy propagation을 이용하여 최적화 시켜줄 필요가 있다. 주의해야 할 점은 항상 a가 b보다 작지는 않다는 것이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include using namespace std;int n, m, a, b, c, d;in.. 더보기