POJ 3264 Balanced Lineup RMQ / 선분 트 리

제목: 지정 한 구간 의 최대 값 과 최소 값 을 찾 는 대기 열 을 보 여 줍 니 다.문제 풀이: RMQ, 경 계 를 잘 정리 해 야 합 니 다.레 퍼 런 스http://www.cnblogs.com/cnjy/archive/2009/08/30/1556566.html
    RMQ (Range Minimum / Maximum Query) 문제:    RMQ 문 제 는 주어진 구간 중 가장 값 을 구 하 는 문제 입 니 다.물론 가장 간단 한 알고리즘 은 O (n) 이지 만 조회 횟수 가 많 고 (최대 100 만 회 설정) O (n) 의 알고리즘 효율 이 부족 하 다.라인 트 리 로 알고리즘 을 O (logn) 로 최적화 할 수 있 습 니 다. (온라인 트 리 에서 라인 의 최고 값 을 저장 합 니 다.) 그러나 Sparse Table 알고리즘 이 가장 좋 습 니 다. O (nlogn) 의 예비 처리 이후 O (1) 의 조회 효율 을 실현 할 수 있 습 니 다. 다음은 Sparse Table 알고리즘 을 예비 처리 와 조회 두 부분 으로 나 누 어 설명 합 니 다. (최소 값 을 예 로 들 면)  예비 처리: DP 를 사용 하 는 사상, f (i, j) 는 [i, i + 2 ^ j - 1] 구간 의 최소 치 를 표시 합 니 다. 우 리 는 f (i, j) 의 값 을 전문 적 으로 저장 할 수 있 는 배열 을 만 들 수 있 습 니 다. 예 를 들 어 f (0, 0) 는 [0, 0], f (0, 2) 는 [0, 3] 간 의 최소 치 를 표시 합 니 다. f (2, 4) 는 [2, 17] 간 의 최소 치 를 표시 합 니 다. f (i, j) 는 f (i, j - 1) 와 f (i + 2 ^ (j - 1) 가 할 수 있 기 때 문 입 니 다., j - 1) 내 보 내기, 전달 의 초기 값 (모든 f (i, 0) = i) 은 이미 알 고 있 기 때문에 우 리 는 아래 에서 위로 향 하 는 알고리즘 으로 조건 에 맞 는 f (i, j) 의 값 을 전달 할 수 있 습 니 다.
