Segment Tree, LIS

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

2042번: 구간 합 구하기

가장 기본문제.

 

구간의 합,최댓값,최소값 등, 원소간 결합,교환법칙이 성립하는 연산에대해 구간의 연산을 구할 수 있는 알고리즘.

LIS(최소증가하는수열)을 구할때도 O(nlogn)에 가능함.

 

필요한 것:

 : 원소의 수보다 큰 2의 거듭제곱 값의 두배의 크기를 갖는 세그먼트트리 배열. (루트 idx=1부터)

 ex)원소의 수가 10이면 이것보다 큰 2의 거듭제곱 값은 16이므로 배열의 크기는 32가 된다.

 

update : O(log n)

construct : O(n)

val : O(log n) 

//원소의 수가 1000000이라면 트리배열 가장 마지막줄은 1<<20(1248576)개의 원소가 들어가면 됨.
const int MAX = 1 << 21; //트리배열의 크기는 그것의 두배

int arr[MAX];

void update(int i, int val) {
	i += (MAX / 2);
	arr[i] = val;
	while (i > 1) {
		i /= 2;
		//구간 최대값이면 max(arr[i*2],arr[i*2+1])
		arr[i] = arr[i * 2] + arr[i * 2 + 1];
	}
}

void construct() {
	for (int i = MAX / 2 - 1; i > 0; --i)
		arr[i] = arr[i * 2] + arr[i * 2 + 1];
}

int val(int s, int e, int node, int ns, int ne) {
	if (e < ns || ne < s) return 0;
	if (s <= ns && ne <=eR) return arr[node];
	int mid = (ns + ne) / 2;
    //구간최댓값이나 최소값이면 밑 문장이 바뀌겠져
	return val(s, e, node * 2, ns, mid) + val(s, e, node * 2 + 1, mid + 1, ne);
}
int val(int s, int e){
	return val(s,e,1,0,MAX/2-1);
}    

 

 

 

LIS(가장긴증가하는부분수열)의 길이는 다음과 같이 구한다.

같은 값을 같는 원소들에 대해 나중에 입력된 값을 먼저 처리하는 이유는,  먼저 입력된 값을 먼저 처리하면 값을 갱신해서 원하는 값보가 큰 값이 나오게 되기 때문임.

//update, construct, val함수를 구간 최댓값으로 변경한 상태에서

int main() {
	int n; cin >> n;

	pair<int, int> p[1000001];
	for (int i = 0,a; i < n; i++) {
		cin >> a;
		p[i] = { a,i };
	}
    
    //가장 작은 값을 앞에 오도록 정렬, 같은 값이면 나중에 입력된 값이 앞에 오도록 정렬
	sort(p, p + n, [](pair<int, int> p, pair<int, int> q) {
		if (p.first != q.first) return p.first < q.first;
		return p.second > q.second;
	});

	//정렬한 순서대로 원소들을 방문하면서 전체 구간의 최대값을 갱신시켜주면
	for (int i = 0; i < n; i++) {
		int temp = val(0, p[i].second, 1, 0, = MAX/2 - 1) + 1;
		update(p[i].second, temp);
	}
    
    //루트노드에 LIS의 길이가 저장된다.
	cout << arr[1] << '\n';
}

 

---

좀더 간단히 구하는 방법

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n;
	while (scanf("%d",&n)>0) {
		vector<int> last(1, 0);
		for (int i = 0, cur; i < n; ++i) {
			scanf("%d", &cur);
			if (last.back() < cur) last.push_back(cur);
			else *lower_bound(last.begin(), last.end(), cur) = cur;
		}
		printf("%d\n", last.size() - 1);
	}
}

 

 

<설명>

{5,6,7,1,2}의 LIS는 {5,6,7}이다. 반면에 길이가 2인 부분 증가 수열은 {5,6}, {5,7}, {1,2}이다.

이 셋 중 다음 LIS의 후보로 유력한 것은 {1,2}이다.

 

c[i] = 지금까지 만든 부분 배열이 갖는 길이 i인 증가 부분수열 중 최소의 마지막 값.

이걸 유지하면

O(n*k),,(k는 LIS의 길이)로 구현할 수 있다.

 

위 코드는 c[i]가 순증가한다는 사실을 이용해서 이분탐색을 한 것.