An Online Incremental Construction for Strong Interval Tree in O(nα(n)) Time

· · 算法·理论

Author: 我

Abstract

We present an online algorithm for the incremental construction of the strong interval tree of a permutation in O(n\alpha(n)) time and O(n) space. The algorithm explicitly tracks the structural changes in the strong interval forest caused by appending a new integer to the permutation. Owing to the slow growth of the inverse Ackermann function, the algorithm is near-optimal with respect to the information-theoretic lower bound. We revisit the basic properties of intervals and the known O(n) offline incremental construction, and then show how to convert the offline algorithm into an online one using a data structure for range semigroup queries——a modest but novel contribution.

Keywords: Strong Interval Tree, Sparse Table, Segment Tree, Ackermann Function

MSC2020: 68R05, 68P05, 68W40

1. Introduction

Throughout this paper, closed intervals may be degenerate: when l=r, [l,r] denotes the singleton \{l\}. All intervals are over the integers, so [l,r]=\{k\in\mathbb Z:l\le k\le r\} with l\le r.

Definition 1.1. Let P=\{p_i\}_{i=1}^n be a permutation.

  1. A factor of P is a contiguous subsequence P_{[L,R]}=\{p_i\}_{i=L}^R.
  2. An interval of P is a factor P_{[L,R]} whose values form a consecutive integer set, i.e., \operatorname{range}(P_{[L,R]}):=\{p_i:i\in[L,R]\}=[l,r] for some l,r\in[n]. Let I_P denote the set of all intervals of P.
  3. A strong interval is an interval x such that for every y\in I_P,
x\subseteq y \quad\text{or}\quad x\supseteq y \quad\text{or}\quad x\cap y=\varnothing.

We first record a basic property of intervals.

Lemma 1.1. Let x,y\in I_P. If x\nsubseteq y, x\nsupseteq y, and x\cap y\neq\varnothing, then x\cap y, x\cup y, x\setminus y, and y\setminus x are all intervals. Moreover, if we define a partial order on I_P by x<y \iff a<b for all a\in x, b\in y, then either

x\setminus y < x\cap y < y\setminus x

or

x\setminus y > x\cap y > y\setminus x.

Proof. Write x=P_{[L_1,R_1]}, y=P_{[L_2,R_2]}, \operatorname{range}(x)=[l_1,r_1], \operatorname{range}(y)=[l_2,r_2]. Assume without loss of generality that L_1<L_2\le R_1<R_2. Then x\cap y=P_{[L_2,R_1]} and \operatorname{range}(x\cap y)=[l_1,r_1]\cap[l_2,r_2]\neq\varnothing. Since neither [L_1,R_1] nor [L_2,R_2] contains the other, the same holds for [l_1,r_1] and [l_2,r_2]; hence either l_1<l_2\le r_1<r_2 or l_1>l_2\ge r_1>r_2. In the first case,

\operatorname{range}(x\cup y)=[l_1,r_2],\quad \operatorname{range}(x\setminus y)=[l_1,l_2-1],\\ \operatorname{range}(x\cap y)=[l_2,r_1],\quad \operatorname{range}(y\setminus x)=[r_1+1,r_2],

which gives the desired order. The second case is symmetric. \square

Intervals correspond to modules in permutation graphs and are central to substitution decomposition theory [2]. Understanding their structure is therefore of combinatorial significance.

Definition 1.2. The strong interval tree of a permutation is the rooted tree whose nodes are the strong intervals, with the parent of a node defined as the shortest strong interval properly containing it. The root is the whole permutation, and the leaves are the unit intervals.

Each node has at most one parent, so the structure is indeed a tree. A non-leaf strong interval x is the disjoint union of its children: they are pairwise disjoint by Definition 1.1, and every leaf inside x must lie in exactly one child.

Definition 1.3. Order the k children of a node x from left to right. Let q_i denote the rank of the i-th child in the partial order on intervals. Then Q=\{q_i\}_{i=1}^k is a permutation, called the children permutation of x.

Children permutations have a special structure.

Lemma 1.2. For a children permutation Q of length k\ge 3, every proper factor of length at least 2 is either an interval or not——uniformly.

Proof.

Call \{i_j\}_{j=1}^c a comparable partition of Q if

1\le i_1<i_2<\cdots<i_c\le k+1

and

Q_{[i_1,i_2-1]}<Q_{[i_2,i_3-1]}<\cdots<Q_{[i_{c-1},i_c-1]}

or the reverse chain holds.