조회: m 에서 n 까지 의 최소 값 을 조회 하려 면 먼저 가장 큰 k 를 구 해서 k 가 2 ^ k < (n - m + 1) 를 만족 시 킬 수 있 도록 합 니 다. 그래서 우 리 는 [m, n] 을 두 개 (부분 이 겹 치 거나 겹 치지 않 는) 길이 로 나 눌 수 있 습 니 다. [m, m + 2 ^ k - 1], [n - 2 ^ k + 1, n]; 그리고 우 리 는 이전에 f (m, k) 를 [m, m + 2 ^ k - 1] 의 최소 값 으로 구 했 습 니 다. f (n - 2 ^ k + 1, k) 는[n - 2 ^ k + 1, n] 의 최소 값 입 니 다.
우 리 는 그 중에서 더 작은 것 만 되 돌아 가면 우리 가 원 하 는 답 이다. 이 알고리즘 의 시간 복잡 도 는 O (1) 이다. 예 를 들 어 rmq (0, 11) = min (f (0, 3), f (4, 3) 이다. 따라서 우리 가 주의해 야 할 것 은 예비 처리 f (i, j) 중의 j 값 은 log (n + 1) / log (2) 만 계산 하면 되 고 i 값 은 n - 2 ^ k + 1 만 계산 하면 된다.
다음 구간 [m, m + 2 ^ k - 1], [n - 2 ^ k + 1, n] 부분 이 겹 치 거나 겹 치지 않 음 을 간단하게 증명 합 니 다.
가장 큰 k 를 취하 기 때문에 2 ^ k < (n - m + 1), 그래서 2 ^ (k + 1) > = (n - m + 1)
또 [n - 2 ^ k + 1] - [m + 2 ^ k + 1] = (n - m + 1) - [2 ^ (k + 1) - 1] <= 2 ^ (k + 1) - [2 ^ (k + 1) - 1] = 1, 그래서 구간 [m, m + 2 ^ k - 1], [n - 2 ^ k + 1, n] 부분 이 겹 치 거나 겹 치지 않 습 니 다. RMQj 해법:

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

#define N 50005

int dp[N], dpmin[N][20], dpmax[N][20];
int n, m;

int max ( int a, int b )
{
	return a > b ? a : b;
}

int min ( int a, int b )
{
	return a < b ? a : b;
}

void Dpmin ()
{
	int i, j, temp;
	for ( i = 1; i <= n; ++i )
		dpmin[i][0] = dp[i];
	temp = floor(log(1.0*n+1)/log(2.0) ); //  
	for ( i = 1; i <= temp; ++i )
		for ( j = 1; j + (1<<i) - 1 <= n; ++j )
			dpmin[j][i] = min ( dpmin[j][i-1], dpmin[j+(1<<(i-1))][i-1] );
}

void Dpmax ()
{
	int i, j, temp;
	for ( i = 1; i <= n; ++i )
		dpmax[i][0] = dp[i];
	temp = floor(log(1.0*n+1)/log(2.0));
	for ( i = 1; i <= temp; ++i )
		for ( j = 1; j + (1<<i) - 1 <= n; ++j )
			dpmax[j][i] = max ( dpmax[j][i-1], dpmax[j+(1<<(i-1))][i-1] );
}

int get_min ( int a, int b )
{
	int k = floor((log(1.0*(b-a+1))/log(2.0)));
	return min ( dpmin[a][k], dpmin[b-(1<<k)+1][k] );
}

int get_max ( int a, int b )
{
	int k = floor((log(1.0*(b-a+1))/log(2.0)));
	return max ( dpmax[a][k], dpmax[b-(1<<k)+1][k] );
}

int main()
{
	int i,a,b;
	//freopen( "a.txt" , "r" , stdin );
	scanf("%d%d",&n,&m);
	for ( i = 1; i <= n; ++i )
		scanf("%d",&dp[i]);
	Dpmin();
	Dpmax();
	for ( i = 1; i <= m; ++i )
	{
		scanf("%d%d",&a,&b);
		printf("%d
", get_max(a,b) - get_min(a,b) );
	}
	return 0;
}
	

선분 트 리 해법:

#include <iostream>
using namespace std;

int n, m, maxval, minval;

struct TreeNode
{
	int l, r, mx, mn;
} node[5000001];

int max ( int a, int b )
{
	return a > b ? a : b;
}

int min ( int a, int b )
{
	return a < b ? a : b;
}

void build_tree ( int l, int r, int root )
{
	node[root].l = l;
	node[root].r = r;
	if ( l == r ) return;
	int mid = ( l + r ) / 2;
	build_tree ( l, mid, root * 2 );
	build_tree ( mid + 1, r, root * 2 + 1 );
}

void update ( int val, int id, int root )
{
	if ( node[root].l == id && node[root].r == id )
	{
		node[root].mx = val;
		node[root].mn = val;
		return;
	}
	int mid = ( node[root].l + node[root].r ) / 2;
	if ( id <= mid )
		update ( val, id, root*2 );
	else
		update ( val, id, root*2+1 );
	node[root].mx = max ( node[root*2].mx, node[root*2+1].mx );
	node[root].mn = min ( node[root*2].mn, node[root*2+1].mn );
}

void query ( int l, int r, int root )
{
	if ( node[root].l == l && node[root].r == r )
	{
		maxval = max ( maxval, node[root].mx );
		minval = min ( minval, node[root].mn );
		return;
	}
	int mid = ( node[root].l + node[root].r ) / 2;
	if ( r <= mid )
		query ( l, r, root * 2 );
	else if ( l > mid )
		query ( l, r, root * 2 + 1 );
	else
	{
		query ( l, mid, root * 2 );
		query ( mid + 1, r, root * 2 + 1 );
	}
}

int main()
{
	int i, a, b, num;
	//freopen("a.txt","r",stdin);
	scanf("%d%d",&n,&m); 
	build_tree ( 1, n, 1 );
	for ( i = 1; i <= n; ++i )
	{
		scanf("%d",&num);
		update(num,i,1);
	}
	for ( i = 1; i <= m; ++i )
	{
		scanf("%d%d",&a,&b);
		maxval = -1;
		minval = 10000000;
		query(a,b,1);
		printf("%d
",maxval-minval);
	}
	return 0;
}