Conventions

This article is based on ordinary set theory. Natural numbers, integers, finite sequences, maps, Cartesian products, total orders, trees, induction, and the finite recursion theorem are assumed to be established. Write $$$\mathbf N={0,1,\ldots}$$$ and $$$\mathbf N_{ \gt 0}=\mathbf N\setminus{0}$$$. All trees are finite trees; all intervals not otherwise qualified are integer intervals.

For $$$l,r\in\mathbf Z$$$, put

When $$$l \gt r$$$, $$$[l,r]=\varnothing$$$. For a nonempty finite set $$$E$$$, $$$|E|$$$ denotes its cardinality. The symbol $$$\sqcup$$$ denotes disjoint union. Composition of maps follows the convention $$$(f\circ g)(x)=f(g(x))$$$.

For $$$n\ge1$$$, put

All asymptotic estimates are taken as $$$n\to\infty$$$; bounds written in terms of $$$\lambda(n)$$$ also apply to $$$n=1$$$.

Computational conventions. Unless otherwise stated, we use the random-access machine model with word length $$$w=\Omega(\log(n+1))$$$. An address, an index, and an encoding of a micro table in this article each occupy $$$O(1)$$$ words; addition, subtraction, comparison, bit operations, shifts, and random access on words cost $$$O(1)$$$. The storage cost of every algebraic operation declared to be a basic operation and of its operands is also $$$O(1)$$$. If arbitrary-precision integers are used and the latter convention is not satisfied, then the time bounds in this article count only algebraic operations and the space bounds count only algebraic elements; bit complexity must be calculated separately.

In particular, in the time bounds for group-valued summation, group operations, inversion, and multiplication of a group element by a known integer length, $$$(p,c)\mapsto pc$$$, are counted as basic operations; if the representation of a concrete group does not support constant-time integer multiples, the actual cost of that operation should be included in the corresponding formula. Merging of general digests, tag composition, and tag actions must also satisfy the constant-time conditions explicitly stated in each theorem. Machine implementations must ensure that the integer operations used do not overflow, or must explicitly compute in a specified residue-class ring.

The costs of initialization, query, and modification are measured separately. To claim that a representation supports a certain operation means that there exists an implementation as defined below together with a corresponding correctness proof; it does not include any claim of optimality.

Chapter 1. Aggregation and Actions

§1. Associativity

Definition 1.1. A semigroup is a nonempty set $$$S$$$ equipped with an associative binary operation $$$\cdot:S\times S\to S$$$. A monoid is a semigroup equipped with an identity element $$$e$$$. A group is a monoid in which every element is invertible. A commutative group is also called an abelian group and is usually written additively.

Let $$$M$$$ be a monoid. For a finite ordered family $$$a=(a_1,\ldots,a_n)\in M^n$$$, define

The parentheses on the right-hand side are omitted by associativity, and the order of the factors must not be changed.

Proposition 1.2. If $$$l\le k \lt r$$$, then

More generally, if $$$[l,r]=I_1\sqcup\cdots\sqcup I_s$$$ and each $$$I_j$$$ is a nonempty interval arranged from left to right, then

Proof. Apply associativity to the number of factors, then induct on $$$s$$$. $$$\square$$$

Definition 1.3. A left-quotient recovery map on a monoid $$$M$$$ is a map $$$\delta:D\to M$$$ defined on

such that $$$\delta(x,x\cdot y)=y$$$. Such a map exists if and only if $$$M$$$ satisfies the left cancellation law; when it exists, it is unique. Its existence itself does not imply that it can be evaluated in constant time.

Proof. If $$$x\cdot y=x\cdot z$$$, then applying $$$\delta$$$ gives $$$y=z$$$. Conversely, the left cancellation law guarantees that the relation $$$(x,x\cdot y)\mapsto y$$$ is single-valued. $$$\square$$$

In a group, the recovery map is $$$\delta(x,z)=x^{-1}\cdot z$$$. Commutativity is not a condition for this formula.

Definition 1.4. A semigroup $$$S$$$ is called idempotent if $$$x\cdot x=x$$$.

Proposition 1.5. Let $$$S$$$ be an idempotent semigroup and let $$$a$$$ be a finite ordered family in $$$S$$$. If nonempty intervals $$$I,J$$$ satisfy

then

Proof. If necessary, adjoin an identity element to $$$S$$$; the resulting monoid is still idempotent. Let $$$x,y,z$$$ be the products, in the original order, over $$$I\setminus J$$$, $$$I\cap J$$$, and $$$J\setminus I$$$, respectively, with the product over an empty family taken to be the adjoined identity. By associativity and $$$y^2=y$$$,

The right-hand side is the desired product. $$$\square$$$

Remark. Proposition 1.5 does not require commutativity. Nor does it allow arbitrary changes in the order of merging intervals.

§2. Digests and Tags

Definition 1.6. Let $$$M$$$ be a monoid and let $$$\operatorname{End}(M)$$$ be the monoid of self-maps preserving the operation and the identity, with composition as its operation. A tag action is a monoid $$$T$$$ together with a homomorphism

Write $$$\Phi_t=\Phi(t)$$$, and let $$$1_T$$$ be the identity of $$$T$$$. Then

The operation on tags is written $$$\circ$$$, so that the tag obtained by first applying $$$s$$$ and then applying $$$t$$$ is $$$t\circ s$$$.

Definition 1.7. Let $$$A$$$ be a set of elements and let $$$\eta:A\to M$$$ be a digest map. For a sequence $$$a\in A^n$$$, the digest of the interval $$$I$$$ is

If $$$T$$$ also acts on $$$A$$$, denote this action by $$$\alpha$$$, and if

then $$$\eta$$$ is said to be compatible with the two actions.

Proposition 1.8. Under the conditions of Definition 1.7, after replacing every element $$$a_i$$$ in the interval $$$I$$$ by $$$\alpha_t(a_i)$$$, the digest of that interval is $$$\Phi_t(\sigma_a(I))$$$.

Proof. Substitute (1.7) term by term, then induct on $$$|I|$$$ using (1.6). $$$\square$$$

Example 1.9. Let $$$G$$$ be an abelian group. Put

Take $$$\eta(x)=(x,1)$$$. For $$$c\in G$$$, define

Here $$$pc$$$ is the sum of $$$p$$$ copies of $$$c$$$. Since

formula (1.8) gives a tag action of the additive monoid $$$G$$$ on $$$M$$$. Its digest contains both the sum and the length.

Example 1.10. Let $$$R$$$ be a commutative ring with identity, and take $$$M=R\times\mathbf N$$$ with the same operation as above. For $$$(\alpha,\beta)\in R^2$$$, put

Composition of tags is

The identity is $$$(1,0)$$$. On elements, $$$(1,c)$$$ means adding $$$c$$$, while $$$(0,c)$$$ means assigning the value $$$c$$$. For example, in $$$R=\mathbf Z$$$, first assigning $$$0$$$ and then adding $$$1$$$, versus first adding $$$1$$$ and then assigning $$$0$$$, give the tags $$$(0,1)$$$ and $$$(0,0)$$$, respectively. Thus commutativity is not a property of general tag actions.

§3. Correctness of Representations

Definition 1.11. For a fixed $$$n$$$, the abstract state space is $$$\mathcal A=A^n$$$. A representation consists of a concrete state set $$$\mathcal C$$$, a subset of legal states $$$\mathcal V\subseteq\mathcal C$$$, and an interpretation map $$$\rho:\mathcal V\to\mathcal A$$$.

Let $$$U:\mathcal A\to\mathcal A$$$ be a modification and $$$Q:\mathcal A\to Y$$$ a query. Their implementations are maps

and must satisfy

