Skip to content

Cat Tree

Introduction

It is well known that segment trees can support fast queries for information over a certain interval, such as the maximum subsegment sum, interval sum, product of interval matrices, etc.

However, a problem is that the interval queries of ordinary segment trees may still be considered somewhat slow in the eyes of some malicious problems.

Simply put, building a segment tree requires \(O(n)\) merge operations, and each interval query requires \(O(\log{n})\) merge operations. Queries like interval sum can still be tolerated, but when we need to query information like interval linear basis, where the merge complexity is as high as \(O(\log^2{w})\), even \(O(\log{n})\) merge operations can sometimes be unacceptable in terms of time.

The so-called "cat tree" is a static segment tree that does not support modifications but only supports fast interval queries.

Constructing such a static segment tree requires \(O(n\log{n})\) merge operations, but the query complexity is accelerated to \(O(1)\) merge operations.

When dealing with special information like linear basis, the complexity can even be reduced to \(O(n\log^2{w})\).

Principle

When querying the information of the interval \([l,r]\), find the LCA on the segment tree between the node representing \([l,l]\) and the node representing \([r,r]\). Let this node \(p\) represent the interval \([L,R]\). We will discover some very interesting properties:

  1. The interval \([L,R]\) must contain \([l,r]\). Obviously, because it is an ancestor of both \(l\) and \(r\).

  2. The interval \([l,r]\) must cross the midpoint of \([L,R]\). Since \(p\) is the LCA of \(l\) and \(r\), this means that the left child of \(p\) is an ancestor of \(l\) but not of \(r\), and the right child of \(p\) is an ancestor of \(r\) but not of \(l\). Therefore, \(l\) must be within the interval \([L,\mathit{mid}]\), and \(r\) must be within the interval \((\mathit{mid},R]\).

With these two properties, we can reduce the query complexity to \(O(1)\).

Implementation

Specifically, when building the tree, for a node on the segment tree representing the interval \((l,r]\).

Unlike the traditional segment tree, which only stores the sum of \([l,r]\) in this node, we additionally store the suffix sum array of \((l,\mathit{mid}]\) and the prefix sum array of \((\mathit{mid},r]\) in this node.

Thus, the complexity of building the tree is \(T(n)=2T(n/2)+O(n)=O(n\log{n})\), and similarly, the space complexity increases from the original \(O(n)\) to \(O(n\log{n})\).

The following is the most crucial part: the query.

If the interval we query is \([l,r]\), we find the LCA of the node representing \([l,l]\) and the node representing \([r,r]\), denoted as \(p\).

According to the two properties mentioned earlier, \(l\) and \(r\) are within the interval contained by \(p\) and must cross the midpoint of \(p\).

This implies a very key fact: we can use the prefix sum array and suffix sum array inside \(p\) to split \([l,r]\) into \([l,\mathit{mid}]+(\mathit{mid},r]\), thereby constructing the interval \([l,r]\).

And this process requires only \(O(1)\) merge operations!

However, it seems we have overlooked something?

It seems that the complexity of finding the LCA is not yet \(O(1)\). The brute-force method is \(O(\log{n})\), the binary lifting method is \(O(\log{\log{n}})\), and converting to an ST table is too costly...

Heap-style Tree Building

Specifically, we pad the sequence to a power of \(2\) and then build the segment tree.

At this point, we find that the LCA number of two nodes on the segment tree is the longest common prefix (LCP) of their binary numbers.

A little thought reveals that in binary, lcp(x,y)=x>>digits[x^y]. (Here, digits[x] represents the number of bits of \(x\) in binary, i.e., \(\lfloor \log_2 x \rfloor+1\).)

Therefore, we can preprocess a digits array to easily complete the task of finding the LCA.

Thus, we have constructed a cat tree.

Since building the tree involves calculating prefix sums and suffix sums, for information like linear basis, where merging is \(O(\log^2{w})\) but calculating prefix sums is \(O(n\log{n})\), using a cat tree can optimize the static interval linear basis from \(O(n\log^2{w}+m\log^2{w}\log{n})\) to \(O(n\log{n}\log{w}+m\log^2{w})\) complexity.

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