Kinetic Tournament Tree

Prerequisite knowledge: Segment Tree

Problem Introduction

Given a sequence of univariate linear functions $F=\{f_1,\dots,f_n\}$: $f_i: \mathbf{R} \rightarrow \mathbf{R}$. Here $f_i(x)=k_ix+b_i$ and $k_i,b_i \in \mathbf{R}$. We need to maintain the following operations:

• $\operatorname{QueryMax}(l,r)$: Given $l$ and $r$, return $\max_{i=l}^r{f_i(0)}$.
• $\operatorname{TranslateLeft}(l,r,\delta)$: Given $l$, $r$, and $\delta$, for every $i\in[l,r]$, perform $f_i(x) \leftarrow f_i(x+\delta)$. This is equivalent to performing $b_i\leftarrow b_i+k_i\delta$. Here $\delta > 0$.

For convenience, assume that all functions are distinct.

The essence of translating a function interval to the left is $b_i \leftarrow k_i\cdot \delta$: for the constant term $b_i$, add the slope $k_i$ multiplied by the horizontal translation amount $\delta$. This operation is equivalent to the “position-coefficient-weighted range addition” encountered in many data-structure problems: for every index in the interval $[l, r]$, namely $i$, add a fixed number $\delta$ multiplied by the coefficient $k_i$ specific to that position. Thus, a function-interval translation is essentially position-coefficient-weighted range addition.

To demonstrate KTT's distinctive binary-tree divide-and-conquer structure, we start directly with interval translation.

Kinetic Data Structures

Kinetic Data Structures is abbreviated as KDS. KDS maintains properties of systems of geometric objects during continuous motion.

Event Queue

We assume that every point has a known motion plan, which can provide complete or partial information about its motion. For example, the curve or line formed by the function $f_i(x)$ can describe the trajectory of moving point $i$ well. A motion plan may change at any time, for example because of a collision or interaction with the environment; we call the cause of a motion-plan change an event. The event queue lists events in chronological order.

A key aspect of a KDS is to have events that are easy to maintain: event types in the event queue correspond to possible combinatorial changes involving a constant, usually small, number of objects. For example, in this problem, one event type we use is “the ordering of the values of function $f_i(0)$ and function $f_{j}(0)$ changes.”

The event queue can be maintained implicitly.

Certificates

These events should be equivalently guaranteed by the intersection of a series of low-degree algebraic conditions, each involving a finite number of objects. We call these conditions KDS certificates. For example, $[f_i(0) > f_j(0)]$.

Kinetic Tournament Tree

Introduction

Kinetic Tournament Tree (KTT for short), a member of Kinetic Data Structures, first appeared in 1999 in Data Structures for Mobile Data for maintaining continuously changing data. More generally, any structure using the following kinetization strategy can be called a Kinetic Tournament:

• Generate correctness certificates for key operations in a static algorithm (such as comparisons), associate each certificate with a global event queue, and record when the certificate may fail.
• When a certificate fails, efficiently update the algorithm output and maintain the set of certificates.

In the algorithm-contest community, it rose to prominence through the 2020 National Training Team paper On Dynamically Maintaining Function Extremes. Academic KTTs and contest KTTs differ in application and implementation, so we introduce a KTT with some optimizations for the algorithm-contest setting.

Basic Structure

First consider a data structure similar to a segment tree for maintaining a static maximum. Build the segment-tree structure; for each non-leaf node, its value is the larger value of its two children. After $O(n)$ comparisons, the value at the root is the global maximum. Now the values begin to change. As long as KTT can detect every change in the source of the maximum at a tree node, we can maintain the global maximum.

To let KTT detect every change in the source of a node's maximum, for a tree node $x$ and the functions $f_L$ and $f_R$ supplied by its left and right children, define the certificate as “the ordering between $f_L$ and $f_R$ remains unchanged.” When the certificate fails, we need to follow the tree path to the node where the certificate failed and update its information. To maintain the failure time of each certificate, observe that a certificate fails exactly when the two functions have equal values. The problem therefore becomes finding the x-coordinate of the intersection of two linear functions, which can be solved in $O(1)$ time.

