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

kkw564 6년 전 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;
}