The equations and conditions describing $$$\mathcal V$$$ are called representation invariants. A query may change the concrete representation, but must not change its interpretation.

In this article, interval queries are $$$a\mapsto\sigma_a([l,r])$$$; point assignment is $$$a_p\leftarrow x$$$; interval addition on an abelian group is $$$a_i\leftarrow a_i+c$$$, $$$i\in[l,r]$$$. Interval sums are denoted $$$\Sigma_a(I)$$$.

Chapter 2. Prefixes and Finite Partitions

§1. Prefix Representation

Definition 2.1. For $$$a\in M^n$$$, its prefix family is

Proposition 2.2. If $$$M$$$ has a left-quotient recovery map $$$\delta$$$, then

In particular, for groups,

for abelian groups, $$$\Sigma_a([l,r])=P_r-P_{l-1}$$$.

Proof. By Proposition 1.2, $$$P_r=P_{l-1}\cdot\Pi_a([l,r])$$$; apply Definition 1.3. $$$\square$$$

Corollary 2.3. If the cost of multiplication and of evaluating $$$\delta$$$ is $$$O(1)$$$, then constructing the prefix family takes $$$O(n)$$$ time and $$$O(n)$$$ space, and each nonempty interval query takes $$$O(1)$$$ time.

Direct term-by-term aggregation has worst-case query cost $$$O(n)$$$; the worst-case cost of $$$q$$$ such queries is $$$O(qn)$$$. The prefix representation changes this total bound to $$$O(n+q)$$$.

Proposition 2.4. For an explicitly stored abelian-group prefix sum, the update formula for adding $$$c$$$ at position $$$p$$$ is

Therefore this explicit representation can be updated in $$$O(n-p+1)$$$ time. For $$$G=\mathbf Z$$$ and $$$c\ne0$$$, if every $$$P_i$$$ must be stored separately with its current value, then $$$n-p+1$$$ distinct cells must be rewritten.

Proof. Compute separately whether each prefix contains $$$p$$$; in the stated integer case, every prefix sum containing $$$p$$$ changes. $$$\square$$$

§2. Intra-Block Prefixes

Fix an integer $$$B$$$, $$$1\le B\le n$$$, put $$$m=\lceil n/B\rceil$$$, and define the ordered partition

Lemma 2.5. Any interval $$$I\subseteq[n]$$$ intersects nonempty and not equal to a whole block in at most two blocks; all other nonempty intersections are whole blocks.

Proof. If a block does not contain either endpoint of $$$I$$$ and intersects $$$I$$$, then both endpoints of the block lie in $$$I$$$, so the block is contained in $$$I$$$. $$$\square$$$

Construction 2.6. Let $$$G$$$ be an abelian group. In each $$$K_j$$$, store all prefix sums relative to the left endpoint of that block, and store the original elements. The sum of a whole block is the last prefix sum of that block. For a query interval, split it according to Lemma 2.5; whole blocks are summed directly, and the remaining at most two fragments are obtained by subtracting intra-block prefixes.

Proposition 2.7. Construction 2.6 has initialization time and space both $$$O(n)$$$; interval query time $$$O(\lceil n/B\rceil)$$$; point assignment or point increment time $$$O(B)$$$.

Proof. A query reads at most $$$m$$$ whole-block sums and four intra-block prefixes. A modification affects only the prefixes in its block starting from the modified position, whose number is at most $$$B$$$. For assignment, first compute the increment from the old element. $$$\square$$$

Corollary 2.8. If both operations above are required to have the same worst-case upper bound, taking $$$B=\lceil\sqrt n\rceil$$$ gives $$$O(\sqrt n)$$$.

If the number of queries $$$q$$$ and the number of modifications $$$u$$$ are known, then the total bound of this representation is

Thus the choice $$$B\asymp\sqrt n$$$ presupposes that the two operations are constrained by the same weight; it is not a uniform optimal choice under all operation distributions.

§3. Translation Representation

Construction 2.9. Let $$$G$$$ be an abelian group. Take the concrete state to be $$$(b,T)\in G^n\times G$$$, interpreted as

Then

Adding $$$c$$$ to all elements is implemented by $$$T\leftarrow T+c$$$; assigning position $$$p$$$ the value $$$x$$$ is implemented by $$$b_p\leftarrow x-T$$$.

Proof. Substitute (2.7) into the interval sum and rearrange using commutativity. The two modification formulas directly satisfy Definition 1.11. $$$\square$$$

§4. Representation with Block Tags

Construction 2.10. For each block in (2.5), store $$$T_j\in G$$$; for each position store $$$b_i\in G$$$; and also store

The interpretation is

An interval query sums over each nonempty intersection $$$J=I\cap K_j$$$ according to the following rules:

When adding $$$c$$$ to an interval $$$I$$$, for each such $$$J$$$ perform

For point assignment $$$a_p\leftarrow x$$$, $$$p\in K_j$$$, implement by

Proposition 2.11. Equation (2.9) is a representation invariant for the above operations; (2.11) returns the correct interval sum; (2.12) and (2.13) implement the declared abstract modifications.

Proof. For a whole block, (2.12) changes no $$$b_i$$$, hence preserves (2.9), and by (2.10) increases every value in the block by $$$c$$$. For a non-whole block, the increment of $$$S_j$$$ equals the sum of the increments of the modified $$$b_i$$$. The same reasoning applies to (2.13). Formula (2.11) is the term-by-term sum of (2.10). $$$\square$$$

Proposition 2.12. This representation has initialization time and space both $$$O(n)$$$; interval query and interval addition time are both

and point assignment time is $$$O(1)$$$. Taking $$$B=\lceil\sqrt n\rceil$$$, (2.14) becomes $$$O(\sqrt n)$$$.

Proof. Lemma 2.5 limits non-whole-block access to at most $$$2B$$$ positions; there are at most $$$m$$$ whole blocks. The rest follows by direct counting from the construction. $$$\square$$$

Chapter 3. Layered Family of Binary Intervals

§1. Interval Tree

Fix $$$n\ge1$$$, put

Then $$$n\le N \lt 2n$$$, including the case $$$n=1$$$.

Definition 3.1. For $$$0\le d\le k$$$, $$$0\le j \lt 2^d$$$, put

The family $$$\mathscr D={D_{d,j}}$$$ is called the binary interval family of $$$[N]$$$. Take $$$D_{0,0}$$$ as the root; the two sons of $$$D_{d,j}$$$ in order are $$$D_{d+1,2j}$$$, $$$D_{d+1,2j+1}$$$. The resulting rooted ordered binary tree is denoted $$$\mathcal T_N$$$.

Number the node $$$D_{d,j}$$$ as $$$u=2^d+j$$$. Then the root has number $$$1$$$, the two sons of a non-leaf node $$$u$$$ have numbers $$$2u,2u+1$$$, and position $$$i$$$ corresponds to leaf number $$$N+i-1$$$. Let $$$I_u$$$ denote the interval of node $$$u$$$, and let $$$u\preceq v$$$ mean that $$$u$$$ is an ancestor of $$$v$$$, allowing $$$u=v$$$.

Proposition 3.2. For $$$I,J\in\mathscr D$$$, if $$$I\cap J\ne\varnothing$$$, then $$$I\subseteq J$$$ or $$$J\subseteq I$$$. Moreover, $$$I_v\subseteq I_u$$$ if and only if $$$u\preceq v$$$.

Proof. Each level is a partition of $$$[N]$$$, and the next level is obtained by bisecting each block of the previous level. Suppose the level of $$$I$$$ is not less than that of $$$J$$$. Then $$$I$$$ is contained in the unique interval of $$$J$$$'s level. If it intersects $$$J$$$, that interval can only be $$$J$$$. The ancestor relation follows from the definition by successive refinement. $$$\square$$$

