Cat Tree

Introduction

It is well known that a segment tree can answer queries for information over an interval, such as the maximum subarray sum, a range sum, or the product of matrices on an interval.

However, ordinary segment-tree range queries may still be too slow in some situations.

In brief, building a segment tree requires $O(n)$ merge operations, while each range query requires $O(\log{n})$ merge operations. The latter is acceptable for a range sum, but when the queried information is a linear basis whose merge costs $O(\log^2{w})$, even $O(\log{n})$ merges can sometimes be too slow.

A “cat tree” is a static segment tree that does not support updates and only supports fast range queries.

Building such a static segment tree requires $O(n\log{n})$ merge operations, but a query then needs only $O(1)$ merge operations.

For special information such as a linear basis, the complexity can even be reduced to $O(n\log^2{w})$.

Principle

To query the information on $[l,r]$, find the LCA in the segment tree of the nodes representing $[l,l]$ and $[r,r]$. Let this node be $p$, and let its interval be $[L,R]$. We have two useful properties:

1. The interval $[L,R]$ contains $[l,r]$. This is immediate because it is an ancestor of both $l$ and $r$.

2. The interval $[l,r]$ crosses the midpoint of $[L,R]$. Since $p$ is the LCA of $l$ and $r$, the left child of $p$ is an ancestor of $l$ but not of $r$, while the right child of $p$ is an ancestor of $r$ but not of $l$. Therefore, $l$ lies in $[L,\mathit{mid}]$ and $r$ lies in $(\mathit{mid},R]$.

With these two properties, the query complexity can be reduced to $O(1)$.

Implementation

More specifically, when building the tree, let a segment-tree node represent $(l,r]$.

Unlike a traditional segment tree, which stores only the sum on $[l,r]$ at this node, we additionally store the suffix sums on $(l,\mathit{mid}]$ and the prefix sums on $(\mathit{mid},r]$.

The construction complexity is $T(n)=2T(n/2)+O(n)=O(n\log{n})$. Similarly, the space complexity increases from $O(n)$ to $O(n\log{n})$.

The query is the key part.

If the queried interval is $[l,r]$, find the LCA of the nodes representing $[l,l]$ and $[r,r]$, denoted by $p$.

By the two properties above, $l,r$ are inside the interval represented by $p$ and cross the midpoint of $p$.

This gives the crucial fact that, using the prefix and suffix sums stored at $p$, we can split $[l,r]$ into $[l,\mathit{mid}]+(\mathit{mid},r]$, and then combine them to obtain the interval $[l,r]$.

This process requires only $O(1)$ merge operations.

But there seems to be a missing detail.

Finding the LCA does not itself appear to take $O(1)$ time: a brute-force search takes $O(\log{n})$, binary lifting takes $O(\log{\log{n}})$, and converting to an ST table has too much overhead…

Heap-style construction

Specifically, pad the sequence to a power of $2$ and then build the segment tree.

The LCA index of two segment-tree nodes is the longest common prefix (LCP) of their binary indices.

It is easy to see that for the binary representations of $x$ and $y$, lcp(x,y)=x>>digits[x^y]. Here digits[x] denotes the number of bits in $x$, namely $\lfloor \log_2 x \rfloor+1$.

Thus, precomputing a digits array lets us find LCAs easily.

This constructs a cat tree.

When building the tree, we compute prefix and suffix sums. For a linear basis, whose merge costs $O(\log^2{w})$ but whose prefix sum costs $O(n\log{n})$, a cat tree improves the complexity of a static range-linear-basis structure from $O(n\log^2{w}+m\log^2{w}\log{n})$ to $O(n\log{n}\log{w}+m\log^2{w})$.

References

• immortalCO's blog
• [Kle77] V. Klee, "Can the Measure of be Computed in Less than O (n log n) Steps?," Am. Math. Mon., vol. 84, no. 4, pp. 284–285, Apr. 1977.
• [BeW80] Bentley and Wood, "An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles," IEEE Trans. Comput., vol. C–29, no. 7, pp. 571–577, Jul. 1980.