글 읽기 - 최솟값을 펜윅트리로 구할 수는 없겠죠??

kkw564 7년 전 0

좀 막 만든 감이 없지않아 있지만,

혹시 펜윅트리로도 최솟값을 구할 수 있나요??(각 구간에서의)

#include <iostream>
#include <cstdio>
#include <algorithm>

#define MAX_N 100001
#define INF 1500000000

using namespace std;

int tree[MAX_N];
int ans[MAX_N];

int query(int left, int right)
{
	int get = INF;

	while (right >= left)
	{
		get = min(get, ans[right]);
		right -= (right&-right);
	}

	return get;
}

void update(int i, int val)
{
	while (i < MAX_N)
	{
		ans[i] = min(val, ans[i]);
		i += (i&-i);
	}
}
int main()
{
	int n, m;
	scanf("%d %d", &n, &m);

	fill(ans, ans + MAX_N, INF);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &tree[i]);
		update(i, tree[i]);
	}

	while (m--)
	{
		int left, right;
		scanf("%d %d", &left, &right);

		printf("%d\n", query(left, right));
	}

	return 0;
}

ntopia 7년 전 2

펜윅트리는 기본적으로 1번부터 x번까지의 대표값을 구하는 트리입니다. 그러니까 min(a[1] ~ a[x]) 의 값은 구할 수 있어요.

그런데 이게 임의의 구간에 대해 값을 구하고 싶으면 조금 골치아픕니다.

만약 연산에 역원이 존재하면 역원을 이용해 특정 구간의 대표값을 구할 수 있습니다. 특정 구간의 합을 구하는 예가 대표적이죠. 합 2개를 구한 다음에 차이를 계산하면 되잖아요?

그런데 min 연산은 역원이 없으므로 이런게 불가능합니다.

baekjoon 7년 전 1

http://www.ioinformatics.org/o...

ntopia 7년 전 1

헐 이거 띠용한 방법이네요!

펜윅트리 2개를 쓰면 되는군요

좋은 것 배우고 갑니다...

kkw564 7년 전 0

좋은 정보 가져갑니다~

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

최솟값을 펜윅트리로 구할 수는 없겠죠??

kkw564 7년 전 0

ntopia 7년 전 2

baekjoon 7년 전 1

ntopia 7년 전 1

kkw564 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말