§2. Canonical Decomposition

Definition 3.3. For a nonempty interval $$$Q\subseteq[N]$$$, put

Call it the canonical decomposition of $$$Q$$$.

Theorem 3.4. $$$\mathscr C(Q)$$$ is a disjoint partition of $$$Q$$$. Among all ways of partitioning $$$Q$$$ by elements of $$$\mathscr D$$$, it has the smallest cardinality, and such a minimum partition is unique.

Proof. For $$$i\in Q$$$, starting from the singleton $$${i}$$$ and moving up the ancestor chain, there is a unique largest node still contained in $$$Q$$$; hence canonical intervals cover $$$Q$$$. By Proposition 3.2, two intersecting canonical intervals must be nested; by maximality, they are equal. Hence they are disjoint.

Let $$$\mathscr P\subseteq\mathscr D$$$ be another disjoint partition of $$$Q$$$. Every $$$J\in\mathscr P$$$ is contained in a unique canonical interval: existence comes from moving up the ancestor chain, and uniqueness from the pairwise disjointness of canonical intervals. Hence $$$\mathscr P$$$ further partitions each canonical interval, and each canonical interval requires at least one member of $$$\mathscr P$$$. Therefore $$$|\mathscr P|\ge|\mathscr C(Q)|$$$. If equality holds, each canonical interval is covered by exactly one member of $$$\mathscr P$$$, which must equal that canonical interval. Thus $$$\mathscr P=\mathscr C(Q)$$$. $$$\square$$$

Lemma 3.5. On any fixed level, there are at most two intervals satisfying $$$I\cap Q\ne\varnothing$$$ but $$$I\nsubseteq Q$$$.

Proof. Intervals on the same level are pairwise disjoint. An interval that intersects $$$Q$$$ but is not contained in $$$Q$$$ must contain the left or right endpoint of $$$Q$$$; each endpoint belongs to only one interval on that level. $$$\square$$$

Proposition 3.6. On every non-root level, $$$\mathscr C(Q)$$$ has at most two members. Therefore

Proof. The parent interval of a non-root canonical interval intersects $$$Q$$$ but is not contained in $$$Q$$$. By Lemma 3.5, there are at most two such parent intervals on the same level. Each parent interval has at most one son contained in $$$Q$$$; otherwise the parent itself would be contained in $$$Q$$$. Thus each non-root level produces at most two canonical intervals. The root level produces at most one. $$$\square$$$

§3. Recursive Retrieval of the Canonical Decomposition

Construction 3.7. When node $$$u$$$ is called, require $$$I_u\cap Q\ne\varnothing$$$. If $$$I_u\subseteq Q$$$, output $$$u$$$ and terminate this call; otherwise, in left-to-right order, recursively call on the sons that intersect $$$Q$$$. The initial call is at the root.

Proposition 3.8. Construction 3.7 outputs exactly $$$\mathscr C(Q)$$$, and the number of visited nodes is at most $$$1+4k$$$.

Proof. The output condition is that the node itself is contained in $$$Q$$$ and no ancestor contained in $$$Q$$$ was encountered before, which is equivalent to Definition 3.3.

Only nodes that intersect $$$Q$$$ but are not contained in $$$Q$$$ produce further calls. There are at most two such nodes on each level, each with at most two sons; hence except for the root, at most four nodes per level are visited; there are $$$k$$$ non-root levels. $$$\square$$$

Remark. Formula (3.4) counts only output nodes; the time bound of the construction is given by Proposition 3.8 and cannot be inferred merely from the number of outputs.

§4. Monoid Representation

Let $$$a\in M^n$$$. Extend it to $$$\widetilde a\in M^N$$$, where $$$\widetilde a_i=e$$$ for $$$n \lt i\le N$$$.

Construction 3.9. Store at each node a value $$$v_u\in M$$$ satisfying

Equivalently, the leaf value is the corresponding element, and every non-leaf node satisfies

Applying (3.6) in increasing order of node height is called building. A point assignment first changes the corresponding leaf, then recomputes along the ancestor chain according to (3.6).

For a query $$$Q\subseteq[n]$$$, use Construction 3.7 to obtain, in left-to-right order, nodes $$$u_1,\ldots,u_s$$$, and return

Theorem 3.10. Construction 3.9 satisfies representation correctness; build time and space are $$$O(n)$$$, and point assignment and interval query time are $$$O(\lambda(n))$$$.

Proof. The equivalence of (3.5) and (3.6) follows from Proposition 1.2 and induction on tree height. A point modification changes only the intervals containing that point, and these are exactly the ancestors of the leaf. Query correctness follows from Theorem 3.4 and Proposition 1.2.

The tree has $$$2N-1 \lt 4n$$$ nodes; an ancestor chain has $$$k+1=O(\lambda(n))$$$ nodes; query cost is controlled by Proposition 3.8. $$$\square$$$

This representation is called a segment tree. Its definition does not require $$$M$$$ to be commutative, so the order in a query is part of the structure.

Chapter 4. Tag-Preserving Representation for Additive Tags

§1. State Space

Fix an abelian group $$$G$$$ and an initial family $$$a^{(0)}\in G^n$$$. Extend to length $$$N$$$ as in Chapter 3, and still denote it by $$$a^{(0)}$$$. Write

Definition 4.1. The concrete state consists of pairs $$$(s_u,t_u)\in G^2$$$ at each node, with legality condition

The interpretation map is defined by

Modifications are allowed only on intervals within $$$[n]$$$, so extended positions remain zero.

Proposition 4.2. For any legal state, let

where $$$v\prec u$$$ means a strict ancestor. Then

Proof. Sum (4.2) over $$$I_u$$$. By Proposition 3.2, a tag interval intersecting $$$I_u$$$ is either an ancestor interval of it or is contained in $$$I_u$$$. Strict ancestor tags occur $$$|I_u|$$$ times; a tag $$$t_v$$$ in the subtree of $$$u$$$ occurs $$$|I_v|$$$ times. Rearrange using commutativity and apply (4.1). $$$\square$$$

Corollary 4.3. Equation (4.1) is equivalent to the following local equations:

Initialization takes $$$t_u=0$$$, $$$s_u=A_u$$$.

§2. Modifications

Construction 4.4. Define the recursive state transformation $$$\mathcal U(u,J,c)$$$, with precondition $$$\varnothing\ne J\subseteq I_u$$$ and $$$J$$$ an interval:

1. Set $$$s_u\leftarrow s_u+|J|c$$$.
2. If $$$J=I_u$$$, set $$$t_u\leftarrow t_u+c$$$ and terminate.
3. Otherwise, in the order of the sons, for each son $$$v$$$ satisfying $$$J\cap I_v\ne\varnothing$$$, perform $$$\mathcal U(v,J\cap I_v,c)$$$.

Adding $$$c$$$ to interval $$$Q$$$ is defined by $$$\mathcal U(1,Q,c)$$$.

Proposition 4.5. Construction 4.4 preserves (4.1), and under the interpretation map it increases exactly each element in $$$Q$$$ by $$$c$$$.

Proof. The tags that are increased are exactly those located at $$$\mathscr C(Q)$$$. By Theorem 3.4, every $$$i\in Q$$$ belongs to exactly one such interval, and no point outside $$$Q$$$ belongs to any such interval; hence the change in (4.2) is exactly the declared modification.

If $$$u$$$ is visited, the canonical tagged intervals lying in its subtree are disjoint and their union is $$$Q\cap I_u$$$, so the right-hand side of (4.1) increases by $$$|Q\cap I_u|c$$$, the same as step 1. If $$$u$$$ is not visited, no tag in its subtree is changed; some strict ancestor may be tagged, but that tag does not occur in (4.1). Hence all nodes preserve legality. $$$\square$$$

