Dynamic Li Chao Tree

data_structure/dynamic_li_chao_tree.hpp · GitHub で見る

共通ページ

#include "lib/data_structure/dynamic_li_chao_tree.hpp"

DynamicLiChaoTree<> tree(-1000000000LL, 1000000001LL);
tree.add_line(2, 1);
tree.add_segment(-3, 5, -1, 4);
auto value = tree.query(0);
if (value) {
	long long answer = static_cast<long long>(*value); // 1
}

例では直線 \(2x+1\) と、\(-3\le x<5\) にだけ有効な直線 \(-x+4\) を追加しています。query(0) の答えは 1 です。返り値は std::optional なので、値があることを確認して *value で取り出します。対象の直線がない場合は nullopt です。例の整数への変換は、答えが long long に収まる場合に使います。

操作	内容・返り値	計算量
DynamicLiChaoTree(lower,upper)	整数座標の範囲 [lower,upper) を指定。省略時は T の全範囲	\(O(1)\)
build(lower,upper)	座標範囲を変更し、全ての直線・線分を削除	\(O(N)\)
lower() / upper()	座標範囲の左端／右端を bound_type で返す	\(O(1)\)
add_line(a,b)	座標範囲全体に直線 \(ax+b\) を追加	償却 \(O(\log C)\)
add_segment(l,r,a,b)	半開区間 \([l,r)\) に直線 \(ax+b\) を追加。座標範囲外は切り詰め、空区間は無視	償却 \(O(\log^2 C)\)
query(x)	座標 x での最小値を optional<value_type> で返す。対象がなければ nullopt	\(O(\log C)\)
empty()	直線・線分を含まないか	\(O(1)\)
node_count()	使用中のノード数。線分追加用の中間ノードも含む	\(O(1)\)
reserve(count)	指定数のノード領域を事前確保。直線・線分は変更しない	\(O(N)\)
clear()	座標範囲と確保領域を残して全ての直線・線分を削除	\(O(N)\)
value_type / bound_type	評価値の型／区間端点の型	—（型）

クエリ座標の事前登録は不要で、追加・クエリをオンラインで処理します。query(x) の x は指定した座標範囲内である必要があります。直線の削除は行いません。座標を全て先読みできる場合は Li Chao Tree (クエリ先読み) も使えます。

DynamicLiChaoTree<T, true> では最大値を返します。T は座標と係数に使う 64 bit 以下の符号付き整数型で、既定は std::int64_t です。浮動小数点座標は扱いません。

既定の value_type は、T が 32 bit 以下なら std::int64_t、64 bit なら __int128_t です。第 3 テンプレート引数で計算・返り値の型を指定できます。狭い型を指定する場合、全ての有効な座標で積と和がその型に収まる必要があります。既定の 128 bit 評価でも、追加した直線・線分の有効範囲で値が 64 bit に収まる間は軽い比較を使います。

bound_type は T が 32 bit 以下なら std::int64_t、64 bit なら __int128_t です。最大座標の一つ先を端点に指定できるため、既定の範囲は T の最大値も含みます。区間は全て右端を含みません。

DynamicLiChaoTree<> all;
using B = decltype(all)::bound_type;
auto last = std::numeric_limits<std::int64_t>::max();
all.add_segment(B(last), B(last) + 1, 0, 7);
auto value = all.query(last);

必要なノードだけを連続配列に確保します。通常の直線追加では新規ノードは高々 1 個です。座標範囲が分かる場合は狭く指定すると、走査の深さを抑えられます。

座標範囲の整数の個数を \(C\)、直線・線分の追加回数をそれぞれ \(L,S\)、使用中のノード数を \(N\) とします。直線追加は償却 \(O(\log C)\)、線分追加は償却 \(O(\log^2 C)\)、クエリは \(O(\log C)\)、ノードの空間は \(O(L+S\log C)\) です。構築は \(O(1)\)、build・clear・確保領域を増やす reserve は \(O(N)\)、その他のクエリは \(O(1)\) です。

依存ライブラリ

• 順序付き整数の中点

検証コード

• test/dynamic_li_chao_tree_line.test.cpp
• test/dynamic_li_chao_tree_segment.test.cpp

コード

#ifndef DYNAMIC_LI_CHAO_TREE_HPP
#define DYNAMIC_LI_CHAO_TREE_HPP

#include "../components/ordered_midpoint.hpp"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>

