[−][src]Struct contest_algorithms::order::PiecewiseLinearConvexFn
Represents a maximum (upper envelope) of a collection of linear functions of one variable, evaluated using an online version of the convex hull trick. It combines the offline algorithm with square root decomposition, resulting in an asymptotically suboptimal but simple algorithm with good amortized performance: N inserts interleaved with Q queries yields O(N sqrt Q + Q log N) time complexity in general, or O(N + Q log N) if all queries come after all inserts.
Implementations
impl PiecewiseLinearConvexFn[src]
pub fn max_with(&mut self, new_m: f64, new_b: f64)[src]
Replaces the represented function with the maximum of itself and a provided line
pub fn evaluate(&mut self, x: f64) -> f64[src]
Evaluates the function at x with good amortized runtime
Trait Implementations
impl Default for PiecewiseLinearConvexFn[src]
fn default() -> PiecewiseLinearConvexFn[src]
Auto Trait Implementations
impl RefUnwindSafe for PiecewiseLinearConvexFn
impl Send for PiecewiseLinearConvexFn
impl Sync for PiecewiseLinearConvexFn
impl Unpin for PiecewiseLinearConvexFn
impl UnwindSafe for PiecewiseLinearConvexFn
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized, [src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized, [src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized, [src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T[src]
impl<T> From<T> for T[src]
impl<T, U> Into<U> for T where
U: From<T>, [src]
U: From<T>,
impl<T, U> TryFrom<U> for T where
U: Into<T>, [src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>, [src]
U: TryFrom<T>,