§3. Queries

Construction 4.6. For $$$\varnothing\ne J\subseteq I_u$$$ and $$$h\in G$$$, define recursively

An interval query returns $$$\mathcal Q(1,Q,0)$$$.

Proposition 4.7. If the passed $$$h$$$ equals the sum of the strict ancestor tags of $$$u$$$, then (4.5) returns $$$\Sigma_a(J)$$$.

Proof. Induct on node height. The fully contained case follows from Proposition 4.2; in the other case, the sum of strict ancestor tags of a son is $$$h+t_u$$$. Use the induction hypothesis and sum over disjoint intersections. $$$\square$$$

Theorem 4.8. Constructions 4.4 and 4.6 give a representation with initialization time and space $$$O(n)$$$, and both interval addition and interval sum time $$$O(\lambda(n))$$$.

Proof. Both constructions visit exactly the nodes visited by Construction 3.7, and each node requires only a constant number of basic operations. Correctness follows from Propositions 4.5 and 4.7. $$$\square$$$

Remark. The property called “tag preservation” or “tag permanence” here is that a query need not push ancestor tags into descendants. It does not constitute preservation of historical states, nor does it claim generalizability to arbitrary tag actions.

Chapter 5. Push-Down Representation for General Tag Actions

§1. Recursive Interpretation

Use the data $$$(A,M,T,\eta,\alpha,\Phi)$$$ from Definitions 1.6 and 1.7. To handle the $$$N-n$$$ extended positions, adjoin an element $$$\bot$$$, with

Henceforth $$$\eta,\alpha$$$ denote the corresponding extensions. Let $$$\alpha_t^*$$$ denote the map that applies $$$\alpha_t$$$ term by term to a sequence, and let $$$\Vert$$$ denote sequence concatenation.

Definition 5.1. A concrete state consists of an element $$$b_u\in A\sqcup{\bot}$$$ at each leaf $$$u$$$, a tag $$$t_u\in T$$$ at each non-leaf $$$u$$$, and digests $$$v_u\in M$$$ at all nodes. Recursively define the sequence represented by a node:

A legal state satisfies

The elements of the first $$$n$$$ leaves belong to $$$A$$$, and the remaining leaves have element $$$\bot$$$. The interpretation map takes the first $$$n$$$ terms of $$$F_1$$$.

Proposition 5.2. In a legal state, $$$v_u=\sigma(F_u)$$$, where $$$\sigma$$$ denotes the digest of the whole node sequence.

Proof. Induct on node height, using Proposition 1.8 and (5.3). $$$\square$$$

§2. Three Local Transformations

Definition 5.3. The apply transformation $$$\operatorname{Apply}(u,t)$$$ at a node is defined by

The push transformation $$$\operatorname{Push}(u)$$$ at a non-leaf node is defined as follows: first set $$$t=t_u$$$, then perform in order

The value $$$v_u$$$ of the node remains unchanged during (5.5).

When $$$t_u=1_T$$$, the pull transformation $$$\operatorname{Pull}(u)$$$ is defined by

Proposition 5.4. $$$\operatorname{Apply}(u,t)$$$ preserves legality inside the subtree of $$$u$$$, and replaces $$$F_u$$$ by $$$\alpha_t^*(F_u)$$$. $$$\operatorname{Push}(u)$$$ preserves the legality and interpretation of the whole representation.

Proof. The leaf case follows from (1.7). For a non-leaf apply transformation,

which is compatible with the new tag; the sequence interpretation is transformed by the same action law.

For push, after the transformation the sequence of the parent node is

which is exactly $$$F_u$$$ before the transformation. Also, by (1.6), the product of the digests of the two sons after the transformation equals the original $$$v_u$$$, so (5.3) still holds after $$$t_u=1_T$$$. The parent interpretation and digest are unchanged, so the invariants at all its ancestors are also unchanged. $$$\square$$$

Remark. Applying $$$\operatorname{Apply}$$$ to a node that has a strict ancestor does not necessarily preserve the digest equation at the ancestor; the following recursive construction is responsible for recomputing its ancestors.

§3. Interval Transformations

Construction 5.5. For a nonempty interval $$$J\subseteq I_u$$$, define the modification $$$\mathcal U_T(u,J,t)$$$:

1. If $$$J=I_u$$$, perform $$$\operatorname{Apply}(u,t)$$$ and terminate.
2. Otherwise perform $$$\operatorname{Push}(u)$$$; for each son $$$v$$$ intersecting $$$J$$$, perform $$$\mathcal U_T(v,J\cap I_v,t)$$$; finally perform $$$\operatorname{Pull}(u)$$$.

The abstract operation $$$a_i\leftarrow\alpha_t(a_i)$$$ on interval $$$Q$$$ is implemented by $$$\mathcal U_T(1,Q,t)$$$.

Construction 5.6. The interval query $$$\mathcal Q_T(u,J)$$$ is specified recursively as follows: if $$$J=I_u$$$, return $$$v_u$$$; otherwise first perform $$$\operatorname{Push}(u)$$$, then obtain, in left-to-right order, the query values of the sons intersecting $$$J$$$, and take their product in that order.

Theorem 5.7. Constructions 5.5 and 5.6 satisfy Definition 1.11. If digest merging, tag composition, tag action, and leaf-element action are all constant-time operations, then initialization time and space are $$$O(n)$$$, and each interval modification or query takes $$$O(\lambda(n))$$$ time.

Proof. Induct on node height. A fully contained modification is correct by Proposition 5.4. When it is not fully contained, pushing does not change $$$F_u$$$, and makes $$$t_u=1_T$$$; hence modifications to the subsequences can be carried out independently on the two sons. By the induction hypothesis, the interpretations and digests of the sons are correct; pulling restores (5.3). A fully contained query is correct by Proposition 5.2; the remaining cases follow from the fact that pushing preserves interpretation and from Proposition 1.2. Pushing during a query may change the concrete state, but satisfies (1.12).

Each recursive expansion performs at most two constant-time apply operations on sons. The number of recursive nodes is controlled by Proposition 3.8, so the total time is still $$$O(\lambda(n))$$$. Initialization takes $$$t_u=1_T$$$ at all nodes and merges from leaves to root. $$$\square$$$

Corollary 5.8. Example 1.9 gives a representation for interval addition and interval sum; Example 1.10 gives a representation for interval affine transformations and interval sum. Both satisfy the complexity bounds of Theorem 5.7, but the latter must use the composition order specified in (1.10).

Remark. A node digest already includes the action of the node's own tag. Pushing down is needed only before accessing the local representations of its sons; directly returning the digest of a fully contained node requires no push-down.

§4. Fibonacci Digests

Definition 5.9. The integer family $$$(f_m)_{m\in\mathbf N}$$$ is uniquely determined by

Put

Proposition 5.10. For $$$m,c\in\mathbf N$$$,

Proof. Equation (5.7) is equivalent to $$$z_{m+1}=Qz_m$$$. Induct from $$$z_0=(1,0)^{\mathsf T}$$$. $$$\square$$$

Proposition 5.11. In $$$\mathbf R$$$, put $$$\varphi=(1+\sqrt5)/2$$$, $$$\psi=(1-\sqrt5)/2$$$. Then

Proof. Both $$$\varphi,\psi$$$ satisfy $$$x^2=x+1$$$, so the right-hand side satisfies the recurrence (5.7) and the two initial values. Uniqueness follows from the finite recursion theorem. $$$\square$$$