For each tree node, maintain the function attaining the maximum value at $0$, the current certificate-failure time, and the earliest certificate-failure time in the entire subtree. Then, when a node's certificate fails, we can find it at that time and update its information. These data record information about the functions themselves. Next consider maintaining interval translations. Since they can be accumulated by addition, we can process them with lazy tags.

Define the lazy tag $\Delta_v$ to mean that every function at another node in the subtree of node $v$ should be translated left by $\Delta_v$ units. For a tree node $v$, a new operation translating all functions in its subtree left by $\delta$, namely $f(x)\leftarrow f(x+\delta)$, requires updating the lazy tag: $\Delta_v\leftarrow \Delta_v + \delta$, accumulating the offsets of all other nodes in the subtree. Translating left also changes the function values at $0$. If the certificate-failure x-coordinate is $t$, then after translation it should be $t-\delta$; if $t-\delta$ crosses $0$, the certificate has failed, so we recursively find the node containing the certificate, update that node, and propagate the new information up to the root. This process can be performed together with the modification.

Thus we obtain a simple implementation.

struct node {
  int l, r;
  int tag;   // the lazy propagation tag
  int k, b;  // the linear function
  int swc;   // the time of certificate violation
};

vector<node> v;

int IntegerPart(double x) {
  if (x >= 0 && x <= inf) return int(ceil(x));
  return inf;
}

void push_up(int rt) {
  int mx = v[rt << 1].b > v[rt << 1 | 1].b ? rt << 1 : rt << 1 | 1, mi = mx ^ 1;
  v[rt].k = v[mx].k, v[rt].b = v[mx].b;
  v[rt].swc = v[mx].k < v[mi].k
                  ? IntegerPart(1.0 * (v[mx].b - v[mi].b) / (v[mi].k - v[mx].k))
                  : inf;
}

void push_tag(int rt, int val) {
  v[rt].tag += val, v[rt].swc -= val, v[rt].b += v[rt].k * val;
}

void push_down(int rt) {
  if (v[rt].tag)
    push_tag(rt << 1, v[rt].tag), push_tag(rt << 1 | 1, v[rt].tag),
        v[rt].tag = 0;
}

void checkswitch(int rt) {
  if (v[rt].l == v[rt].r) return;
  push_down(rt);
  if (v[rt].swc <= 0) checkswitch(rt << 1), checkswitch(rt << 1 | 1);
  push_up(rt);
}

void build(int rt, int l, int r) {
  v[rt].l = l, v[rt].r = r;
  if (l == r) return v[rt].k = k[l], v[rt].b = b[l], void();
  int mid = (l + r) >> 1;
  build(rt << 1, l, mid);
  build(rt << 1 | 1, mid + 1, r);
  push_up(rt);
}

void TranslateLeft(int rt, int l, int r, int val) {
  if (l <= v[rt].l && v[rt].r <= r) return push_tag(rt, val), checkswitch(rt);
  int mid = v[rt << 1].r;
  push_down(rt);
  if (l <= mid) TranslateLeft(rt << 1, l, r, val);
  if (mid < r) TranslateLeft(rt << 1 | 1, l, r, val);
  push_up(rt);
}

int QueryMax(int rt, int l, int r) {
  if (l <= v[rt].l && v[rt].r <= r) return v[rt].b;
  int mid = v[rt << 1].r, res = 0;
  push_down(rt);
  if (l <= mid) res = max(res, QueryMax(rt << 1, l, r));
  if (mid < r) res = max(res, QueryMax(rt << 1 | 1, l, r));
  return res;
}

Complexity Analysis

Proving the time complexity of KTT requires potential analysis.

Let $d(x)$ be the depth of node $x$ in the segment tree, with the root at depth $1$. Define the potential of node $x$ in the segment tree as:

That is, when comparing the two functions at $x$, if the function with the smaller slope has the larger value at $0$, the current node's potential is $d(x)$; otherwise it is $0$.

Define the potential of the entire KTT as the sum of the potentials of all nodes:

Consider an update of node $x$ and its parent $p$ with actual cost $c=1$, and let the potentials before and after the update be $\Phi$ and $\Phi'$, respectively. We calculate the amortized cost of updating node $x$. Because node $x$ is updated, its potential at that moment must decrease from $d(x)$ to $0$. For $p$, its potential may in the worst case increase from $0$ to $d(p)$:

Summing the actual costs, define the initial potential $\Phi_s$ and the final potential $\Phi_t$:

This is the number of updates required by KTT, when only global modifications exist, to finish updating all failed certificates.

In addition, consider the effect of interval translations on the potential. For an interval translation, the nodes to consider are those whose subtrees contain some but not all nodes affected by the interval translation. These are exactly the nodes traversed in the tree while performing the modification, and there are at most $O(\log n)$ of them. In the worst case, each node's potential increases by $d(x)\le \log n$, so each operation increases the potential by $O(\log^2 n)$.

To maintain interval translations, certificate updates are performed $O(n\log n + m\log^2 n)$ times. Each certificate update requires following a path in the tree to the failed certificate, which takes $O(\log n)$ time. Thus the total time complexity is $O(n\log^2 n+ m\log^3 n)$.

The strength of this method is that it reaches the lower bound $O(\lambda_{s}(n)\log^2 n)$ for the problem's time complexity. Here $\lambda_{s}(n)$ denotes the longest Davenport–Schinzel sequence of type (n, s). For linear functions, $s=1$ and $\lambda_1(n)=n$. This is computational-geometry material and is omitted here.

Higher-Degree Case

If we maintain polynomial functions or more complicated functions instead of linear functions, how should we proceed? Two complicated functions may have multiple intersections. Given a continuous, fully defined sequence of univariate functions $F=\{f_1,\dots,f_n\}$: $f_i: \mathbf{R} \rightarrow \mathbf{R}$. Every pair of function graphs intersects at most $s$ times. A representative example satisfying this condition is a collection of degree-$s$ polynomial functions.

For the same problem, we use potential analysis.

Let $d(x)$ be the depth of node $x$ in the segment tree, with the root at depth $1$. Let $I(x)$ denote, at node $x$, the number of intersections after $0$ between the two functions compared there. Define the potential of node $x$ in the segment tree as:

Define the potential of the entire KTT as the sum of the potentials of all nodes:

Consider an update of node $x$ and its parent $p$ with actual cost $c=1$, and let the potentials before and after the update be $\Phi$ and $\Phi'$, respectively. We calculate the amortized cost of updating node $x$. Because node $x$ is updated, its potential at that moment must decrease from $d(x)^{\log_2(s+1)}I(x)$ to $d(x)^{\log_2(s+1)}(I(x)-1)$. For $p$, its potential may in the worst case increase from $0$ to $d(p)^{\log_2(s+1)}$:

From the third line to the fourth line, we use the fact that $d(x)$ is a positive integer.

Summing the actual costs, define the initial potential $\Phi_s$ and the final potential $\Phi_t$:

We obtain the upper bound $O(ns (\log n)^{1+\log_2{(s+1)}} + ms (\log n)^{2+\log_2{(s+1)}})$. ¹

Approximation Case

Given a continuous, fully defined sequence of univariate functions $F=\{f_1,\dots,f_n\}$, define $\mathfrak U_F(x)$, $\mathfrak L_F(x)$, and $\mathfrak E_F(x)$ as the upper envelope, lower envelope, and extent, respectively.

We only require the program to return $\tilde{\mathfrak U}_F(x)$ satisfying

Then in the general case, we can achieve $O((1/\epsilon^2)n\log^3 n)$, independent of the polynomial degree, and allow the functions to be translated left or right over intervals.

References and Notes

• P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. Approximating extent measures of points. J. ACM, 51(4):606–635, July 2004.
• J. Basch, L. J. Guibas, and J. Hershberger. Data structures for mobile data. Journal of Algorithms, 31(1):1–28, 1999.
• G. Alexandron, H. Kaplan, and M. Sharir. Kinetic and dynamic data structures for convex hulls and upper envelopes. Computational Geometry, 36(2):144–158, 2007.