Kinetic Tournament Tree

Prerequisites: Segment Tree

Problem Introduction

Given a sequence of univariate linear functions \(F=\{f_1,\dots,f_n\}\): \(f_i: \mathbf{R} \rightarrow \mathbf{R}\), where \(f_i(x)=k_ix+b_i\) and \(k_i,b_i \in \mathbf{R}\). We need to support 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 all \(i\in[l,r]\), perform the operation \(f_i(x) \leftarrow f_i(x+\delta)\), which is equivalent to performing \(b_i\leftarrow b_i+k_i\delta\). Here \(\delta > 0\).

For convenience, we assume all functions are distinct.

The essence of translating a segment of linear functions to the left is \(b_i \leftarrow k_i\cdot \delta\), i.e., for the constant term \(b_i\), we 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 each index \(i\) in the interval \([l, r]\), add a fixed number \(\delta\) multiplied by the position-specific coefficient \(k_i\) to its value. Therefore, translating a segment of linear functions is essentially a position-coefficient weighted range addition.

To demonstrate the unique binary tree divide-and-conquer structure of KTT, we will start directly with segment translation.

Kinetic Data Structures

Kinetic Data Structures, abbreviated as KDS, are used to maintain properties of geometric object systems undergoing continuous motion.

Event Queue

We assume each point has a known motion plan, which can provide complete or partial motion information. For example, the curve or line formed by the function \(f_i(x)\) can well describe the motion trajectory of moving point \(i\). The motion plan may change at any time, possibly due to collisions or environmental interactions; we call the cause of such changes an event. The event queue provides events in chronological order.

A key aspect of KDS is the need to maintain events easily, meaning the event types in the event queue correspond to possible combinatorial changes involving a constant and usually small number of objects. For example, in the maintenance for this problem, one event type we use is "the order of \(f_i(0)\) and \(f_{j}(0)\) changes".

The event queue can be maintained implicitly.

Certificates

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

Kinetic Tournament Tree

Introduction

The Kinetic Tournament Tree (KTT) belongs to Kinetic Data Structures and first appeared in the 1999 paper Data Structures for Mobile Data, used for maintaining continuously changing data. More generally, any structure adopting the following kinetization strategy can be called a Kinetic Tournament:

• Generate correctness certificates for key operations (e.g., comparisons) in the static algorithm, and associate each certificate with a global event queue, recording the time point when the certificate might fail.
• When a certificate fails, we can efficiently update the algorithm's output and maintain the set of certificates.

In the competitive programming community, it gained popularity from the 2020 Chinese National Team paper 浅谈函数最值的动态维护. The KTT in academia and the KTT in competitive programming differ in application areas and implementation, so we will introduce a version optimized for competitive programming.

Basic Structure

First, consider designing a data structure similar to a segment tree to maintain the static maximum. We build the segment tree structure; for each non-leaf node, its value is the larger of its two children's values. After \(O(n)\) comparisons, the root's value is the global maximum. Now, the values start changing. As long as KTT can detect every change in the source of the maximum value on the tree, we can maintain the global maximum.

To enable KTT to detect each change in the maximum source on the tree, for a tree node \(x\) and the functions \(f_L\) and \(f_R\) provided by its left and right children, we define the certificate as "the order relation between \(f_L\) and \(f_R\) remains unchanged". When a certificate fails, we need to walk down the tree path to the node where the certificate failed to update its information. To maintain the failure time of each certificate, we note that the moment a certificate fails is precisely when the two functions have equal values. Thus, the problem reduces to finding the x-coordinate of the intersection of two linear functions, which can be solved in \(O(1)\) time.

For each tree node, we maintain the function that achieves the maximum at \(0\), the current certificate failure time, and the earliest certificate failure time in the entire subtree. Then, at the moment a node's certificate fails, we can find it and update its information. This information is used to record the function's own data. Next, we consider maintaining the segment translation operation. Since it is additive, we can use lazy propagation to handle segment translation.

We define a lazy tag \(\Delta_v\) indicating that all functions on nodes in the subtree of \(v\) should be translated left by \(\Delta_v\) units. Now, for a tree node \(v\), a new operation wants to translate all functions in its subtree left by \(\delta\), i.e., \(f(x)\leftarrow f(x+\delta)\). We need to update the lazy tag: \(\Delta_v\leftarrow \Delta_v + \delta\), accumulating the offset for all other nodes in the subtree. Simultaneously, left translation also changes the function value at \(0\). We can observe that if the certificate's failure x-coordinate is \(t\), then after translation, the failure x-coordinate becomes \(t-\delta\). If \(t-\delta\) crosses \(0\), it means the certificate fails, and we need to recursively descend to find the node where the certificate is located, update the current node, and propagate the new information up to the root. This process can be performed along with the modification.

Thus, we can obtain a simple implementation.

Reference 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 depth being \(1\). Define the potential of node \(x\) in the segment tree as:

\[ \alpha(x) = \begin{cases} d(x) & \text{if the lower slope function has larger value} \\ 0 & \text{otherwise}\\ \end{cases} \]

That is, for the two functions compared at \(x\), if the function with the smaller slope has a larger value at \(0\), then the current node's potential is \(d(x)\); otherwise, it is \(0\).