Let the element family be $$$a\in\mathbf N^n$$$; the query is $$$\sum_{i=l}^r f_{a_i}$$$, and the modification is $$$a_i\leftarrow a_i+c$$$ on an interval, with $$$c\in\mathbf N$$$.

Construction 5.12. Take the digest monoid $$$(\mathbf Z^2,+,0)$$$, $$$\eta(m)=z_m$$$, and tag action

For summation over a finite family, the second component of the resulting digest is the desired query value. Since matrix multiplication distributes over vector addition, (5.11) satisfies Definition 1.6. One may also map all integers into any fixed commutative ring with identity, such as $$$\mathbf Z/m\mathbf Z$$$, and evaluate in that ring.

To implement this construction using only matrices and vectors, one may take the element state set to be $$$A'={z_m:m\in\mathbf N}$$$, the tag monoid to be $$$T'={Q^c:c\in\mathbf N}$$$, the digest map to be the inclusion map, and the element action to be matrix-vector multiplication. The map

turns exponent shifts into term-by-term matrix actions and preserves all specified query values, as follows from (5.9). Therefore one can use the representation of Definition 1.11 on vector states without recovering the original exponents from the vectors. In a residue-class ring, even if $$$\Psi$$$ is not injective, this does not affect compatibility with these operations and queries.

Proposition 5.13. Construction 5.12 can be implemented by the push-down representation of Chapter 5. If the matrix $$$Q^c$$$ for one modification is given, that modification and query use $$$O(\lambda(n))$$$ constant-dimensional matrix and vector operations.

If $$$c$$$ is given as a binary integer without an accompanying matrix, binary exponentiation additionally requires $$$O(\lambda(c+1))$$$ matrix operations. Hence the total bound for that modification is

Without preprocessing powers, generating the initial vectors one by one by binary exponentiation requires

algebraic operations for initialization; the generated segment tree occupies $$$O(n)$$$ vector or matrix cells.

If the initial exponents and all modification increments belong to $$$[0,U]$$$, precompute $$$Q^0,\ldots,Q^U$$$ sequentially; then total initialization time is $$$O(n+U)$$$, extra power-table space is $$$O(U)$$$, and every subsequent operation is $$$O(\lambda(n))$$$. In an implementation one may store matrix tags directly, whose composition is matrix multiplication, and thus need not explicitly store accumulated exponents.

Proof. Binary exponentiation squares and multiplies the required powers bit by bit according to the binary digits of the exponent, so the number of operations is proportional to the number of bits. The rest follows from Theorem 5.7 and the constant dimension. $$$\square$$$

§5. A Failed Generalization

Proposition 5.14. For all $$$c,d\in\mathbf N$$$,

Therefore Fibonacci shift tags commute pairwise.

Proof. This follows from the power laws of elements of the same monoid and the commutativity of integer addition. $$$\square$$$

However, the rule in Chapter 4 that “directly add the local digest increment of a child to the ancestor digest” cannot be derived from (5.13).

Counterexample 5.15. Take the exponent family $$$(0,0)$$$ of length $$$2$$$. The local vector at both leaves is $$$z_0=(1,0)^{\mathsf T}$$$, and the root digest is $$$(2,0)^{\mathsf T}$$$. Add $$$1$$$ to the whole interval, change the root digest to $$$(2,2)^{\mathsf T}$$$, and keep $$$Q$$$ at the root without changing the local vectors of the leaves. Then add $$$1$$$ only to the first position.

The local increment computed from the leaf digest that has not absorbed the root tag is

If this increment is added directly to the root, one obtains $$$(2,3)^{\mathsf T}$$$; the actual exponent family is $$$(2,1)$$$, whose digest is

The required increment at the root is $$$Q\Delta=(1,0)^{\mathsf T}$$$. Thus the failure comes from the local digest and the ancestor digest being in different action states, not from noncommutativity of matrix powers. This counterexample only refutes the above uncompensated update formula; it does not refute other possible tag-preserving representations.

Chapter 6. Binary Valuation and the Fenwick Representation

§1. Numbering of Retained Intervals

Definition 6.1. For $$$i\in\mathbf N_{ \gt 0}$$$, let $$$\nu_2(i)$$$ be the largest nonnegative integer such that $$$2^{\nu_2(i)}$$$ divides $$$i$$$, and put

On a two's-complement word large enough to contain $$$i$$$, $$$\ell(i)=i\mathbin{&}(-i)$$$. This is an identity of bit representations, not a premise of the definition.

Proposition 6.2. In $$$\mathcal T_N$$$, retain the root and all left sons. Mapping each retained node to the right endpoint of its interval gives a bijection between the set of retained nodes and $$$[N]$$$; the interval corresponding to endpoint $$$i$$$ is $$$R_i$$$.

Proof. A binary interval of length $$$2^t$$$ has the form

A non-root node is a left son if and only if $$$q$$$ is even. Then its right endpoint is $$$(2h+1)2^t$$$, so the 2-adic valuation of the right endpoint is exactly $$$t$$$, and the interval is exactly $$$R_i$$$. Conversely, for any $$$i \lt N$$$, write $$$i=(2h+1)2^t$$$; the resulting $$$R_i$$$ is exactly a left-son interval. $$$i=N$$$ corresponds to the root. The right endpoint uniquely determines $$$t$$$ and the interval, so the map is bijective. $$$\square$$$

Proposition 6.3. If $$$i \lt N$$$, then the number of the nearest strict ancestor of $$$i$$$ in the retained-node tree is

Here the retained-node tree connects adjacent retained ancestors and omits the unretained intermediate nodes.

Proof. Let $$$h=\ell(i)$$$. The node $$$R_i$$$ is a left son, and its parent interval in the original tree is $$$[i-h+1,i+h]$$$. If this parent node is a left son or the root, it is retained. Otherwise it is a right son, and moving up to the parent does not change the right endpoint; continue moving up until first reaching a left son or the root. The right endpoint remains $$$i+h$$$ throughout. This node is exactly the nearest retained ancestor. $$$\square$$$

Corollary 6.4. For $$$1\le x \lt y\le N$$$,

if $$$p(x)\le N$$$, then $$$R_x\subsetneq R_{p(x)}$$$; if $$$x \lt y \lt p(x)$$$, then $$$R_x\cap R_y=\varnothing$$$.

Proof. The first formula follows from Proposition 3.2 and the order of right endpoints; the rest follows from the definition of nearest retained ancestor. $$$\square$$$

For arbitrary $$$n$$$, use only $$$R_1,\ldots,R_n$$$; when $$$p(i) \gt n$$$, the node $$$i$$$ has no parent in this truncated structure. Therefore the truncated structure is generally a forest, not necessarily a tree.

§2. Group-Valued Representation

Let $$$G$$$ be an abelian group.

Definition 6.5. The Fenwick representation of a sequence $$$a\in G^n$$$ is a family $$$c\in G^n$$$ satisfying

Lemma 6.6. All $$$R_i$$$ containing position $$$p$$$ are exactly the intervals corresponding to the following sequence:

until the next term exceeds $$$n$$$.

Proof. The listed nodes are the retained ancestor chain of $$$p$$$, so all contain $$$p$$$. Conversely, if $$$p\in R_i$$$, then $$$i\ge p$$$, and $$$R_i$$$ intersects $$$R_p$$$. By (6.3), $$$R_p\subseteq R_i$$$, so $$$i$$$ lies on this ancestor chain. $$$\square$$$

Construction 6.7. When adding $$$d$$$ at position $$$p$$$, for each valid index in (6.5), perform $$$c_{i_j}\leftarrow c_{i_j}+d$$$.

Proposition 6.8. Construction 6.7 preserves (6.4) and uses $$$O(\lambda(n))$$$ operations.