template <class T = std::int64_t, bool maximize = false, class R = std::conditional_t<(sizeof(T) < 8), std::int64_t, __int128_t>>
class DynamicLiChaoTree {
	static_assert(std::is_integral_v<T> && std::is_signed_v<T> && sizeof(T) <= 8);
	using B = std::conditional_t<(sizeof(T) < 8), std::int64_t, __int128_t>;
	static constexpr std::uint32_t present = std::uint32_t(1) << 31, mask = present - 1;
	static constexpr B first = std::numeric_limits<T>::lowest(), end = B(std::numeric_limits<T>::max()) + 1;
	struct Line {
		T a = 0, b = 0;
		template <class V> V eval(T x) const { return V(R(a) * R(x) + R(b)); }
	};
	struct Node { Line line; std::uint32_t left = 0, right = 0; };
	std::vector<Node> nodes_{Node{}};
	std::uint32_t root_ = 0;
	T low_, high_;
	bool wide_ = false;
	template <class V> static bool better(V a, V b) {
		if constexpr (maximize) return a > b;
		else return a < b;
	}
	std::uint32_t make_node(Line f = {}, bool has_line = false) {
		assert(nodes_.size() < present);
		nodes_.push_back({f, has_line ? present : 0, 0});
		return std::uint32_t(nodes_.size() - 1);
	}
	template <class V> std::uint32_t insert(std::uint32_t k, T l, T r, Line f) {
		if (!k) return make_node(f, true);
		std::uint32_t result = k;
		for (;;) {
			auto& node = nodes_[k];
			if (!(node.left & present)) {
				node.line = f, node.left |= present;
				return result;
			}
			auto& g = node.line;
			if (f.a == g.a) {
				if (better(f.b, g.b)) g = f;
				return result;
			}
			T m = ordered_midpoint(l, r);
			if (better(f.template eval<V>(m), g.template eval<V>(m))) std::swap(f, g);
			if (l == r) return result;
			bool right = better(f.a, g.a);
			if (!better(f.template eval<V>(right ? r : l), g.template eval<V>(right ? r : l))) return result;
			std::uint32_t child = right ? node.right : node.left & mask;
			if (!child) {
				child = make_node(f, true);
				if (right) nodes_[k].right = child;
				else nodes_[k].left = (nodes_[k].left & present) | child;
				return result;
			}
			k = child;
			if (right) l = T(m + 1);
			else r = m;
		}
	}
	template <class V> std::uint32_t insert_segment(std::uint32_t k, T l, T r, T ql, T qr, Line f) {
		if (k && (nodes_[k].left & present)) {
			const auto& g = nodes_[k].line;
			if (f.a == g.a) {
				if (!better(f.b, g.b)) return k;
			} else {
				T edge = better(f.a, g.a) ? std::min(r, qr) : std::max(l, ql);
				if (!better(f.template eval<V>(edge), g.template eval<V>(edge))) return k;
			}
		}
		if (ql <= l && r <= qr) return insert<V>(k, l, r, f);
		if (!k) k = make_node();
		T m = ordered_midpoint(l, r);
		if (ql <= m) {
			auto child = insert_segment<V>(nodes_[k].left & mask, l, m, ql, qr, f);
			nodes_[k].left = (nodes_[k].left & present) | child;
		}
		if (m < qr) nodes_[k].right = insert_segment<V>(nodes_[k].right, T(m + 1), r, ql, qr, f);
		return k;
	}
	void check(Line f, T l, T r) {
		if constexpr (std::is_same_v<R, __int128_t>) if (!wide_) {
			R a = f.template eval<R>(l), b = f.template eval<R>(r);
			wide_ = a < std::numeric_limits<std::int64_t>::lowest() || a > std::numeric_limits<std::int64_t>::max()
				|| b < std::numeric_limits<std::int64_t>::lowest() || b > std::numeric_limits<std::int64_t>::max();
		}
	}
	template <class F> decltype(auto) dispatch(F f) const {
		if constexpr (std::is_same_v<R, __int128_t>) if (!wide_) return f.template operator()<std::int64_t>();
		return f.template operator()<R>();
	}
	template <class V> std::optional<R> query_impl(T x) const {
		V result = maximize ? std::numeric_limits<V>::lowest() : std::numeric_limits<V>::max();
		bool found = false;
		T l = low_, r = high_;
		for (std::uint32_t k = root_; k;) {
			const auto& node = nodes_[k];
			if (node.left & present) {
				V value = node.line.template eval<V>(x);
				if (better(value, result)) result = value;
				found = true;
			}
			if (l == r) break;
			T m = ordered_midpoint(l, r);
			if (x <= m) k = node.left & mask, r = m;
			else k = node.right, l = T(m + 1);
		}
		if (found) return R(result);
		return std::nullopt;
	}

  public:
	using value_type = R;
	using bound_type = B;
	explicit DynamicLiChaoTree(B lower = first, B upper = end) { build(lower, upper); }
	void build(B lower, B upper) {
		assert(first <= lower && lower < upper && upper <= end);
		low_ = T(lower), high_ = T(upper - 1);
		clear();
	}
	B lower() const { return B(low_); }
	B upper() const { return B(high_) + 1; }
	bool empty() const { return root_ == 0; }
	std::size_t node_count() const { return nodes_.size() - 1; }
	void reserve(std::size_t count) {
		assert(count < present);
		nodes_.reserve(count + 1);
	}
	void clear() { nodes_.resize(1), root_ = 0, wide_ = false; }
	void add_line(T a, T b) {
		Line f{a, b};
		check(f, low_, high_);
		dispatch([&]<class V>() { root_ = insert<V>(root_, low_, high_, f); });
	}
	void add_segment(B l, B r, T a, T b) {
		assert(l <= r);
		l = std::max(l, lower()), r = std::min(r, upper());
		if (l >= r) return;
		Line f{a, b};
		T ql = T(l), qr = T(r - 1);
		check(f, ql, qr);
		dispatch([&]<class V>() { root_ = insert_segment<V>(root_, low_, high_, ql, qr, f); });
	}
	std::optional<R> query(T x) const {
		assert(low_ <= x && x <= high_);
		return dispatch([&]<class V>() { return query_impl<V>(x); });
	}
};

#endif

Back to top page