li_chao_tree.hpp¶
Affine function slope*x + intercept used by li_chao_tree.
Verified by line_add_get_min, segment_add_get_min.
动态加入直线或线段，并在坐标点查询最小/最大函数值；适合斜率和查询顺序都不单调。
Implementation¶
#ifndef NOYA_LI_CHAO_TREE_HPP
#define NOYA_LI_CHAO_TREE_HPP 1
/// @complexity Time: O(log n) per line/segment insertion or point query on n coordinates.
/// Space: O(number of stored tree nodes).
#include <algorithm>
#include <cassert>
#include <optional>
#include <vector>
namespace noya {
/// @brief Affine function slope*x + intercept used by li_chao_tree.
template <class T> struct li_chao_line {
T slope{};
T intercept{};
T operator()(const T &x) const { return slope * x + intercept; }
};
/// @brief Li Chao tree on a fixed set of coordinates.
template <class T, bool Minimize = true> struct li_chao_tree {
using line_type = li_chao_line<T>;
std::vector<T> coordinates;
std::vector<std::optional<line_type>> lines;
li_chao_tree() = default;
explicit li_chao_tree(std::vector<T> points) { build(std::move(points)); }
/// @brief Rebuild on a sorted unique copy of the query coordinates.
void build(std::vector<T> points) {
std::sort(points.begin(), points.end());
points.erase(std::unique(points.begin(), points.end()), points.end());
coordinates = std::move(points);
lines.assign(std::max(1, int(coordinates.size()) * 4), std::nullopt);
}
/// @brief Add a line on every registered coordinate.
void add_line(line_type line) {
if (!coordinates.empty()) {
add_line_at(1, 0, int(coordinates.size()), line);
}
}
/// @brief Add a line on registered coordinates x in [left, right).
void add_segment(const T &left, const T &right, line_type line) {
int begin =
int(std::lower_bound(coordinates.begin(), coordinates.end(), left) -
coordinates.begin());
int end =
int(std::lower_bound(coordinates.begin(), coordinates.end(), right) -
coordinates.begin());
if (begin < end) {
add_segment_at(1, 0, int(coordinates.size()), begin, end, line);
}
}
/// @brief Query the optimum at a registered coordinate x.
T query(const T &x) const {
auto answer = query_optional(x);
assert(answer.has_value());
return *answer;
}
/// @brief Query the optimum at x, or nullopt when no active line covers x.
std::optional<T> query_optional(const T &x) const {
auto iterator = std::lower_bound(coordinates.begin(), coordinates.end(), x);
assert(iterator != coordinates.end() && *iterator == x);
return query_index_optional(int(iterator - coordinates.begin()));
}
/// @brief Query the optimum at coordinates[index].
T query_index(int index) const {
auto answer = query_index_optional(index);
assert(answer.has_value());
return *answer;
}
/// @brief Query by coordinate index, or nullopt when it is uncovered.
std::optional<T> query_index_optional(int index) const {
assert(0 <= index && index < int(coordinates.size()));
std::optional<T> answer;
query_at(1, 0, int(coordinates.size()), index, answer);
return answer;
}
private:
static bool better(const T &left, const T &right) {
if constexpr (Minimize) {
return left < right;
} else {
return right < left;
}
}
void add_line_at(int node, int left, int right, line_type line) {
if (!lines[node]) {
lines[node] = line;
return;
}
int middle = (left + right) / 2;
bool wins_left =
better(line(coordinates[left]), (*lines[node])(coordinates[left]));
bool wins_middle =
better(line(coordinates[middle]), (*lines[node])(coordinates[middle]));
if (wins_middle) {
std::swap(line, *lines[node]);
}
if (right - left == 1) {
return;
}
if (wins_left != wins_middle) {
add_line_at(node * 2, left, middle, line);
} else {
add_line_at(node * 2 + 1, middle, right, line);
}
}
void add_segment_at(int node, int left, int right, int query_left,
int query_right, line_type line) {
if (query_right <= left || right <= query_left) {
return;
}
if (query_left <= left && right <= query_right) {
add_line_at(node, left, right, line);
return;
}
int middle = (left + right) / 2;
add_segment_at(node * 2, left, middle, query_left, query_right, line);
add_segment_at(node * 2 + 1, middle, right, query_left, query_right, line);
}
void query_at(int node, int left, int right, int index,
std::optional<T> &answer) const {
if (lines[node]) {
T value = (*lines[node])(coordinates[index]);
if (!answer || better(value, *answer)) {
answer = value;
}
}
if (right - left == 1) {
return;
}
int middle = (left + right) / 2;
if (index < middle) {
query_at(node * 2, left, middle, index, answer);
} else {
query_at(node * 2 + 1, middle, right, index, answer);
}
}
};
} // namespace noya
#endif // NOYA_LI_CHAO_TREE_HPP
#include <algorithm>
#include <cassert>
#include <optional>
#include <vector>
/// @complexity Time: O(log n) per line/segment insertion or point query on n coordinates.
/// Space: O(number of stored tree nodes).
namespace noya {
/// @brief Affine function slope*x + intercept used by li_chao_tree.
template <class T> struct li_chao_line {
T slope{};
T intercept{};
T operator()(const T &x) const { return slope * x + intercept; }
};
/// @brief Li Chao tree on a fixed set of coordinates.
template <class T, bool Minimize = true> struct li_chao_tree {
using line_type = li_chao_line<T>;
std::vector<T> coordinates;
std::vector<std::optional<line_type>> lines;
li_chao_tree() = default;
explicit li_chao_tree(std::vector<T> points) { build(std::move(points)); }
/// @brief Rebuild on a sorted unique copy of the query coordinates.
void build(std::vector<T> points) {
std::sort(points.begin(), points.end());
points.erase(std::unique(points.begin(), points.end()), points.end());
coordinates = std::move(points);
lines.assign(std::max(1, int(coordinates.size()) * 4), std::nullopt);
}
/// @brief Add a line on every registered coordinate.
void add_line(line_type line) {
if (!coordinates.empty()) {
add_line_at(1, 0, int(coordinates.size()), line);
}
}
/// @brief Add a line on registered coordinates x in [left, right).
void add_segment(const T &left, const T &right, line_type line) {
int begin =
int(std::lower_bound(coordinates.begin(), coordinates.end(), left) -
coordinates.begin());
int end =
int(std::lower_bound(coordinates.begin(), coordinates.end(), right) -
coordinates.begin());
if (begin < end) {
add_segment_at(1, 0, int(coordinates.size()), begin, end, line);
}
}
/// @brief Query the optimum at a registered coordinate x.
T query(const T &x) const {
auto answer = query_optional(x);
assert(answer.has_value());
return *answer;
}
/// @brief Query the optimum at x, or nullopt when no active line covers x.
std::optional<T> query_optional(const T &x) const {
auto iterator = std::lower_bound(coordinates.begin(), coordinates.end(), x);
assert(iterator != coordinates.end() && *iterator == x);
return query_index_optional(int(iterator - coordinates.begin()));
}
/// @brief Query the optimum at coordinates[index].
T query_index(int index) const {
auto answer = query_index_optional(index);
assert(answer.has_value());
return *answer;
}
/// @brief Query by coordinate index, or nullopt when it is uncovered.
std::optional<T> query_index_optional(int index) const {
assert(0 <= index && index < int(coordinates.size()));
std::optional<T> answer;
query_at(1, 0, int(coordinates.size()), index, answer);
return answer;
}
private:
static bool better(const T &left, const T &right) {
if constexpr (Minimize) {
return left < right;
} else {
return right < left;
}
}
void add_line_at(int node, int left, int right, line_type line) {
if (!lines[node]) {
lines[node] = line;
return;
}
int middle = (left + right) / 2;
bool wins_left =
better(line(coordinates[left]), (*lines[node])(coordinates[left]));
bool wins_middle =
better(line(coordinates[middle]), (*lines[node])(coordinates[middle]));
if (wins_middle) {
std::swap(line, *lines[node]);
}
if (right - left == 1) {
return;
}
if (wins_left != wins_middle) {
add_line_at(node * 2, left, middle, line);
} else {
add_line_at(node * 2 + 1, middle, right, line);
}
}
void add_segment_at(int node, int left, int right, int query_left,
int query_right, line_type line) {
if (query_right <= left || right <= query_left) {
return;
}
if (query_left <= left && right <= query_right) {
add_line_at(node, left, right, line);
return;
}
int middle = (left + right) / 2;
add_segment_at(node * 2, left, middle, query_left, query_right, line);
add_segment_at(node * 2 + 1, middle, right, query_left, query_right, line);
}
void query_at(int node, int left, int right, int index,
std::optional<T> &answer) const {
if (lines[node]) {
T value = (*lines[node])(coordinates[index]);
if (!answer || better(value, *answer)) {
answer = value;
}
}
if (right - left == 1) {
return;
}
int middle = (left + right) / 2;
if (index < middle) {
query_at(node * 2, left, middle, index, answer);
} else {
query_at(node * 2 + 1, middle, right, index, answer);
}
}
};
} // namespace noya