Proof. The modified table entries are exactly the interval sums containing $$$p$$$, so correctness follows from Lemma 6.6. Write $$$i=(2h+1)2^t$$$; then

so the 2-adic valuation strictly increases at each step. The valuation of a valid index is at most $$$\lfloor\log_2 n\rfloor$$$, so the number of steps is $$$O(\lambda(n))$$$. $$$\square$$$

§3. Prefix Decomposition

Proposition 6.9. For $$$r\in[0,n]$$$, define

Let $$$r_s=0$$$ be the first term reaching zero. Then

Moreover, $$$s$$$ equals the number of $$$1$$$s in the binary representation of $$$r$$$.

Proof. By definition, $$$R_{r_j}=[r_{j+1}+1,r_j]$$$. These intervals are adjacent and disjoint, and cover the entire prefix. Subtracting the lowest nonzero binary digit clears exactly one $$$1$$$, so the number of loop iterations is as stated. $$$\square$$$

Theorem 6.10. The Fenwick representation supports prefix sum, interval sum, and point increment in $$$O(\lambda(n))$$$ time, and uses $$$O(n)$$$ space. Interval sums are obtained by subtracting two prefixes. If the current elements are also stored, point assignment is first converted into a point increment.

Proof. By Propositions 6.8, 6.9, and 2.2. $$$\square$$$

§4. Construction

Construction 6.11. Initialize $$$c_i=a_i$$$; for $$$i=1,\ldots,n$$$ in order, if $$$p(i)\le n$$$, perform

Proposition 6.12. Construction 6.11 builds (6.4) in $$$O(n)$$$ time.

Proof. In the retained-node forest, the set of node numbers in the subtree of a node $$$i$$$ is exactly $$$R_i$$$: a number $$$p$$$ lies in this subtree if and only if $$$R_p\subseteq R_i$$$, which by Lemma 6.6 is equivalent to $$$p\in R_i$$$. Also, a parent number is strictly greater than a child number, so increasing index order ensures that when a node is processed, all its descendants' initial values have already been accumulated to that node through their unique parent edges. Thus when processing $$$i$$$, $$$c_i=\sum_{p\in R_i}a_p$$$. Each node passes to its parent at most once. $$$\square$$$

Remark. The local increment formula in this chapter assumes an abelian group. The static noncommutative group prefix recovery formula (2.3) cannot directly prove that the same Fenwick increment update formula applies to noncommutative groups.

Chapter 7. Doubling Representation for Idempotent Aggregation

§1. Doubling Table

Fix an idempotent semigroup $$$S$$$ and $$$a\in S^n$$$. This chapter deals only with static sequences.

Definition 7.1. The doubling table is

with domain $$$j\in[0,\lfloor\log_2 n\rfloor]$$$, $$$i\in[1,n-2^j+1]$$$. This table is also called a Sparse Table, abbreviated ST table.

Proposition 7.2. The doubling table is uniquely determined by the following recurrence:

Proof. An interval of length $$$2^j$$$ is the disjoint union of two adjacent intervals of length $$$2^{j-1}$$$; apply Proposition 1.2. $$$\square$$$

Theorem 7.3. For $$$Q=[l,r]\subseteq[n]$$$, let

Then

Proof. Let $$$L=r-l+1$$$, $$$b=2^d$$$; then $$$b\le L \lt 2b$$$. The intervals

are both contained in $$$Q$$$, their left endpoints and right endpoints are arranged in the same order, and $$$I\cup J=Q$$$, $$$I\cap J\ne\varnothing$$$. Apply Proposition 1.5. The proof includes the case $$$I=J=Q$$$. $$$\square$$$

Corollary 7.4. The doubling representation has preprocessing time and space $$$O(n\lambda(n))$$$, and interval query time $$$O(1)$$$.

Proof. The number of table entries is at most $$$n\lambda(n)$$$, and each entry is obtained by a constant number of operations. Precompute an integer logarithm table

then $$$L_s=\lfloor\log_2 s\rfloor$$$, with construction cost $$$O(n)$$$. Formula (7.3) requires only a constant number of table lookups and one semigroup operation. $$$\square$$$

§2. Range Minima on Ordered Sets

Definition 7.5. Let $$$(X,\le)$$$ be a totally ordered set and $$$a\in X^n$$$. Use the lexicographic order on $$$X\times[n]$$$. Write

Since the second components are distinct, the minimum position is unique; it is the leftmost occurrence of the minimum value. $$$\operatorname{rmq}_a$$$ returns a position, and the interval minimum is $$$a_{\operatorname{rmq}_a(l,r)}$$$.

Proposition 7.6. On a totally ordered set, the binary operation defined by taking the smaller of two elements is associative, commutative, and idempotent. Therefore (7.3) applies to (7.5).

Proof. Both parenthesizations return the minimum of the three elements, and the other properties follow directly from the definition of a total order. $$$\square$$$

On the dual total order one obtains maximum queries. The greatest common divisor of nonnegative integers, fixed-word-length bitwise AND, and bitwise OR also give idempotent semigroups, so the doubling representation can be used; these examples do not change the assumptions of Theorem 7.3.

Terminological convention. Below, RMQ specifically means interval minimum-position query on a totally ordered set. Interval aggregation on a general idempotent semigroup is distinguished from RMQ.

Chapter 8. Sequences with Adjacent Differences Equal to One

§1. Equivalence Types of Blocks

Definition 8.1. For $$$m\ge1$$$, call $$$h=(h_1,\ldots,h_m)\in\mathbf Z^m$$$ a unit-difference sequence if

Two integer sequences $$$x,y$$$ of length $$$b$$$ are called translation-equivalent if there exists $$$c\in\mathbf Z$$$ such that $$$y_i=x_i+c$$$, $$$i\in[b]$$$.

Proposition 8.2. Two sequences of the same length are translation-equivalent if and only if their adjacent-difference sequences are the same. Translation-equivalent sequences have the same leftmost minimum position on every common index interval.

Proof. Translation preserves differences. Conversely, equal differences give

for all $$$i$$$. Translation preserves order and equality, hence also preserves the minimum position with index tie-breaking. $$$\square$$$

Definition 8.3. The type of a unit-difference sequence of length $$$b$$$ is

The canonical representative $$$z^\tau$$$ of this type is defined by

The number of types of length $$$b$$$ is exactly $$$2^{b-1}$$$. The type together with the first value of the block uniquely determines the whole block.

§2. Finite Micro Tables

Fix an upper bound $$$B\ge1$$$ on block length.

Construction 8.4. For all types $$$\tau$$$ of length $$$1\le b\le B$$$, and all $$$1\le s\le t\le b$$$, store

For fixed $$$\tau,s$$$, compute the entries in the order $$$t=s,s+1,\ldots,b$$$: the initial entry is $$$s$$$, and thereafter compare the previous minimum position with the new position $$$t$$$, keeping the smaller index when they are equal.

Proposition 8.5. The time and space required to construct all micro tables are both

When an actual block $$$K=[L,L+b-1]$$$ has type $$$\tau$$$, the leftmost minimum position of the subinterval $$$[L+s-1,L+t-1]$$$ is

Proof. For each type, first generate the canonical representative in $$$O(b)$$$ time, then obtain all entries with $$$O(b^2)$$$ comparisons. The total is at most $$$B^2\sum_{b=1}^B2^{b-1} \lt 2^BB^2$$$. Formula (8.6) follows from Proposition 8.2. $$$\square$$$

Encode $$$-1,+1$$$ as $$$0,1$$$, respectively; then the difference part of a type can be represented by a $$$b-1$$$-bit integer. Including the length as part of the encoding distinguishes all tail-block types.