Define the total potential of the KTT as the sum of all node potentials:

\[ \Phi = \sum_x \alpha(x) \]

Consider an actual update cost \(c=1\) for some node \(x\) and its parent \(p\), with potentials before and after the update being \(\Phi\) and \(\Phi'\). We compute the amortized update cost for updating node \(x\). Since node \(x\) is updated, its potential must drop from \(d(x)\) to \(0\) at that moment. For \(p\), the worst-case potential might rise from \(0\) to \(d(p)\):

\[ \begin{aligned} \hat{c} &= 1 + \Phi' - \Phi\\ &= 1 + (\alpha'(p) + \alpha'(x)) - (\alpha(p) + \alpha(x))\\ &= 1 + (\alpha'(p) - \alpha(p)) + (\alpha'(x) - \alpha(x))\\ &\leq 1 + d(p) - d(x)\\ &= 0 \end{aligned} \]

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

\[ \begin{aligned} \sum c &= \sum \hat{c} + \Phi_{s} - \Phi_{t}\\ &\leq \Phi_{s} - \Phi_{t}\\ &=O(n\log n) \end{aligned} \]

This part represents the number of times KTT updates all certificate failures under only global modifications.

Additionally, consider the impact of segment translation on potential. For a segment translation, the nodes we need to consider are those whose subtree contains, but does not entirely consist of, nodes affected by the translation. These are precisely the nodes traversed during the modification operation, numbering at most \(O(\log n)\). 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 segment translation, certificate updates will be performed \(O(n\log n + m\log^2 n)\) times. Each certificate update requires walking down the tree path to the failing node, which costs \(O(\log n)\). Therefore, the total time complexity is \(O(n\log^2 n+ m\log^3 n)\).

The excellence of this method lies in the fact that it touches the lower bound of the problem's time complexity, \(O(\lambda_{s}(n)\log^2 n)\). Here, \(\lambda_{s}(n)\) denotes the length of the longest (n, s) Davenport-Schinzel sequence. For linear functions, corresponding to \(s=1\), we have \(\lambda_1(n)=n\). This belongs to computational geometry and will not be elaborated here.

Higher-Degree Cases

How do we handle cases where we maintain polynomial functions or more complex functions instead of linear ones? Two complex functions may have multiple intersection points. Given a continuous, fully defined univariate function sequence \(F=\{f_1,\dots,f_n\}\): \(f_i: \mathbf{R} \rightarrow \mathbf{R}\), where the graphs of each pair of functions intersect at most \(s\) points. Representatively, sets of degree-\(s\) polynomial functions satisfy this requirement.

For the same problem, we use potential analysis.

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

\[ \alpha(x)=d(x)^{\log_2(s+1)}I(x) \]

Define the total potential of the KTT as the sum of all node potentials:

\[ \Phi = \sum_x \alpha(x) \]

Consider an actual update cost \(c=1\) for some node \(x\) and its parent \(p\), with potentials before and after the update being \(\Phi\) and \(\Phi'\). We compute the amortized update cost for updating node \(x\). Since node \(x\) is updated, its potential must drop from \(d(x)^{\log_2(s+1)}I(x)\) to \(d(x)^{\log_2(s+1)}(I(x)-1)\). For \(p\), the worst-case potential might rise from \(0\) to \(d(p)^{\log_2(s+1)}\):

\[ \begin{aligned} \hat{c} &= 1 + \Phi' - \Phi\\ &= 1 + (\alpha'(x) - \alpha(x)) + (\alpha'(p) - \alpha(p))\\ &\leq 1 - d(x)^{\log_2{(s+1)}} + s(d(x)-1)^{\log_2{(s+1)}}\\ &\leq 0 \end{aligned} \]

From the third to the fourth line, we used the constraint that \(d(x)\) is a positive integer.

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

\[ \begin{aligned} \sum c &= \sum \hat{c} - \Phi_t + \Phi_s\\ &\leq \Phi_s - \Phi_t\\ &= O(ns (\log n)^{\log_2{(s+1)}}) \end{aligned} \]

We obtain an upper bound on complexity: \(O(ns (\log n)^{1+\log_2{(s+1)}} + ms (\log n)^{2+\log_2{(s+1)}})\).¹

Approximate Case

Given a continuous, fully defined univariate function sequence \(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 spread, respectively.

\[ \begin{aligned} \mathfrak U_F(x) & = \max\{f_i(x) \mid f_i \in F\} \\ \mathfrak L_F(x) & = \min\{f_i(x) \mid f_i \in F\} \\ \mathfrak E_F(x) & = \mathfrak U_F(x) - \mathfrak L_F(x) \end{aligned} \]

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

\[ \mathfrak U_F(x) \geq \tilde{\mathfrak U}_F(x) \geq \mathfrak U_F(x) - \epsilon \mathfrak E_F(x) \]

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

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.

---

1. Note that this only provides an upper bound; the lower bound of complexity should be \(O(\lambda_{s}(n)\log n)\). The author speculates that the potential analysis construction here should refer to the general formula for \(\lambda_{s}(n)\) corresponding to Davenport-Schinzel sequences to obtain a tighter upper bound. ↩

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用