Suppose Q_{[L_0,R_0]} is an interval, neither the whole Q nor a singleton. Let s_j be the j-th child of x. Then y=\bigcup_{j=L_0}^{R_0} s_j is not strong, so there exists another interval w that overlaps but does not contain y. By Definition 1.1 and Lemma 1.1, w must be a union of consecutive children, say \bigcup_{j=L_1}^{R_1} s_j. If L_0<L_1\le R_0<R_1, then \{L_0,L_1,R_0+1,R_1+1\} is comparable. Repeating this argument forces the entire set \{1,\dots,k+1\} to be comparable, meaning Q is either \{1,2,\dots,k\} or \{k,k-1,\dots,1\}. \square

Nodes of the first type are called linear, and nodes of the second type prime. The strong interval tree gives a complete description of all intervals.

Theorem 1.1. For a linear node x with children s_1,\dots,s_k, every union \bigcup_{i=L}^R s_i with [L,R]\subsetneq[1,k] and R-L\ge1 is a non-strong interval. Conversely, every non-strong interval arises in this way from a unique linear node.

Proof. The first direction is immediate. For the converse, let y be a non-strong interval, and let x be the shortest strong interval containing y. Then y cannot partially overlap a child of x; otherwise Definition 1.1 would be violated. Hence y is a union of consecutive children. Since y is not strong, it must be a proper union of at least two children, which forces x to be linear. \square

We now turn to the algorithmic problem: how to construct the strong interval tree efficiently.

2. An Offline Incremental Construction

It is known [3] that the strong interval tree can be constructed in O(n) time. In particular, an incremental approach is feasible [4].

Definition 2.1. A maximal interval of a factor is an interval not properly contained in any other interval of that factor.

The maximal intervals of a factor partition it: they are disjoint by Lemma 1.1, and every position belongs to at least one maximal interval.

At step i, we have already built the strong interval forest for the maximal intervals of the prefix P_{[1,i-1]}. We must update this forest to reflect the extension to P_{[1,i]}.

Theorem 2.1. All non-root strong intervals of the current forest remain in the final tree. Only linear roots may be removed.

Proof. Suppose a non-root node P_{[L_1,R_1]} is destroyed because a new interval P_{[L_2,i]} violates Definition 1.1. Then necessarily L_1<L_2\le R_1<i. Let P_{[L_3,R_3]} be the parent of P_{[L_1,R_1]}. Then P_{[L_2,R_3]} is an interval. Since the child was strong, it must have been the rightmost child of its parent; otherwise P_{[L_2,L_3]} would already violate Definition 1.1. By Lemma 1.1, the child is either the largest or smallest among its siblings, so its parent is linear (Lemma 1.2). If it is the largest, then

P_{[L_1,L_2-1]}<P_{[L_2,R_1]}<P_{[R_1+1,i]},

which implies that the union of P_{[L_1,L_2-1]} with P_{[L_1,R_1]}'s previous sibling is an interval, contradicting Definition 1.1. The second assertion is clear. \square

Theorem 2.1 identifies which nodes survive and which are deleted. The next theorem describes the new nodes.

Theorem 2.2. Any new strong interval introduced by appending an element has the form P_{[L,i]}, where L is the left endpoint of some original maximal interval.

Proof. A non-strong interval cannot become strong, so any new interval must have right endpoint i. If L split an original maximal interval, Definition 1.1 would be violated. \square

Based on these two theorems and a simple fact that all deleted nodes are contained by the new maximal interval, the following algorithm is correct: maintain a stack of maximal intervals, with intervals closer to the right end of P stored closer to the top. When inserting p_i, pop the top element P_{[L,R]}, delete it if it is no longer strong, and insert P_{[L,i]} if it is an interval. Repeat until no more strong intervals appear, then push the last inserted node onto the stack as a new maximal interval.

Since P_{[L,R]} is an interval iff \max_{j=L}^R p_j-\min_{j=L}^R p_j=R-L, interval tests can be done in O(1) time using a w-block sparse table [5]. The total number of stack operations is O(n).