§3. Inter-Block Representation

Construction 8.6. Partition $$$[m]$$$ into consecutive nonempty blocks $$$K_1,\ldots,K_s$$$ of length $$$B$$$, where $$$s=\lceil m/B\rceil$$$, and the last block may have length less than $$$B$$$. Record the type of each block, and let

Each $$$p_j$$$ is obtained from the micro table. Build the doubling representation of Chapter 7 on the sequence $$$(v_j)_{j=1}^s$$$, using lexicographic comparison.

For $$$Q=[l,r]$$$, if the two endpoints belong to the same block, return according to (8.6). Otherwise, split $$$Q$$$ into the following nonempty parts: the suffix of the block containing $$$l$$$, all blocks strictly between the two end blocks, and the prefix of the block containing $$$r$$$. The minimum positions in the first and third parts are obtained from micro tables; if the middle part is nonempty, it is obtained from the inter-block doubling table. Compare at most three candidate keys $$$(h_p,p)$$$, and return the position of the smallest.

Proposition 8.7. Construction 8.6 is correct; preprocessing time and space are both

and each query takes $$$O(1)$$$ time, provided that encoding a type and one table access are word-level operations.

Proof. Each candidate position is the unique lexicographic minimum on a disjoint part; these parts cover $$$Q$$$, so the smallest among the candidates is the minimum of $$$Q$$$. Scanning all differences and forming block types takes $$$O(m)$$$ time; (8.5) controls the micro tables; Corollary 7.4 controls the inter-block representation. A query uses only a bounded number of table accesses and comparisons. $$$\square$$$

§4. Linear Bound

Theorem 8.8. RMQ on unit-difference sequences has a representation with preprocessing time $$$O(m)$$$, space $$$O(m)$$$, and query time $$$O(1)$$$.

Proof. Take

For $$$m\ge16$$$, $$$B=\Theta(\log m)$$$, so

Also,

because $$$(\log_2m)^2/\sqrt m$$$ is bounded for $$$m\ge16$$$. Finitely many smaller $$$m$$$ are covered by enlarging the constant. A type encoding uses at most $$$B-1=O(\log m)$$$ bits, and table addresses also use $$$O(\log m)$$$ bits, satisfying the computational conventions. Substitute into (8.8). $$$\square$$$

Remark. Formula (8.11) does not regard $$$\sqrt m\log^2m$$$ as being of the same order as $$$m$$$; it only uses the fact that it is $$$O(m)$$$. The cost of generating all micro tables has been included in preprocessing and no free external lookup facility is assumed.

Chapter 9. Euler Representation of Rooted Trees

§1. Ancestor Order

Definition 9.1. Let $$$T$$$ be a nonempty finite rooted tree with vertex set $$$V$$$ and root $$$o$$$. Let $$$u\preceq_Tv$$$ mean that $$$u$$$ lies on the unique simple path from $$$o$$$ to $$$v$$$. The depth $$$d(v)$$$ of a vertex is the number of edges on this path. The subtree $$$T_u$$$ of a vertex $$$u$$$ consists of the vertices $$$v$$$ satisfying $$$u\preceq_Tv$$$.

Proposition 9.2. For $$$u,v\in V$$$, the set of common ancestors is nonempty and has a unique maximum under $$$\preceq_T$$$.

Proof. The root is a common ancestor. All ancestors of $$$u$$$ form a finite totally ordered chain under $$$\preceq_T$$$; the set of common ancestors is a nonempty subset of this chain, hence has a unique maximum. $$$\square$$$

Definition 9.3. The maximum element in Proposition 9.2 is denoted $$$\operatorname{lca}_T(u,v)$$$, and is called the lowest common ancestor.

For each vertex, choose and fix a total order on its sons; this yields an ordered rooted tree. This additional choice does not change the ancestor order or the lowest common ancestor.

§2. Euler Sequence

Definition 9.4. For the empty tree, put $$$E(\varnothing)$$$ as the empty sequence. If the sons of $$$u$$$ in the fixed order are $$$v_1,\ldots,v_s$$$, recursively define

When $$$s=0$$$, the right-hand side is by convention $$$(u)$$$. Write $$$E(T)=(e_1,\ldots,e_m)$$$, and define

Proposition 9.5. If $$$|V|=n$$$, then $$$m=2n-1$$$; any two adjacent terms $$$e_j,e_{j+1}$$$ are adjacent vertices in the tree, so $$$h_{j+1}-h_j\in{-1,1}$$$. $$$E(T_u)$$$ occupies a contiguous factor in $$$E(T)$$$, and this factor contains all occurrences of all vertices in the subtree of $$$u$$$.

Proof. If the subtree sizes are $$$n_1,\ldots,n_s$$$, then by the induction hypothesis and (9.1),

Each step in the sequence is a descent or return along some parent-child edge; use the induction hypothesis inside each subtree. The contiguous-factor property follows directly from the recursive concatenation formula: only after the expansion of a subtree is completely finished are the following parent vertex and the next subtree concatenated; there are no other expansions of vertices of that subtree outside it. $$$\square$$$

§3. Shallowest Vertex

Theorem 9.6. Let $$$u,v\in V$$$,

Then

Proof. Both $$$u,v$$$ lie in $$$T_w$$$, so their first occurrences lie in the contiguous factor occupied by $$$E(T_w)$$$; by Proposition 9.5, all terms between the two first occurrences also lie in $$$T_w$$$. Hence all depths in the interval are at least $$$d(w)$$$, and the only vertex in $$$T_w$$$ whose depth equals $$$d(w)$$$ can be $$$w$$$.

It remains to prove that $$$w$$$ occurs in the interval under consideration. If $$$w=u$$$ or $$$w=v$$$, then it already occurs at the corresponding endpoint. Otherwise, $$$u,v$$$ lie in two different son subtrees of $$$w$$$. After swapping $$$u,v$$$ if necessary, assume $$$f(u) \lt f(v)$$$. Formula (9.1) concatenates at least one occurrence of $$$(w)$$$ after finishing the son subtree containing $$$u$$$ and before entering the son subtree containing $$$v$$$, so $$$w$$$ occurs in the interval. This gives (9.3). $$$\square$$$

Remark. Formula (9.3) asserts that the vertex attaining the shallowest depth is unique; it does not assert that the sequence position attaining the shallowest depth is unique. The same vertex $$$w$$$ may occur multiple times in $$$[L,R]$$$.

Corollary 9.7. With the leftmost-minimum-position convention of Chapter 7,

Theorem 9.8. For a rooted tree with $$$n\ge1$$$ vertices, lowest common ancestor queries have a representation with preprocessing time $$$O(n)$$$, space $$$O(n)$$$, and query time $$$O(1)$$$.

Proof. Use the recursive traversal of (9.1) to generate $$$E,h,f$$$. Each edge is descended and returned along exactly once, so time and output space are $$$O(n)$$$; recursion stack space is at most $$$O(n)$$$. By Proposition 9.5, $$$h$$$ is a unit-difference sequence of length $$$2n-1$$$, so Theorem 8.8 applies. Finally query according to (9.4). $$$\square$$$

Chapter 10. Cartesian Trees and General RMQ

§1. Ordered Trees and Heap Order

Fix a totally ordered set $$$X$$$ and $$$a\in X^n$$$, and continue using the lexicographic order on $$$q_i=(a_i,i)$$$. Since positions are distinct, $$$q_1,\ldots,q_n$$$ are pairwise distinct.

Definition 10.1. For an interval $$$[l,r]\subseteq[n]$$$, recursively define the ordered binary tree $$$C_a[l,r]$$$: if $$$l \gt r$$$, take the empty tree; otherwise put

