🗂️Data StructureAdvanced

Kinetic Tournament Tree

Key Points

•
A kinetic tournament tree maintains the minimum (or maximum) of moving values whose pairwise order can change over time.
•
Each internal node is certified by an inequality that remains true until a specific future time when two contenders become equal.
•
When a certificate fails, an event is processed: the local winner may swap, and this change is propagated up to the root.
•
Events are kept in a priority queue by failure time so the structure advances time in sorted order.
•
For algebraic trajectories where any pair changes order at most s times, the number of events is O(s n log n).
•
Each event can be handled in O(log n) time, giving O(s n lo $g^{2}$ n) total processing time in the worst case.
•
Floating-point robustness and simultaneous events must be handled carefully to avoid incorrect ordering.
•
This structure is used in dynamic geometric optimization like tracking the leftmost moving point or the minimum of time-varying linear functions.

Prerequisites

→Balanced binary trees / segment trees — A KTT is built on a balanced tournament/segment tree structure storing winners at internal nodes.
→Priority queues (heaps) — Events are processed in nondecreasing time using a priority queue.
→Asymptotic time and space complexity — Understanding O(n log n) event counts and O(log n) responsiveness requires comfort with asymptotics.
→Floating-point arithmetic and robustness — Event times are computed by solving equations; numerical issues can corrupt event ordering.
→Algebraic functions and roots — Certificates fail when two algebraic trajectories are equal; root finding underlies failure times.
→Divide-and-conquer paradigm — The tournament structure partitions the set and combines local winners to form the global answer.
→Event-driven processing — Kinetic data structures advance time by jumping between discrete event times instead of step-by-step.

Detailed Explanation

Tap terms for definitions

01Overview

A kinetic tournament tree (KTT) is a data structure for tracking an extremal element (minimum or maximum) among items whose values evolve continuously over time. Unlike static tournament trees that compare fixed values, a KTT attaches a time-dependent comparator to each internal node and a certificate (a proof of who currently wins) with an associated expiration time. The certificate is valid until a predicted event when the inequality at that node ceases to hold. By queuing these future failures (events) in a priority queue ordered by time, the structure can jump from one event to the next and update the winners along the path to the root, maintaining the correct extremal element for all times in between. This event-driven approach is central to kinetic data structures: we avoid recomputing everything at every time instant and instead react only when the answer could actually change. KTTs are particularly effective when item trajectories are simple algebraic functions (like linear functions of time), where pairwise ordering changes are limited. Applications include tracking the minimum of multiple time-varying costs, the leftmost or rightmost among moving points, and other dynamic geometric selections.

02Intuition & Analogies

Imagine a sports tournament bracket where each player’s skill changes smoothly over time. At any moment, each match has a current winner. The overall champion is the winner at the top of the bracket. You don’t re-run the entire tournament continuously. Instead, for each match, you predict when the underdog might catch up—say, in 7.3 minutes based on how their skills are trending. You write that time on a sticky note for that match. Now, you collect all sticky notes and look for the earliest time any match might flip. You fast-forward time to that moment, review that one match, possibly swap the winner, and then check if this changes who wins higher-level matches in the bracket. You update the sticky notes for all affected matches and repeat. Between these event times, nothing changes in the champion, so you can answer “Who’s best right now?” instantly. In a kinetic tournament tree, items are the players and their time-varying values are their skills. Certificates are the sticky notes that say, “Left child beats right child until time t.” When a certificate fails, that local result flips, and the ripple may move up to the root, possibly changing the global champion. Because each flip only affects O(log n) matches along one root-to-leaf path, the updates are efficient. If each pair of players can exchange dominance only a few times, the number of sticky notes you ever need to process stays manageable.

03Formal Definition

Let X = {

x_{1}

\dots

x_{n}

} be items with time-dependent keys

f_{i}

(t), typically algebraic of bounded degree s. A kinetic tournament tree is a balanced binary tree over X where each leaf holds one item, and each internal node v maintains: (1) the current winner

w_{v}

(t) =

ar g min

f_{i}

(t) : i

\in

leaves

(v)\}; (2) a certificate

C_{v}

(t): an inequality between the current winners of v’s two children, e.g.,

f_{ℓ}

(t)

\leq

f_{r}

