<commit_before>#pragma once

#include <vector>
#include <iterator>
#include <functional>

namespace altruct {
namespace container {

/**
 * Range minimum query structure.
 *
 * Space complexity: `O(n)`.
 * Time complexities:
 *   build: `O(n)`
 *   query: `O(1)`
 */
template<typename VALUE_T, typename COMPARE_T = std::less<VALUE_T>, typename INDEX_T = int, int BLOCK_SIZE = 8>
class direct_rmq {
public:
	typedef VALUE_T value_t;
	typedef COMPARE_T compare_t;
	typedef INDEX_T index_t;
	typedef char small_index_t;
	
	struct tree_t {
		small_index_t idx[BLOCK_SIZE][BLOCK_SIZE];
	};
	
	direct_rmq(compare_t comp = compare_t()) : comp(comp) {
		calc_ballot_numbers();
	}

	template<typename It>
	void build(It begin, It end) {
		index_t len = (index_t)std::distance(begin, end);
		blocks = (len + BLOCK_SIZE - 1) / BLOCK_SIZE;
		_array.assign(begin, end);
		_array.resize(blocks * BLOCK_SIZE);
		build_block_trees();
		build_sparse_table();
	}

	value_t get_value(index_t begin, index_t end) const {
		return _array.at(get_index(begin, end));
	}

	index_t get_index(index_t begin, index_t end) const {
		index_t l = begin, r = end - 1;
		index_t x = l / BLOCK_SIZE, y = r / BLOCK_SIZE, z = y - x;
		if (z == 0) return x * BLOCK_SIZE + _block_tree[x]->idx[l % BLOCK_SIZE][r % BLOCK_SIZE];
		if (z == 1) return min_index(
			x * BLOCK_SIZE + _block_tree[x]->idx[l % BLOCK_SIZE][BLOCK_SIZE - 1],<commit_msg>range_minimum_query documentation<commit_after>#pragma once

#include <vector>
#include <iterator>
#include <functional>

namespace altruct {
namespace container {

/**
 * Range minimum query structure.
 *
 * Note: to guarantee the given time and space complexities,
 * `BLOCK_SIZE` must be at most `log2(n)/2`. See the table below.
 *
 * Space complexity: `O(n)`.
 * Time complexities:
 *   build: `O(n)`
 *   query: `O(1)`
 */
template<typename VALUE_T, typename COMPARE_T = std::less<VALUE_T>, typename INDEX_T = int, int BLOCK_SIZE = 8>
class direct_rmq {
public:
	typedef VALUE_T value_t;
	typedef COMPARE_T compare_t;
	typedef INDEX_T index_t;
	typedef char small_index_t;

	/**
	 *       Number of elements  BLOCK_SIZE  Time & Memory
	 *       4^L <= n < 4^(L+1)        L     L^2 Catalan[L]
	 *         4             16        1                  1
	 *        16             64        2                  8
	 *        64            256        3                 45
	 *       256           1024        4                224
	 *      1024           4096        5               1050
	 *      4096          16384        6               4752
	 *     16384          65536        7              21021
	 *     65536         262144        8              91520
	 *    262144        1048576        9             393822
	 *   1048576        4194304       10            1679600
	 *   4194304       16777216       11            7113106
	 *  16777216       67108864       12           29953728
	 *  67108864      268435456       13          125550100
	 * 268435456     1073741824       14          524190240
	 */
	struct tree_t {
		small_index_t idx[BLOCK_SIZE][BLOCK_SIZE];
	};
	
	direct_rmq(compare_t comp = compare_t()) : comp(comp) {
		calc_ballot_numbers();
	}

	template<typename It>
	void build(It begin, It end) {
		index_t len = (index_t)std::distance(begin, end);
		blocks = (len + BLOCK_SIZE - 1) / BLOCK_SIZE;
		_array.assign(begin, end);
		_array.resize(blocks * BLOCK_SIZE);
		build_block_trees();
		build_sparse_table();
	}

	value_t get_value(index_t begin, index_t end) const {
		return _array.at(get_index(begin, end));
	}

	index_t get_index(index_t begin, index_t end) const {
		index_t l = begin, r = end - 1;
		index_t x = l / BLOCK_SIZE, y = r / BLOCK_SIZE, z = y - x;
		if (z == 0) return x * BLOCK_SIZE + _block_tree[x]->idx[l % BLOCK_SIZE][r % BLOCK_SIZE];
		if (z == 1) return min_index(
			x * BLOCK_SIZE + _block_tree[x]->idx[l % BLOCK_SIZE][BLOCK_SIZE - 1],
{'fraction_non_alphanumeric': 0.10850515463917526, 'fraction_numerical': 0.0672680412371134, 'mean_word_length': 2.3836094158674803, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4229050', 'n_tokens_mistral': 1601, 'n_tokens_neox': 1333, 'n_words': 351}