take $$$m$$$ as the root, and take the left and right subtrees to be $$$C_a[l,m-1]$$$ and $$$C_a[m+1,r]$$$, respectively. Write $$$C_a=C_a[1,n]$$$, called the minimum Cartesian tree of $$$a$$$.

The applicability of the recursive definition comes from the fact that both subintervals are strictly shorter than the original interval.

Proposition 10.2. The inorder sequence of $$$C_a[l,r]$$$ is $$$(l,l+1,\ldots,r)$$$. Every non-root vertex $$$v$$$ and its parent $$$u$$$ satisfy

The set of vertex indices of every subtree is a contiguous interval, and the key of its root is the unique minimum key of that interval.

Proof. Induct on interval length. The inorder sequences of the left and right subtrees are given by the induction hypothesis; inserting the root $$$m$$$ between them gives the complete index sequence. The root is chosen by (10.1) as the minimum key of the interval, and since keys are distinct, it is strictly smaller than the keys of all proper descendants. Each subtree is still generated by the same recursion, so the remaining assertions hold simultaneously. $$$\square$$$

Proposition 10.3. $$$C_a$$$ is the unique ordered binary tree with vertex set $$$[n]$$$, inorder sequence $$$(1,\ldots,n)$$$, and satisfying (10.2).

Proof. A root satisfying heap order is strictly smaller along every path than all other vertices, so it must be the unique minimum of all keys. The inorder condition then uniquely specifies the vertex sets of the left and right subtrees as the two intervals before and after the root index. Induct on the two. Existence follows from Definition 10.1 and Proposition 10.2. $$$\square$$$

§2. Equivalence of Queries

Theorem 10.4. For $$$1\le l\le r\le n$$$,

Proof. Put $$$z=\operatorname{lca}_{C_a}(l,r)$$$. The index set of its subtree is some contiguous interval $$$[L_z,R_z]$$$, and contains $$$l,r$$$; hence it also contains the whole $$$[l,r]$$$. By Proposition 10.2, $$$q_z$$$ is no greater than any key in $$$[l,r]$$$.

It remains to prove $$$z\in[l,r]$$$. If $$$z=l$$$ or $$$z=r$$$, the conclusion holds. Otherwise, $$$l,r$$$ must lie in different son subtrees of $$$z$$$; otherwise that son would be a deeper common ancestor than $$$z$$$. By the inorder index order, $$$l$$$ is in the left subtree and $$$r$$$ is in the right subtree, so $$$l \lt z \lt r$$$. Thus $$$z$$$ is the position of the unique minimum key in $$$[l,r]$$$. $$$\square$$$

§3. Right Spine

Definition 10.5. The right spine of a nonempty ordered binary tree is the vertex sequence obtained by starting at the root and repeatedly taking the right son until the right son is empty. Its last term may have a nonempty left subtree.

Proposition 10.6. If the inorder sequence of a tree is $$$(1,\ldots,s)$$$, then vertex $$$s$$$ is the last term of the right spine. If the tree also satisfies (10.2), then the keys on the right spine are strictly increasing from root to last term.

Proof. The last vertex visited in inorder is obtained by repeatedly taking the right son from the root; if the current vertex has no right son, its left subtree has already been visited before it. Hence the last term is $$$s$$$. The monotonicity of keys follows edge by edge from parent-child heap order. $$$\square$$$

§4. Stack Construction

Let $$$0$$$ denote the null pointer. For each $$$i\in[n]$$$, initialize left and right pointers $$$L_i=R_i=0$$$. A stack is a finite sequence $$$S=(s_1,\ldots,s_t)$$$, whose last term is the top; the empty stack is allowed.

Construction 10.7. Initially the stack is empty and the root pointer is $$$0$$$. For $$$i=1,2,\ldots,n$$$, perform the following finite process:

1. Let $$$z=0$$$.
2. While the stack is nonempty and $$$q_{s_t} \gt q_i$$$, set $$$z=s_t$$$ and delete the last term of the stack; repeat this step.
3. Set $$$L_i=z$$$. If the stack is nonempty, let its current last term be $$$p$$$, and set $$$R_p=i$$$; otherwise set the root pointer to $$$i$$$.
4. Append $$$i$$$ to the end of the stack. Keep $$$R_i=0$$$.

Pointers not assigned by the above rules remain unchanged.

Theorem 10.8. After processing position $$$i$$$, the current tree is $$$C_a[1,i]$$$, and the stack lists exactly the right spine of this tree from root to last term.

Proof. Induct on $$$i$$$. The empty-tree case and the case $$$i=1$$$ directly satisfy the assertion. Assume the assertion holds for $$$i-1$$$. By Proposition 10.6, keys in the stack are strictly increasing, so step 2 deletes a terminal subsequence.

If no node is popped, then $$$z=0$$$, and the original stack top has no right son; attach $$$i$$$ as its right son. Because of the loop stopping condition and distinct keys, the key of the original top is less than $$$q_i$$$, so heap order is preserved.

If nodes are popped, then the final $$$z$$$ is the node closest to the root among the popped part. It and its whole subtree form a terminal interval of the inorder sequence of the original tree. If the retained stack is nonempty, its last term $$$p$$$ originally had $$$z$$$ as its right son; if the retained stack is empty, then $$$z$$$ was originally the root. Step 3 makes this whole subtree the left subtree of $$$i$$$, and replaces its original position by $$$i$$$.

In the latter case, the loop gives $$$q_i \lt q_z$$$; if a retained $$$p$$$ exists, additionally $$$q_p \lt q_i$$$. Hence both possible newly added edges satisfy heap order, and all other edges are unchanged. The moved subtree preserves its inorder order, and the new vertex $$$i$$$ follows it and is at the far right of the whole tree, so the new tree has inorder sequence $$$(1,\ldots,i)$$$. By Proposition 10.3, the new tree must be $$$C_a[1,i]$$$.

The new right spine is exactly the retained original stack followed by $$$i$$$; the moved subtree has become a left subtree, and its nodes no longer lie on the right spine. Step 4 restores the stack invariant. $$$\square$$$

Proposition 10.9. Construction 10.7 takes total time $$$O(n)$$$ and space $$$O(n)$$$.

Proof. Each index is pushed exactly once and popped at most once. There are at most $$$n$$$ successful pop comparisons; each outer iteration has at most one additional key comparison that terminates the loop. The remaining assignments are constant many per iteration. Hence the total number of operations is $$$O(n)$$$. Tree pointers and the stack each occupy $$$O(n)$$$ space. $$$\square$$$

§5. General Static Minimum-Position Queries

Theorem 10.10. Under the stated computational model, for any finite sequence of length $$$n\ge1$$$ in a totally ordered set, RMQ has a representation with preprocessing time $$$O(n)$$$, space $$$O(n)$$$, and query time $$$O(1)$$$.

Proof. By Construction 10.7, build $$$C_a$$$ in $$$O(n)$$$ time; by Chapter 9, build a lowest-common-ancestor representation on this tree. By Theorem 10.4, querying $$$[l,r]$$$ is equivalent to querying the lowest common ancestor of vertices $$$l,r$$$ in the tree, which takes constant time. All parts have linear space and preprocessing time. $$$\square$$$

If $$$(E,h,f)$$$ is the Euler representation of $$$C_a$$$, then the above query can be written as the single equation

The inner query in (10.4) is implemented by Chapter 8 and does not depend on the general RMQ being constructed. Hence this construction has no circular dependency in its recursive definition.

Corollary 10.11. Replacing the total order by its dual gives static interval maximum-position queries with the same bounds. Theorem 10.10 itself does not provide the same linear preprocessing bound for arbitrary idempotent semigroups, nor does it provide dynamic modification operations.