(t), valid on an interval [

τ

τ

') containing the current time

τ

; and (3) the failure time

T_{v}

in f

\{t >

τ

C_{v}

(t)

is false

\}, with

T_{v}

= +

\infty

C_{v}

never fails. The global winner is w_{

root

}(t). The KTT maintains a priority queue Q of events (

T_{v}

, v). It advances time from

τ

to the minimum event time, extracts all events with that time, validates them (to avoid stale events), updates

w_{v}

at those nodes, and propagates changes upward, rescheduling certificates along affected paths. For algebraic trajectories where any pair (i, j) can swap order at most s times, each internal node’s certificate between two current child winners fails at most O(s) times per pair encountered, yielding O(s n

lo g

n) total events. Each event triggers O(

lo g

n) node updates, giving O(s n

lo g^{2}

n) total processing time, with O(n) space for the tree and certificates.

04When to Use

Use a kinetic tournament tree when you need to maintain an extremal element among continuously evolving keys and you can predict, for each local comparison, when it might change. It excels when: (1) The trajectories are simple (e.g., linear or low-degree polynomials), so pairwise order changes are few and computable; (2) The answer changes infrequently relative to time, letting you jump between discrete event times; (3) You need fast queries of the current minimum/maximum at arbitrary times; and (4) Insertions/deletions are rare or can be batched, since the classic KTT is most natural for a fixed set. Concrete examples: tracking the leftmost moving point among n points with constant velocities (f_i(t) = x_{i0} + v_{ix} t); maintaining the minimum of linear cost functions for online ad bidding where costs drift over time; monitoring the best option among algorithms whose predicted runtime is a linear function of load; or following the closest moving point to the origin along a fixed axis if the distance proxy is algebraic. If comparisons are not predictable (e.g., stochastic jumps) or if changes are extremely frequent and irregular, an event-driven kinetic structure may not be suitable.

⚠️Common Mistakes

Common pitfalls include: (1) Floating-point robustness: Computing event times by solving f_i(t) = f_j(t) with doubles can introduce small errors that cause events to fire out of order or be missed. Prefer long double, robust tie-breaking, and epsilon checks; consider exact rationals when feasible. (2) Not validating events: After a lower-level change, previously scheduled events can become stale. Always attach a version or timestamp to each certificate and discard mismatched events on extraction. (3) Mishandling simultaneous events: Multiple certificates can fail at the same time. Process all events at that time together, and use deterministic tie-breaking (e.g., by index) to avoid oscillations. (4) Ignoring degenerate cases: Parallel trajectories (equal slopes) either never swap or remain identical; treat these as infinite or handle equality consistently. (5) Over-scheduling: Only schedule certificates for nodes whose children currently have defined winners; avoid creating events for sentinel leaves. (6) Forgetting propagation: After a local change, recompute winners and reschedule certificates on every ancestor; stopping early can leave the root wrong. (7) Incorrect comparator monotonicity assumptions: The certificate must remain valid until the computed failure time; ensure your next-failure computation matches the sign dynamics of your model. (8) Memory leaks or priority queue bloat: Events that become stale should be cheap to discard; keep version counters per node so the heap can safely accumulate outdated entries without correctness issues.

Key Formulas

Linear Trajectory

f_{i} (t) = a_{i} t + b_{i}

Explanation: Each item i evolves linearly over time, with slope $a_{i}$ and intercept $b_{i}$ . This is a common and analytically convenient motion model.

Linear Intersection Time

t^{*} = \frac{b _{j} - b _{i}}{a _{i} - a _{j}}

Explanation: For two linear functions $f_{i}$ and $f_{j}$ , the time when they are equal solves $f_{i}$ ( $t^{*}$ ) = $f_{j}$ ( $t^{*}$ ). If $a_{i} = a_{j}$ , they are parallel and never intersect unless $b_{i} = b_{j}$ .

Difference Dynamics

d (t) = f_{i} (t) - f_{j} (t) = (a_{i} - a_{j}) t + (b_{i} - b_{j})

Explanation: The sign of d(t) determines who wins. If d( $t_{0}$ ) $\leq$ 0 and $a_{i}$ - $a_{j} > 0$ , the inequality will flip once at $t^{*}$ ; if $a_{i}$ - $a_{j}$ $\leq$ 0, it will never flip in the future.

Node Winner

w_{v} (t) = ar g i \in leaves (v) min f_{i} (t)

Explanation: Each internal node v stores the identity of the leaf whose value is minimal within v’s subtree at time t. The root’s winner is the global minimum.

Event Count Bound

E (n, s) = O (s n lo g n)

Explanation: If any pair of items swaps order at most s times, then across all nodes the number of certificate failures is O(s n log n). For linear functions, s = 1.

Total Processing Time

T_{total} = O (E (n, s) lo g n) = O (s n lo g^{2} n)

Explanation: Each valid event triggers O(log n) node updates. Multiplying by the total number of events yields the overall time bound.

Space Complexity

S (n) = O (n)

Explanation: The balanced binary tree stores O(n) leaves and O(n) internal nodes, plus one certificate per internal node.

Lower Envelope Query

Q (t) = i min f_{i} (t)

Explanation: At any time t, the KTT provides the value of the lower envelope, i.e., the minimum over all functions.

Complexity Analysis

Let n be the number of items, and suppose any pair of trajectories changes order at most s times (e.g.,

s = 1

for linear functions). The kinetic tournament tree is a balanced binary tree, so each item participates in O(log n) nodes. At any internal node, the certificate compares the current winners of the two children. Over time, the identity of each child winner changes only when a lower-level certificate fails; each time a unique pair of child winners faces off, their order can flip at most s times. Amortizing over all nodes and all times a contender reaches that node, the total number of certificate failures (events) across the entire tree is E(n, s) = O(s n log n). Each valid event requires updating the local node and (re)scheduling its certificate, and then propagating potential winner changes to ancestors, which touches O(log n) nodes. Thus, the worst-case responsiveness per valid event is O(log n), and the total processing time is O(E(n, s) log n) = O(s n lo

g^{2}

n). Space is O(n) for the tree plus O(n) certificates and a priority queue that may hold a comparable number of events (including stale ones) at any time. Querying the current minimum identity or value is O(1) from the root. Insertions and deletions are not inherent to the classic KTT but can be supported with rebuilding or by maintaining an overallocated tree and updating along a root-to-leaf path in O(log n), at the cost of rescheduling O(log n) certificates. In practice, numerical robustness (using long double or exact arithmetic) is crucial for maintaining correct event ordering and avoiding spurious event explosions.

Code Examples

Kinetic Tournament Tree for the minimum of linear functions f_i(t) = a_i t + b_i

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Kinetic Tournament Tree tracking argmin of linear functions f_i(t) = a_i * t + b_i.
5 // - Static set of n functions
6 // - Advance time by processing certificate failures in increasing time order
7 // - Query current argmin and its value in O(1)
8 
9 struct KTTMinLines {
10     struct Node {
11         int left = -1, right = -1, parent = -1;
12         int winner = -1;                 // index of the winning leaf in this subtree
13         long double expire = INFINITY;   // time when certificate may fail
14         unsigned long long ver = 0;      // version to detect stale events
15     };
16 
17     struct Event {
18         long double t;
19         int node;
20         unsigned long long ver;
21         bool operator<(Event const& o) const {
22             // Min-heap by time using priority_queue (invert comparison)
23             if (t != o.t) return t > o.t;
24             return node > o.node; // tie-break deterministically
25         }
26     };
27 
28     int n = 0;                 // number of real functions
29     int base = 1;              // power-of-two leaves
30     vector<Node> tr;           // tree nodes, 1-indexed internal structure
31     vector<long double> a, b;  // function parameters
32     long double now = 0.0L;    // current time
33     priority_queue<Event> pq;  // event queue
34     const long double EPS = 1e-18L;
35 
36     KTTMinLines() {}
37 
38     KTTMinLines(const vector<long double>& A, const vector<long double>& B, long double t0 = 0.0L) {
39         build(A, B, t0);
40     }
41 
42     void build(const vector<long double>& A, const vector<long double>& B, long double t0 = 0.0L) {
43         a = A; b = B; n = (int)a.size(); now = t0;
44         // Build complete binary tree with power-of-two leaves
45         base = 1; while (base < n) base <<= 1;
46         tr.assign(2 * base, Node());
47         // Initialize leaves
48         for (int i = 0; i < base; ++i) {
49             int v = base + i;
50             tr[v].left = tr[v].right = -1;
51             tr[v].parent = (v >> 1);
52             tr[v].winner = (i < n ? i : -1);
53         }
54         // Build internal nodes
55         for (int v = base - 1; v >= 1; --v) {
56             tr[v].left = v << 1;
57             tr[v].right = v << 1 | 1;
58             tr[v].parent = (v >> 1);
59             pull(v); // compute winner and schedule certificate
60         }
61     }
62 
63     // Public API
64     int argmin() const { return tr[1].winner; }
65     long double min_value() const { return value(tr[1].winner, now); }
66     long double time_now() const { return now; }
67 
68     // Process all events with time <= T. Optional callback fired when global argmin changes.
69     void advance_to(long double T, function<void(long double,int)> on_change = nullptr) {
70         if (T < now) return; // do not go back in time
71         // Process events in nondecreasing time
72         while (!pq.empty() && pq.top().t <= T + EPS) {
73             long double t = pq.top().t;
74             // Process all events at this time t (within EPS)
75             vector<Event> batch;
76             while (!pq.empty() && fabsl(pq.top().t - t) <= EPS) {
77                 batch.push_back(pq.top()); pq.pop();
78             }
79             now = max(now, t); // jump to event time
80             // Validate and apply
81             bool root_changed = false;
82             for (auto &e : batch) {
83                 if (e.node <= 0 || e.node >= (int)tr.size()) continue;
84                 Node &nd = tr[e.node];
85                 if (nd.ver != e.ver) continue; // stale
86                 // Recompute at node and propagate upward
87                 int v = e.node;
88                 bool changed = recompute_node(v);
89                 int p = tr[v].parent;
90                 while (p >= 1) {
91                     bool ch = recompute_node(p);
92                     changed = changed || ch;
93                     p = tr[p].parent;
94                 }
95                 root_changed = root_changed || changed;
96             }
97             if (root_changed && on_change) on_change(now, argmin());
98         }
99         now = T;
100     }
101 
102 private:
103     // Evaluate function i at time t
104     long double value(int i, long double t) const {
105         if (i < 0) return numeric_limits<long double>::infinity();
106         return a[i] * t + b[i];
107     }
108 
109     // Is i <= j at time t? Deterministic tie-break by index
110     bool leq(int i, int j, long double t) const {
111         if (i == j) return true;
112         long double vi = value(i, t), vj = value(j, t);
113         if (fabsl(vi - vj) > EPS) return vi < vj;
114         return i < j;
115     }
116 
117     // Compute failure time for inequality winner <= loser, assuming it holds at now
118     long double failure_time(int winner, int loser) const {
119         if (winner < 0 || loser < 0) return INFINITY;
120         // d(t) = f_w(t) - f_l(t) = (aw - al) t + (bw - bl)
121         long double da = a[winner] - a[loser];
122         long double db = b[winner] - b[loser];
123         long double dnow = da * now + db;
124         // By assumption winner <= loser at now, so dnow <= 0 (up to EPS)
125         if (fabsl(da) <= EPS) {
126             // Parallel: if equal forever, no flip; else inequality maintains
127             return INFINITY;
128         }
129         // If slope difference is positive, d(t) increases; it will cross 0 once in the future.
130         if (da > 0) {
131             long double tstar = -db / da; // solve da*t + db = 0
132             if (tstar <= now + EPS) {
133                 // Immediate or past crossing: treat as now to avoid missed flips
134                 return now;
135             }
136             return tstar;
137         } else {
138             // da < 0: d(t) decreases; once <= 0, stays <= 0; no future flip
139             return INFINITY;
140         }
141     }
142 
143     // Recompute winner and certificate at node v given current time 'now'
144     bool recompute_node(int v) {
145         if (v >= base) {
146             // leaf: nothing to schedule
147             return false;
148         }
149         int L = tr[v].left, R = tr[v].right;
150         int lw = tr[L].winner;
151         int rw = tr[R].winner;
152         int neww;
153         if (lw < 0) neww = rw;
154         else if (rw < 0) neww = lw;
155         else neww = (leq(lw, rw, now) ? lw : rw);
156         bool changed = (neww != tr[v].winner);
157         tr[v].winner = neww;
158         // Schedule certificate for this node based on current child winners
159         long double exp = INFINITY;
160         if (lw >= 0 && rw >= 0) {
161             int win = neww, los = (win == lw ? rw : lw);
162             exp = failure_time(win, los);
163         }
164         tr[v].expire = exp;
165         tr[v].ver++;
166         if (isfinite(exp)) {
167             pq.push(Event{exp, v, tr[v].ver});
168         }
169         return changed;
170     }
171 
172     // Pull function used at build time (like recompute_node but bottom-up)
173     void pull(int v) {
174         if (v >= base) return;
175         int L = v << 1, R = v << 1 | 1;
176         tr[v].left = L; tr[v].right = R;
177         int lw = tr[L].winner;
178         int rw = tr[R].winner;
179         int neww;
180         if (lw < 0) neww = rw;
181         else if (rw < 0) neww = lw;
182         else neww = (leq(lw, rw, now) ? lw : rw);
183         tr[v].winner = neww;
184         // schedule
185         long double exp = INFINITY;
186         if (lw >= 0 && rw >= 0) {
187             int win = neww, los = (win == lw ? rw : lw);
188             exp = failure_time(win, los);
189         }
190         tr[v].expire = exp;
191         tr[v].ver = 0;
192         if (isfinite(exp)) pq.push(Event{exp, v, tr[v].ver});
193     }
194 };
195 
196 int main() {
197     ios::sync_with_stdio(false);
198     cin.tie(nullptr);
199 
200     // Example: Track the minimum among linear functions
201     // f0(t) = 2t + 3, f1(t) = -1t + 10, f2(t) = 0.5t + 1
202     vector<long double> A = {2.0L, -1.0L, 0.5L};
203     vector<long double> B = {3.0L, 10.0L, 1.0L};
204 
205     KTTMinLines ktt(A, B, /*t0=*/0.0L);
206 
207     auto on_change = [&](long double t, int id){
208         cout << fixed << setprecision(6);
209         cout << "Change at t=" << t << ": argmin becomes f" << id
210              << " with value " << ktt.min_value() << "\n";
211     };
212 
213     cout << fixed << setprecision(6);
214     cout << "Initial t=0: argmin=f" << ktt.argmin() << ", value=" << ktt.min_value() << "\n";
215 
216     // Advance time and observe changes
217     ktt.advance_to(5.0L, on_change);
218     cout << "At t=5: argmin=f" << ktt.argmin() << ", value=" << ktt.min_value() << "\n";
219     ktt.advance_to(20.0L, on_change);
220     cout << "At t=20: argmin=f" << ktt.argmin() << ", value=" << ktt.min_value() << "\n";
221 
222     return 0;
223 }
224

This program implements a kinetic tournament tree for the minimum among linear functions. Internal nodes store the current winner (argmin) and a certificate expiration time computed from the two child winners. Events are scheduled in a priority queue. The advance_to method processes all events up to a target time, validating each with a version counter to discard stale events. When a local comparison flips, winner changes propagate to the root. The callback prints when the global argmin changes.

Time: O(s n log^2 n) total for linear functions with s=1; O(log n) per valid event; O(1) per argmin querySpace: O(n) for the tree and certificates; the priority queue holds O(n) pending events (plus stales)

Tracking the leftmost moving point in 2D (by x-coordinate) using a KTT

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Reuse the same KTT for linear functions: x_i(t) = x0_i + vx_i * t
5 struct KTTMinLines {
6     struct Node { int left=-1,right=-1,parent=-1; int winner=-1; long double expire=INFINITY; unsigned long long ver=0; };
7     struct Event { long double t; int node; unsigned long long ver; bool operator<(Event const& o) const { if (t!=o.t) return t>o.t; return node>o.node; } };
8     int n=0, base=1; vector<Node> tr; vector<long double> a,b; long double now=0; priority_queue<Event> pq; const long double EPS=1e-18L;
9     KTTMinLines(const vector<long double>& A, const vector<long double>& B, long double t0=0){ build(A,B,t0);} KTTMinLines(){}
10     void build(const vector<long double>& A,const vector<long double>& B,long double t0=0){ a=A;b=B;n=(int)a.size();now=t0;base=1;while(base<n)base<<=1;tr.assign(2*base,Node());for(int i=0;i<base;i++){int v=base+i;tr[v].parent=v>>1;tr[v].winner=(i<n?i:-1);}for(int v=base-1;v>=1;--v){tr[v].left=v<<1;tr[v].right=v<<1|1;tr[v].parent=v>>1;pull(v);} }
11     int argmin() const { return tr[1].winner; } long double min_value() const { return value(tr[1].winner, now);} long double time_now() const { return now; }
12     void advance_to(long double T, function<void(long double,int)> on_change=nullptr){ if(T<now) return; while(!pq.empty() && pq.top().t<=T+EPS){ long double t=pq.top().t; vector<Event> batch; while(!pq.empty() && fabsl(pq.top().t - t)<=EPS){ batch.push_back(pq.top()); pq.pop(); } now=max(now,t); bool root_changed=false; for(auto &e:batch){ if(e.node<=0 || e.node>=(int)tr.size()) continue; auto &nd=tr[e.node]; if(nd.ver!=e.ver) continue; int v=e.node; bool changed=recompute_node(v); int p=tr[v].parent; while(p>=1){ bool ch=recompute_node(p); changed=changed||ch; p=tr[p].parent; } root_changed=root_changed||changed; } if(root_changed && on_change) on_change(now,argmin()); } now=T; }
13 private:
14     long double value(int i,long double t) const { if(i<0) return numeric_limits<long double>::infinity(); return a[i]*t + b[i]; }
15     bool leq(int i,int j,long double t) const { if(i==j) return true; long double vi=value(i,t), vj=value(j,t); if(fabsl(vi - vj)>EPS) return vi < vj; return i<j; }
16     long double failure_time(int winner,int loser) const { if(winner<0 || loser<0) return INFINITY; long double da=a[winner]-a[loser]; long double db=b[winner]-b[loser]; if(fabsl(da)<=EPS) return INFINITY; if(da>0){ long double tstar = -db/da; return tstar; } return INFINITY; }
17     bool recompute_node(int v){ if(v>=base) return false; int L=tr[v].left,R=tr[v].right; int lw=tr[L].winner, rw=tr[R].winner; int neww; if(lw<0) neww=rw; else if(rw<0) neww=lw; else neww = (leq(lw,rw,now) ? lw : rw); bool changed=(neww!=tr[v].winner); tr[v].winner=neww; long double exp=INFINITY; if(lw>=0 && rw>=0){ int los=(neww==lw?rw:lw); exp=failure_time(neww,los); if(isfinite(exp) && exp<=now+1e-18L) exp=now; } tr[v].expire=exp; tr[v].ver++; if(isfinite(exp)) pq.push({exp,v,tr[v].ver}); return changed; }
18     void pull(int v){ int L=v<<1,R=v<<1|1; int lw=tr[L].winner, rw=tr[R].winner; int neww; if(lw<0) neww=rw; else if(rw<0) neww=lw; else neww=(leq(lw,rw,now)?lw:rw); tr[v].winner=neww; long double exp=INFINITY; if(lw>=0 && rw>=0){ int los=(neww==lw?rw:lw); exp=failure_time(neww,los); }
19         tr[v].ver=0; tr[v].expire=exp; if(isfinite(exp)) pq.push({exp,v,tr[v].ver}); }
20 };
21 
22 struct Pt { long double x0,y0,vx,vy; };
23 
24 int main(){
25     ios::sync_with_stdio(false);
26     cin.tie(nullptr);
27 
28     // Leftmost point among moving points with constant velocity: minimize x(t) = x0 + vx * t
29     vector<Pt> P = {
30         {0.0L, 0.0L, 0.5L, 0.1L},   // starts at x=0, drifting right
31         {5.0L, 1.0L, -0.4L, -0.2L}, // starts at x=5, moving left
32         {2.0L, 2.0L, 0.0L, 0.0L},   // stationary in x
33         {-1.0L, -3.0L, 0.2L, 0.0L}  // starts left, moving right slowly
34     };
35 
36     vector<long double> A, B; A.reserve(P.size()); B.reserve(P.size());
37     for (auto &p : P) { A.push_back(p.vx); B.push_back(p.x0); }
38 
39     KTTMinLines ktt(A, B, /*t0=*/0.0L);
40 
41     auto on_change = [&](long double t, int id){
42         cout << fixed << setprecision(6);
43         cout << "t=" << t << ": leftmost point index=" << id << ", x(t)=" << ktt.min_value() << "\n";
44     };
45 
46     cout << fixed << setprecision(6);
47     cout << "Initial: leftmost index=" << ktt.argmin() << ", x(0)=" << ktt.min_value() << "\n";
48     ktt.advance_to(10.0L, on_change);
49     cout << "At t=10: leftmost index=" << ktt.argmin() << ", x(t)=" << ktt.min_value() << "\n";
50     return 0;
51 }
52

We model each point’s x-coordinate as a linear function x_i(t) = x0_i + vx_i t and use the KTT to maintain the index with the smallest x(t). The y-coordinates are irrelevant for this selection. The callback reports every time the leftmost point changes.

Time: O(n log^2 n) total for linear motion; O(log n) per valid event; O(1) per querySpace: O(n)

Updating a function in-place and rescheduling along its path

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Extension: support updating a single function's (a,b) at current time.
5 // We reuse and slightly extend the first KTT implementation.
6 
7 struct KTTMinLines {
8     struct Node { int left=-1,right=-1,parent=-1; int winner=-1; long double expire=INFINITY; unsigned long long ver=0; };
9     struct Event { long double t; int node; unsigned long long ver; bool operator<(Event const& o) const { if (t!=o.t) return t>o.t; return node>o.node; } };
10     int n=0, base=1; vector<Node> tr; vector<long double> a,b; long double now=0; priority_queue<Event> pq; const long double EPS=1e-18L;
11     KTTMinLines(const vector<long double>& A, const vector<long double>& B, long double t0=0){ build(A,B,t0);} KTTMinLines(){}
12     void build(const vector<long double>& A,const vector<long double>& B,long double t0=0){ a=A;b=B;n=(int)a.size();now=t0;base=1;while(base<n)base<<=1;tr.assign(2*base,Node());for(int i=0;i<base;i++){int v=base+i;tr[v].parent=v>>1;tr[v].winner=(i<n?i:-1);}for(int v=base-1;v>=1;--v){tr[v].left=v<<1;tr[v].right=v<<1|1;tr[v].parent=v>>1;pull(v);} }
13     int argmin() const { return tr[1].winner; } long double min_value() const { return value(tr[1].winner, now);} long double time_now() const { return now; }
14     void advance_to(long double T){ if(T<now) return; while(!pq.empty() && pq.top().t<=T+EPS){ long double t=pq.top().t; vector<Event> batch; while(!pq.empty() && fabsl(pq.top().t - t)<=EPS){ batch.push_back(pq.top()); pq.pop(); } now=max(now,t); for(auto &e:batch){ if(e.node<=0 || e.node>=(int)tr.size()) continue; auto &nd=tr[e.node]; if(nd.ver!=e.ver) continue; int v=e.node; recompute_node(v); int p=tr[v].parent; while(p>=1){ recompute_node(p); p=tr[p].parent; } } } now=T; }
15 
16     // Update a single function's parameters at the current time 'now'.
17     // After changing (a[i], b[i]), we recompute along its leaf-to-root path.
18     void update_function(int i, long double new_a, long double new_b) {
19         if (i < 0 || i >= n) return;
20         a[i] = new_a; b[i] = new_b;
21         // Invalidate and reschedule certificates on the path to root
22         int v = base + i; // leaf position
23         int p = tr[v].parent;
24         while (p >= 1) {
25             // Bump version to invalidate old events at this node and recompute
26             tr[p].ver++;
27             recompute_node(p);
28             p = tr[p].parent;
29         }
30     }
31 
32 private:
33     long double value(int i,long double t) const { if(i<0) return numeric_limits<long double>::infinity(); return a[i]*t + b[i]; }
34     bool leq(int i,int j,long double t) const { if(i==j) return true; long double vi=value(i,t), vj=value(j,t); if(fabsl(vi - vj)>EPS) return vi < vj; return i<j; }
35     long double failure_time(int winner,int loser) const { if(winner<0 || loser<0) return INFINITY; long double da=a[winner]-a[loser]; long double db=b[winner]-b[loser]; if(fabsl(da)<=EPS) return INFINITY; if(da>0){ long double tstar = -db/da; return tstar; } return INFINITY; }
36     bool recompute_node(int v){ if(v>=base) return false; int L=tr[v].left,R=tr[v].right; int lw=tr[L].winner, rw=tr[R].winner; int neww; if(lw<0) neww=rw; else if(rw<0) neww=lw; else neww=(leq(lw,rw,now)?lw:rw); bool changed=(neww!=tr[v].winner); tr[v].winner=neww; long double exp=INFINITY; if(lw>=0 && rw>=0){ int los=(neww==lw?rw:lw); exp=failure_time(neww,los); if(isfinite(exp) && exp<=now+1e-18L) exp=now; }
37         tr[v].expire=exp; tr[v].ver++; if(isfinite(exp)) pq.push({exp,v,tr[v].ver}); return changed; }
38     void pull(int v){ int L=v<<1,R=v<<1|1; int lw=tr[L].winner, rw=tr[R].winner; int neww; if(lw<0) neww=rw; else if(rw<0) neww=lw; else neww=(leq(lw,rw,now)?lw:rw); tr[v].winner=neww; long double exp=INFINITY; if(lw>=0 && rw>=0){ int los=(neww==lw?rw:lw); exp=failure_time(neww,los); } tr[v].ver=0; tr[v].expire=exp; if(isfinite(exp)) pq.push({exp,v,tr[v].ver}); }
39 };
40 
41 int main(){
42     ios::sync_with_stdio(false);
43     cin.tie(nullptr);
44 
45     vector<long double> A = {1.0L, -0.2L, 0.3L};
46     vector<long double> B = {0.0L, 5.0L, 1.0L};
47     KTTMinLines ktt(A,B,0.0L);
48 
49     cout << fixed << setprecision(6);
50     cout << "t=0: argmin=" << ktt.argmin() << ", val=" << ktt.min_value() << "\n";
51     ktt.advance_to(10.0L);
52     cout << "t=10: argmin=" << ktt.argmin() << ", val=" << ktt.min_value() << "\n";
53 
54     // Suppose function 1 changes trajectory at t=10 (e.g., a model update)
55     ktt.update_function(1, /*new a=*/-2.0L, /*new b=*/8.0L);
56     cout << "After update at t=10: argmin=" << ktt.argmin() << ", val=" << ktt.min_value() << "\n";
57 
58     ktt.advance_to(20.0L);
59     cout << "t=20: argmin=" << ktt.argmin() << ", val=" << ktt.min_value() << "\n";
60     return 0;
61 }
62

This example adds an update_function method to modify a leaf’s trajectory at the current time and reschedule certificates along its path to the root. It demonstrates how to handle occasional model updates without full rebuilding. Updates cost O(log n) node recomputations and rescheduling.

Time: O(log n) per update plus O(log n) per valid event during future advances; O(1) per argmin querySpace: O(n)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Kinetic Tournament Tree tracking argmin of linear functions f_i(t) = a_i * t + b_i.
5	// - Static set of n functions
6	// - Advance time by processing certificate failures in increasing time order
7	// - Query current argmin and its value in O(1)
8
9	struct KTTMinLines {
10	struct Node {
11	int left = -1, right = -1, parent = -1;
12	int winner = -1; // index of the winning leaf in this subtree
13	long double expire = INFINITY; // time when certificate may fail
14	unsigned long long ver = 0; // version to detect stale events
15	};
16
17	struct Event {
18	long double t;
19	int node;
20	unsigned long long ver;
21	bool operator<(Event const& o) const {
22	// Min-heap by time using priority_queue (invert comparison)
23	if (t != o.t) return t > o.t;
24	return node > o.node; // tie-break deterministically
25	}
26	};
27
28	int n = 0; // number of real functions
29	int base = 1; // power-of-two leaves
30	vector<Node> tr; // tree nodes, 1-indexed internal structure
31	vector<long double> a, b; // function parameters
32	long double now = 0.0L; // current time
33	priority_queue<Event> pq; // event queue
34	const long double EPS = 1e-18L;
35
36	KTTMinLines() {}
37
38	KTTMinLines(const vector<long double>& A, const vector<long double>& B, long double t0 = 0.0L) {
39	build(A, B, t0);
40	}
41
42	void build(const vector<long double>& A, const vector<long double>& B, long double t0 = 0.0L) {
43	a = A; b = B; n = (int)a.size(); now = t0;
44	// Build complete binary tree with power-of-two leaves
45	base = 1; while (base < n) base <<= 1;
46	tr.assign(2 * base, Node());
47	// Initialize leaves
48	for (int i = 0; i < base; ++i) {
49	int v = base + i;
50	tr[v].left = tr[v].right = -1;
51	tr[v].parent = (v >> 1);
52	tr[v].winner = (i < n ? i : -1);
53	}
54	// Build internal nodes
55	for (int v = base - 1; v >= 1; --v) {
56	tr[v].left = v << 1;
57	tr[v].right = v << 1 \| 1;
58	tr[v].parent = (v >> 1);
59	pull(v); // compute winner and schedule certificate
60	}
61	}
62
63	// Public API
64	int argmin() const { return tr[1].winner; }
65	long double min_value() const { return value(tr[1].winner, now); }
66	long double time_now() const { return now; }
67
68	// Process all events with time <= T. Optional callback fired when global argmin changes.
69	void advance_to(long double T, function<void(long double,int)> on_change = nullptr) {
70	if (T < now) return; // do not go back in time
71	// Process events in nondecreasing time
72	while (!pq.empty() && pq.top().t <= T + EPS) {
73	long double t = pq.top().t;
74	// Process all events at this time t (within EPS)
75	vector<Event> batch;
76	while (!pq.empty() && fabsl(pq.top().t - t) <= EPS) {
77	batch.push_back(pq.top()); pq.pop();
78	}
79	now = max(now, t); // jump to event time
80	// Validate and apply
81	bool root_changed = false;
82	for (auto &e : batch) {
83	if (e.node <= 0 \|\| e.node >= (int)tr.size()) continue;
84	Node &nd = tr[e.node];
85	if (nd.ver != e.ver) continue; // stale
86	// Recompute at node and propagate upward
87	int v = e.node;
88	bool changed = recompute_node(v);
89	int p = tr[v].parent;
90	while (p >= 1) {
91	bool ch = recompute_node(p);
92	changed = changed \|\| ch;
93	p = tr[p].parent;
94	}
95	root_changed = root_changed \|\| changed;
96	}
97	if (root_changed && on_change) on_change(now, argmin());
98	}
99	now = T;
100	}
101
102	private:
103	// Evaluate function i at time t
104	long double value(int i, long double t) const {
105	if (i < 0) return numeric_limits<long double>::infinity();
106	return a[i] * t + b[i];
107	}
108
109	// Is i <= j at time t? Deterministic tie-break by index
110	bool leq(int i, int j, long double t) const {
111	if (i == j) return true;
112	long double vi = value(i, t), vj = value(j, t);
113	if (fabsl(vi - vj) > EPS) return vi < vj;
114	return i < j;
115	}
116
117	// Compute failure time for inequality winner <= loser, assuming it holds at now
118	long double failure_time(int winner, int loser) const {
119	if (winner < 0 \|\| loser < 0) return INFINITY;
120	// d(t) = f_w(t) - f_l(t) = (aw - al) t + (bw - bl)
121	long double da = a[winner] - a[loser];
122	long double db = b[winner] - b[loser];
123	long double dnow = da * now + db;
124	// By assumption winner <= loser at now, so dnow <= 0 (up to EPS)
125	if (fabsl(da) <= EPS) {
126	// Parallel: if equal forever, no flip; else inequality maintains
127	return INFINITY;
128	}
129	// If slope difference is positive, d(t) increases; it will cross 0 once in the future.
130	if (da > 0) {
131	long double tstar = -db / da; // solve da*t + db = 0
132	if (tstar <= now + EPS) {
133	// Immediate or past crossing: treat as now to avoid missed flips
134	return now;
135	}
136	return tstar;
137	} else {
138	// da < 0: d(t) decreases; once <= 0, stays <= 0; no future flip
139	return INFINITY;
140	}
141	}
142
143	// Recompute winner and certificate at node v given current time 'now'
144	bool recompute_node(int v) {
145	if (v >= base) {
146	// leaf: nothing to schedule
147	return false;
148	}
149	int L = tr[v].left, R = tr[v].right;
150	int lw = tr[L].winner;
151	int rw = tr[R].winner;
152	int neww;
153	if (lw < 0) neww = rw;
154	else if (rw < 0) neww = lw;
155	else neww = (leq(lw, rw, now) ? lw : rw);
156	bool changed = (neww != tr[v].winner);
157	tr[v].winner = neww;
158	// Schedule certificate for this node based on current child winners
159	long double exp = INFINITY;
160	if (lw >= 0 && rw >= 0) {
161	int win = neww, los = (win == lw ? rw : lw);
162	exp = failure_time(win, los);
163	}
164	tr[v].expire = exp;
165	tr[v].ver++;
166	if (isfinite(exp)) {
167	pq.push(Event{exp, v, tr[v].ver});
168	}
169	return changed;
170	}
171
172	// Pull function used at build time (like recompute_node but bottom-up)
173	void pull(int v) {
174	if (v >= base) return;
175	int L = v << 1, R = v << 1 \| 1;
176	tr[v].left = L; tr[v].right = R;
177	int lw = tr[L].winner;
178	int rw = tr[R].winner;
179	int neww;
180	if (lw < 0) neww = rw;
181	else if (rw < 0) neww = lw;
182	else neww = (leq(lw, rw, now) ? lw : rw);
183	tr[v].winner = neww;
184	// schedule
185	long double exp = INFINITY;
186	if (lw >= 0 && rw >= 0) {
187	int win = neww, los = (win == lw ? rw : lw);
188	exp = failure_time(win, los);
189	}
190	tr[v].expire = exp;
191	tr[v].ver = 0;
192	if (isfinite(exp)) pq.push(Event{exp, v, tr[v].ver});
193	}
194	};
195
196	int main() {
197	ios::sync_with_stdio(false);
198	cin.tie(nullptr);
199
200	// Example: Track the minimum among linear functions
201	// f0(t) = 2t + 3, f1(t) = -1t + 10, f2(t) = 0.5t + 1
202	vector<long double> A = {2.0L, -1.0L, 0.5L};
203	vector<long double> B = {3.0L, 10.0L, 1.0L};
204
205	KTTMinLines ktt(A, B, /t0=/0.0L);
206
207	auto on_change = [&](long double t, int id){
208	cout << fixed << setprecision(6);
209	cout << "Change at t=" << t << ": argmin becomes f" << id
210	<< " with value " << ktt.min_value() << "\n";
211	};
212
213	cout << fixed << setprecision(6);
214	cout << "Initial t=0: argmin=f" << ktt.argmin() << ", value=" << ktt.min_value() << "\n";
215
216	// Advance time and observe changes
217	ktt.advance_to(5.0L, on_change);
218	cout << "At t=5: argmin=f" << ktt.argmin() << ", value=" << ktt.min_value() << "\n";
219	ktt.advance_to(20.0L, on_change);
220	cout << "At t=20: argmin=f" << ktt.argmin() << ", value=" << ktt.min_value() << "\n";
221
222	return 0;
223	}
224

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Reuse the same KTT for linear functions: x_i(t) = x0_i + vx_i * t
5	struct KTTMinLines {
6	struct Node { int left=-1,right=-1,parent=-1; int winner=-1; long double expire=INFINITY; unsigned long long ver=0; };
7	struct Event { long double t; int node; unsigned long long ver; bool operator<(Event const& o) const { if (t!=o.t) return t>o.t; return node>o.node; } };
8	int n=0, base=1; vector<Node> tr; vector<long double> a,b; long double now=0; priority_queue<Event> pq; const long double EPS=1e-18L;
9	KTTMinLines(const vector<long double>& A, const vector<long double>& B, long double t0=0){ build(A,B,t0);} KTTMinLines(){}
10	void build(const vector<long double>& A,const vector<long double>& B,long double t0=0){ a=A;b=B;n=(int)a.size();now=t0;base=1;while(base<n)base<<=1;tr.assign(2*base,Node());for(int i=0;i<base;i++){int v=base+i;tr[v].parent=v>>1;tr[v].winner=(i<n?i:-1);}for(int v=base-1;v>=1;--v){tr[v].left=v<<1;tr[v].right=v<<1\|1;tr[v].parent=v>>1;pull(v);} }
11	int argmin() const { return tr[1].winner; } long double min_value() const { return value(tr[1].winner, now);} long double time_now() const { return now; }
12	void advance_to(long double T, function<void(long double,int)> on_change=nullptr){ if(T<now) return; while(!pq.empty() && pq.top().t<=T+EPS){ long double t=pq.top().t; vector<Event> batch; while(!pq.empty() && fabsl(pq.top().t - t)<=EPS){ batch.push_back(pq.top()); pq.pop(); } now=max(now,t); bool root_changed=false; for(auto &e:batch){ if(e.node<=0 \|\| e.node>=(int)tr.size()) continue; auto &nd=tr[e.node]; if(nd.ver!=e.ver) continue; int v=e.node; bool changed=recompute_node(v); int p=tr[v].parent; while(p>=1){ bool ch=recompute_node(p); changed=changed\|\|ch; p=tr[p].parent; } root_changed=root_changed\|\|changed; } if(root_changed && on_change) on_change(now,argmin()); } now=T; }
13	private:
14	long double value(int i,long double t) const { if(i<0) return numeric_limits<long double>::infinity(); return a[i]*t + b[i]; }
15	bool leq(int i,int j,long double t) const { if(i==j) return true; long double vi=value(i,t), vj=value(j,t); if(fabsl(vi - vj)>EPS) return vi < vj; return i<j; }
16	long double failure_time(int winner,int loser) const { if(winner<0 \|\| loser<0) return INFINITY; long double da=a[winner]-a[loser]; long double db=b[winner]-b[loser]; if(fabsl(da)<=EPS) return INFINITY; if(da>0){ long double tstar = -db/da; return tstar; } return INFINITY; }
17	bool recompute_node(int v){ if(v>=base) return false; int L=tr[v].left,R=tr[v].right; int lw=tr[L].winner, rw=tr[R].winner; int neww; if(lw<0) neww=rw; else if(rw<0) neww=lw; else neww = (leq(lw,rw,now) ? lw : rw); bool changed=(neww!=tr[v].winner); tr[v].winner=neww; long double exp=INFINITY; if(lw>=0 && rw>=0){ int los=(neww==lw?rw:lw); exp=failure_time(neww,los); if(isfinite(exp) && exp<=now+1e-18L) exp=now; } tr[v].expire=exp; tr[v].ver++; if(isfinite(exp)) pq.push({exp,v,tr[v].ver}); return changed; }
18	void pull(int v){ int L=v<<1,R=v<<1\|1; int lw=tr[L].winner, rw=tr[R].winner; int neww; if(lw<0) neww=rw; else if(rw<0) neww=lw; else neww=(leq(lw,rw,now)?lw:rw); tr[v].winner=neww; long double exp=INFINITY; if(lw>=0 && rw>=0){ int los=(neww==lw?rw:lw); exp=failure_time(neww,los); }
19	tr[v].ver=0; tr[v].expire=exp; if(isfinite(exp)) pq.push({exp,v,tr[v].ver}); }
20	};
21
22	struct Pt { long double x0,y0,vx,vy; };
23
24	int main(){
25	ios::sync_with_stdio(false);
26	cin.tie(nullptr);
27
28	// Leftmost point among moving points with constant velocity: minimize x(t) = x0 + vx * t
29	vector<Pt> P = {
30	{0.0L, 0.0L, 0.5L, 0.1L}, // starts at x=0, drifting right
31	{5.0L, 1.0L, -0.4L, -0.2L}, // starts at x=5, moving left
32	{2.0L, 2.0L, 0.0L, 0.0L}, // stationary in x
33	{-1.0L, -3.0L, 0.2L, 0.0L} // starts left, moving right slowly
34	};
35
36	vector<long double> A, B; A.reserve(P.size()); B.reserve(P.size());
37	for (auto &p : P) { A.push_back(p.vx); B.push_back(p.x0); }
38
39	KTTMinLines ktt(A, B, /t0=/0.0L);
40
41	auto on_change = [&](long double t, int id){
42	cout << fixed << setprecision(6);
43	cout << "t=" << t << ": leftmost point index=" << id << ", x(t)=" << ktt.min_value() << "\n";
44	};
45
46	cout << fixed << setprecision(6);
47	cout << "Initial: leftmost index=" << ktt.argmin() << ", x(0)=" << ktt.min_value() << "\n";
48	ktt.advance_to(10.0L, on_change);
49	cout << "At t=10: leftmost index=" << ktt.argmin() << ", x(t)=" << ktt.min_value() << "\n";
50	return 0;
51	}
52

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Extension: support updating a single function's (a,b) at current time.
5	// We reuse and slightly extend the first KTT implementation.
6
7	struct KTTMinLines {
8	struct Node { int left=-1,right=-1,parent=-1; int winner=-1; long double expire=INFINITY; unsigned long long ver=0; };
9	struct Event { long double t; int node; unsigned long long ver; bool operator<(Event const& o) const { if (t!=o.t) return t>o.t; return node>o.node; } };
10	int n=0, base=1; vector<Node> tr; vector<long double> a,b; long double now=0; priority_queue<Event> pq; const long double EPS=1e-18L;
11	KTTMinLines(const vector<long double>& A, const vector<long double>& B, long double t0=0){ build(A,B,t0);} KTTMinLines(){}
12	void build(const vector<long double>& A,const vector<long double>& B,long double t0=0){ a=A;b=B;n=(int)a.size();now=t0;base=1;while(base<n)base<<=1;tr.assign(2*base,Node());for(int i=0;i<base;i++){int v=base+i;tr[v].parent=v>>1;tr[v].winner=(i<n?i:-1);}for(int v=base-1;v>=1;--v){tr[v].left=v<<1;tr[v].right=v<<1\|1;tr[v].parent=v>>1;pull(v);} }
13	int argmin() const { return tr[1].winner; } long double min_value() const { return value(tr[1].winner, now);} long double time_now() const { return now; }
14	void advance_to(long double T){ if(T<now) return; while(!pq.empty() && pq.top().t<=T+EPS){ long double t=pq.top().t; vector<Event> batch; while(!pq.empty() && fabsl(pq.top().t - t)<=EPS){ batch.push_back(pq.top()); pq.pop(); } now=max(now,t); for(auto &e:batch){ if(e.node<=0 \|\| e.node>=(int)tr.size()) continue; auto &nd=tr[e.node]; if(nd.ver!=e.ver) continue; int v=e.node; recompute_node(v); int p=tr[v].parent; while(p>=1){ recompute_node(p); p=tr[p].parent; } } } now=T; }
15
16	// Update a single function's parameters at the current time 'now'.
17	// After changing (a[i], b[i]), we recompute along its leaf-to-root path.
18	void update_function(int i, long double new_a, long double new_b) {
19	if (i < 0 \|\| i >= n) return;
20	a[i] = new_a; b[i] = new_b;
21	// Invalidate and reschedule certificates on the path to root
22	int v = base + i; // leaf position
23	int p = tr[v].parent;
24	while (p >= 1) {
25	// Bump version to invalidate old events at this node and recompute
26	tr[p].ver++;
27	recompute_node(p);
28	p = tr[p].parent;
29	}
30	}
31
32	private:
33	long double value(int i,long double t) const { if(i<0) return numeric_limits<long double>::infinity(); return a[i]*t + b[i]; }
34	bool leq(int i,int j,long double t) const { if(i==j) return true; long double vi=value(i,t), vj=value(j,t); if(fabsl(vi - vj)>EPS) return vi < vj; return i<j; }
35	long double failure_time(int winner,int loser) const { if(winner<0 \|\| loser<0) return INFINITY; long double da=a[winner]-a[loser]; long double db=b[winner]-b[loser]; if(fabsl(da)<=EPS) return INFINITY; if(da>0){ long double tstar = -db/da; return tstar; } return INFINITY; }
36	bool recompute_node(int v){ if(v>=base) return false; int L=tr[v].left,R=tr[v].right; int lw=tr[L].winner, rw=tr[R].winner; int neww; if(lw<0) neww=rw; else if(rw<0) neww=lw; else neww=(leq(lw,rw,now)?lw:rw); bool changed=(neww!=tr[v].winner); tr[v].winner=neww; long double exp=INFINITY; if(lw>=0 && rw>=0){ int los=(neww==lw?rw:lw); exp=failure_time(neww,los); if(isfinite(exp) && exp<=now+1e-18L) exp=now; }
37	tr[v].expire=exp; tr[v].ver++; if(isfinite(exp)) pq.push({exp,v,tr[v].ver}); return changed; }
38	void pull(int v){ int L=v<<1,R=v<<1\|1; int lw=tr[L].winner, rw=tr[R].winner; int neww; if(lw<0) neww=rw; else if(rw<0) neww=lw; else neww=(leq(lw,rw,now)?lw:rw); tr[v].winner=neww; long double exp=INFINITY; if(lw>=0 && rw>=0){ int los=(neww==lw?rw:lw); exp=failure_time(neww,los); } tr[v].ver=0; tr[v].expire=exp; if(isfinite(exp)) pq.push({exp,v,tr[v].ver}); }
39	};
40
41	int main(){
42	ios::sync_with_stdio(false);
43	cin.tie(nullptr);
44
45	vector<long double> A = {1.0L, -0.2L, 0.3L};
46	vector<long double> B = {0.0L, 5.0L, 1.0L};
47	KTTMinLines ktt(A,B,0.0L);
48
49	cout << fixed << setprecision(6);
50	cout << "t=0: argmin=" << ktt.argmin() << ", val=" << ktt.min_value() << "\n";
51	ktt.advance_to(10.0L);
52	cout << "t=10: argmin=" << ktt.argmin() << ", val=" << ktt.min_value() << "\n";
53
54	// Suppose function 1 changes trajectory at t=10 (e.g., a model update)
55	ktt.update_function(1, /new a=/-2.0L, /new b=/8.0L);
56	cout << "After update at t=10: argmin=" << ktt.argmin() << ", val=" << ktt.min_value() << "\n";
57
58	ktt.advance_to(20.0L);
59	cout << "t=20: argmin=" << ktt.argmin() << ", val=" << ktt.min_value() << "\n";
60	return 0;
61	}
62