Only Forwards In Time

A kinetic segment tree (kinetic tournament) maintains max⁡i(ait+bi)\max_i (a_i t + b_i) over subranges as tt advances. What is the price of admission?

A

There is no price at all. Query and single-line update are O(log⁡n)O(\log n), and advancing tt is O(log⁡n)O(\log n) worst case, so the structure strictly dominates a Li Chao tree on every axis.

B

tt may only increase. Query and single-line update are O(log⁡n)O(\log n), and advancing tt is O(log⁡2n)O(\log^2 n) amortized, an amortization that exists only because the certificates melt in one direction.

C

tt may move either way. Query and single-line update are O(log⁡n)O(\log n), and advancing or rewinding tt is O(n)O(n) per step, since the certificates must be recomputed whenever the clock runs backwards.

D

Lines must be inserted in order of increasing slope. Query and single-line update are O(log⁡n)O(\log n), and advancing tt is O(log⁡2n)O(\log^2 n) amortized, an amortization that exists only because the slopes arrive in order.