Let P_{[L,i]} be an arbitrary factor. The shortest new strong interval containing it is at least P_{[L',i]}, where

L'=\min_{j=m}^M p^{-1}_j =\min_{j=L}^{i-1} \left\{ \min_{k=\min(p_j,p_{j+1})}^{\max(p_j,p_{j+1})} p^{-1}_k \right\},\\ m=\min_{j=L}^i p_j,\quad M=\max_{j=L}^i p_j,\quad p_{p^{-1}_j}=j.

In other words, L must expand to at least L' to fill the gaps in \operatorname{range}(P_{[L,i]}). If P_{[L,i]} is an interval, then L'=L; otherwise L'<L. Thus, repeatedly replacing L by L' until it stabilizes yields the next new strong interval.

This iterative process can be expressed by the recurrence

m_j=\min_{k=\min(p_j,p_{j+1})}^{\max(p_j,p_{j+1})} p^{-1}_k,\qquad l_j=\min\left\{\min_{k=m_j}^{j-1} l_k,\ j\right\},

where l_j denotes the rightmost index to which the left endpoint must extend in order to cover all values between p_j and p_{j+1}.

Then the successor of interval P_{[L,i]} is P_{[l_{L-1},i]}. Since {\rm range}(P_{[L,i]})=\bigcup_{j=L}^{i-1} {\rm range}(P_{[j,j+1]}) holds when L<i, this recurrence is equivalent to the previous iteration. The process stops when P_{[l_{L-1},i]} is not an interval. The values m_j can be computed via the same w-block sparse table. However, l_j is a variation of the static RMQ problem with append operations. Fortunately, once a sparse table entry captures a minimum, its value never changes, so l_j can be maintained in O(n) time by updating only the affected entries according to the recurrence.

Specifically, let {\rm st}(j,L) denote the minimum of P_{[L,L+2^j-1]} stored by sparse table, then the recurrence is {\rm st}(j,L)=\min\{{\rm st}(j-1,L),{\rm st}(j-1,L+2^{j-1})\}, which can be represented by a directed acyclic graph G_{\rm st}=(V_{\rm st},E_{\rm st}) where

V_{\rm st}=\Big\{{\rm st}(j,L) : j\geq 0,\ 1\leq L\leq \Big\lceil \frac{n}{w} \Big\rceil-2^j+1\Big\},\\ E_{\rm st}=\Big\{\big({\rm st}(j-1,L),{\rm st}(j,L)\big),\ \big({\rm st}(j-1,L+2^{j-1}),{\rm st}(j,L)\big) : j\geq 1,\ 1\leq L\leq \Big\lceil \frac{n}{w} \Big\rceil-2^j+1\Big\}.

Modifying the j-th element affects {\rm st}(0,j) and all nodes reachable from it. If we avoid traversing nodes whose value is \infty during the update, the total time complexity is O(|V_{\rm st}|+|E_{\rm st}|)=O(n).

The in-block data naturally supports append operations.

3. Online Conversion

To make the incremental construction work in an online setting, range maximum and minimum queries on P can be handled in the same way as the maintenance of l_j. The computation of m_j, however, presents a different challenge. Abstractly, we start with an array A of length n filled with \infty. We then perform n replacements: the i-th replacement sets some \infty to i. Between replacements, range minimum queries may be issued. The w-block sparse table is not suitable here because its in-block information does not support arbitrary point updates.

To overcome this limitation, we introduce a data structure that supports static range semigroup queries in O(n\alpha(n)) preprocessing time and O(\alpha(n)) query time, using a more complete DAG structure [6].

Definition 3.1. (Ackermann Function and Its Inverse)

A_k(j)=\begin{cases} j+1 & k=0,\\ A^{(j+1)}_{k-1}(j) & k\ge 1, \end{cases}

where the superscript denotes iteration. Equivalently,

A(i,k,j)=A^{(i)}_k(j)=\begin{cases} j & i=0,\\ j+1 & i=1 \land k=0,\\ A(j,k-1,A(1,k-1,j)) & i=1 \land k\ge 1,\\ A(i-1,k,A(1,k,j)) & i\ge 2, \end{cases}

and

\alpha(n)=\min \{k : A_k(1)\ge n\}.

Any closed interval [1,h] can be partitioned into at most \alpha(h)+1 intervals of the form [a, A(c,b,a)-1].

Theorem 3.1. For any h\ge 1, there exist

1=a_1<a_2<\cdots<a_k=h,\\ \alpha(h)\ge b_1>b_2>\cdots>b_k\ge 0,

and c_1,\dots,c_k\ge 1 with c_i\le a_i such that a_{i+1}=A(c_i,b_i,a_i).

Proof. Define

b_{i+1}=\max\{b:A(1,b,a_i)\le h\},\qquad c_{i+1}=\max\{c:A(c,b_i,a_i)\le h\}.

The sequence b_i must decrease to compensate for the growth of A(c_i,b_i,a_i) as a_i increases. Since A(1,b_i,a_i)\le h implies b_i\le\alpha(h), the bound follows. Replacing (c_i,a_i) by (c_i-a_i-1, A(1,b_i+1,a_i)) repeatedly ensures c_i\le a_i. \square

If we use a segment tree to query the minimum over a subsequence, the result is the union of information along a leaf-to-leaf path. Splitting this path at the LCA reduces the problem to considering leaf-to-ancestor paths.

Theorem 3.2. Let h_a denote the height of node a (with h_a=1 for leaves), let \operatorname{Anc}(a,h) denote the ancestor of a at height h, and let \operatorname{Path}(x,y) denote the path between x and y. Then the number of paths of the form \operatorname{Path}(a,\operatorname{Anc}(a,A(c,b,h_a))) is O(n\alpha(n)).

Proof. By Theorem 3.1, it suffices to consider paths with 0\le b\le \alpha(\log_2 n) and 1\le c\le h_a. Their total number is bounded by

\begin{aligned} \sum_{i=0}^{\log_2 n +1} (\alpha(\log_2 n)+1) 2^i(\log_2 n+2-i) &=(\alpha(\log_2 n)+1)\left((\log_2 n+2)(2^{\log_2 n+2}-1)-\sum_{i=0}^{\log_2 n+1}i2^i\right)\\ &=(\alpha(\log_2 n)+1)(8n-\log_2 n-4)\\ &=O(n\alpha(n)).\\ & & \square \end{aligned}

Thus we can precompute the information along these paths recursively according to the definition of the Ackermann function, using O(n\alpha(n)) time and space. This can be improved to O(n) by applying \alpha(n)-blocking while preserving O(\alpha(n)) query time per operation.

Moreover, the techniques used for the sparse table also apply to this segment-tree-based structure, as it consists solely of the recurrence relation for the minimum value. Let {\rm sgt}(a,b,c) denote the minimum on {\rm Path}(a,{\rm Anc}(a,A(c,b,h_a))), the recurrence is

{\rm sgt}(c,b,a)=\begin{cases} \min\bigg\{{\rm sgt}\Big(1,b-1,a\Big),{\rm sgt}\Big(h_a,b-1,{\rm Anc}\big(a,A(1,b-1,h_a)\big)\Big)\bigg\} & c=1 \land b\geq 1,\\ \min\bigg\{{\rm sgt}\Big(1,b,a\Big),{\rm sgt}\Big(c-1,b,{\rm Anc}\big(a,A(1,b,h_a)\big)\Big)\bigg\} & c\geq 2, \end{cases}

where {\rm sgt}(1,0,a)s are basic values. It's DAG structure is easy to see.

Nevertheless, since we need to perform n-1 queries on this data structure, the overall complexity of this online incremental method remains O(n\alpha(n)).

Acknowledgments

The author is deeply grateful to Prof. Sergei Kalmykov of Academic English Writing for his invaluable guidance on academic writing throughout this paper.

The author thanks UnyieldingTrilobite for insightful discussions on the range semigroup query problem.

The author thanks Querainy for constructive comments that significantly improved this paper.

References

[1] Ir1d, StudyingFather, Tiphereth-A, H-J-Granger, sshwy, countercurrent-time, et al., "The Strong Interval Tree," OI-wiki. May 13, 2026. [Online]. Available: https://oiwiki.org/ds/divide-combine/ [Accessed: Jul. 16, 2026]

[2] C. Capelle, M. Habib, and F. de Montgolfier, "Graph Decompositions and Factorizing Permutations," Discrete Mathematics and Theoretical Computer Science, vol. 5, pp. 55-70, 2002. doi: 10.46298/dmtcs.298.

[3] A. Pierrot, "Combinatoire et algorithmique dans les classes de permutations," Ph.D. dissertation, Université Paris Diderot - Paris 7, Paris, France, 2013.

[4] Chengao Liu, "Basic Interval Data Structure," WC2019 Participant Presentations, Guangzhou No.2 Middle School, Jan. 26, 2019.

[5] StudyingFather, Ir1d, zhouyuyang2002, Tiphereth-A, AxolotlXD666, c-forrest, et al., "RMQ," OI-wiki. Jun. 20, 2026. [Online]. Available: https://oiwiki.org/topic/rmq/ [Accessed: Jul. 31, 2026]

[6] UnyieldingTrilobite, "Segment Tree, Ackermann, Blocking," Luogu. Oct. 26, 2024. [Online]. Available: https://www.luogu.com/article/on6jtb2m [Accessed: Jan. 20, 2026]