SegmentTreeによるRMQ

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <list>

using namespace std;

using i8 = char;
using u8 = unsigned char;
using i32 = int;
using u32 = unsigned int;
using i64 = long long int;
using u64 = unsigned long long int;

using pii = pair<i32, i32>;

#define LOOP_TYPE(s, n) decltype((n) - (s))
#define FOR(i, s, n) for (auto i = LOOP_TYPE(s, n)(s); i != LOOP_TYPE(s, n)(n); i++)
#define FORR(i, s, n) for (auto i = LOOP_TYPE(s, n)(n) - 1; i != LOOP_TYPE(s, n)(s) - 1; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) FORR(i, 0, n)
#define mp make_pair

constexpr int dx[4] = {0, -1, 0, 1};
constexpr int dy[4] = {-1, 0, 1, 0};

/**
 *	[0, n)の区間において、[a,b)の最小値を高速に求めるデータ構造
 */
class RangeMinimumSegmentTree {
public:
	RangeMinimumSegmentTree(size_t nodeNum_)
	{
		/* 簡単のため、要素数を2のべき乗にする */
		size_t nodeNum = 1;
		while (nodeNum < nodeNum_) nodeNum *= 2;
		m_nodeNum = nodeNum;
		/* 最初はすべて最大値で埋めておく */
		m_nodes.resize(2 * nodeNum - 1);
		fill(m_nodes.begin(), m_nodes.end(), INT32_MAX);
	}

	/**
	 *	index番目の値をvalueに変更
	 */
	void Update(i32 index, int value)
	{
		/* 葉の節点から更新を始める */
		i32 k = index + m_nodeNum;	/* 前半部分に枝の節点があるので、index番目の葉はm_nodeNumズレたところにある */
		m_nodes[k] = value;
		/* 親に登りながら更新していく */
		while (k > 0) {
			k = (k - 1) / 2;	/* 節点kの親に移動 */
			const i32 lhs = k * 2 + 1;	/* 節点kの左の子 */
			const i32 rhs = k * 2 + 2;	/* 節点kの右の子 */
			m_nodes[k] = min(m_nodes[lhs], m_nodes[rhs]);
		}
	}

	/**
	 *	[a,b)の最小値を求める
	 */
	i32 RangeMinimum(i32 a, i32 b) const
	{
		return RangeMinimum(a, b, 0, 0, m_nodeNum);
	}

private:

	/**
	 *	[a,b)の最小値を求める
	 */
	i32 RangeMinimum(i32 a, i32 b, i32 k, i32 lhs, i32 rhs) const
	{
		if ((rhs <= a) || (b <= lhs)) {
			/* [a, b)と[lhs, rhs)が交差しなければ、最大値を返す */
			return INT32_MAX;
		} else if ((a <= lhs) && (rhs <= b)) {
			/* 完全に含んでいたらその値 */
			return m_nodes[k];
		} else {
			/* それ以外は、節点kの子の最小値 */
			const i32 chl = k * 2 + 1;	/* 節点kの左の子 */
			const i32 chr = k * 2 + 2;	/* 節点kの右の子 */
			const i32 mid = (lhs + rhs) / 2;
			const i32 lmin = RangeMinimum(a, b, k * 2 + 1, lhs, mid);
			const i32 rmin = RangeMinimum(a, b, k * 2 + 2, mid, rhs);
			return min(lmin, rmin);
		}
	}

	size_t m_nodeNum;
	vector<i32>	m_nodes;
};

int main()
{
	RangeMinimumSegmentTree rmq(10);
	rmq.Update(1, 4);
	rmq.Update(3, 2);
	printf("%d\n", rmq.RangeMinimum(0, 5));
	return 0;
}