Designing a Hash Function

To count the number of unique binary trees, let us consider hashing binary trees. What kind of hash functions can be used?

As shown in the figure below, define a function \(S\) that expands a binary tree with \(N\) vertices into a string of length \(3N\).

Formally, for a binary tree \(T\), let \(T_L\) and \(T_R\) denote the left and right subtrees of the root of \(T\), respectively. Then \(S(T)\) is defined as follows:

\[ S(T) = \begin{cases} \text{\text{empty string}}& (T\text{ is empty})\\ \text{``\verb/{/''} + S(T_L) + \text{``\verb/|/''} + S(T_R) + \text{``\verb/}/''} & (\text{otherwise})\\ \end{cases} \]

Since this function is injective, the rolling hash of \(S(T)\) is suitable as a hash of \(T\).
Additionally, you can remove all } characters to reduce the length of \(S(T)\) to \(2N\) while maintaining injectivity.

Transforming the Problem

Instead of computing the hash of \(C(l, r)\) directly, we can compute the minimum value \(A_m\) of \(A_l, A_{l+1}, \dots, A_r\), and then separately compute the hashes of \(C(l, m - 1)\) and \(C(m + 1, r)\).
For simplicity, let us focus on computing \(C(l, m - 1)\); the computation of \(C(m + 1, r)\) follows a similar approach.

By transforming the problem in this way, the range of the interval is restricted, making the problem easier to solve. Specifically, \(C(l, m - 1)\) appears as a subtree of \(C(l, N)\). Thus, the problem can be solved using the following steps:

• For \(l' = N, N - 1, \dots, 1\):
  • Construct \(C(l', N)\) from \(C(l' + 1, N)\).
  • Compute the rolling hash of a subtree of \(C(l', N)\) as a string.

The operation “computing the rolling hash of a subtree as a string” can be implemented by managing the rolling hash of an interval using a segment tree.
Then, it suffices to handle the following:

• Reflect changes in the Cartesian Tree when \(l'\) decreases in the segment tree.
• Identify the segment tree interval corresponding to a subtree.

Managing the Segment Tree

For \(C(1, N)\) and the string expanded from it, consider the correspondence between vertices and the three characters, as shown below:

Let \(V\) be a subset of vertices of \(C(1, N)\) such that \(x, y \in V \implies \operatorname{LCA}(x, y) \in V\). From \(A\), extract the elements corresponding to the vertices in \(V\) to form a sequence \(A'\), and extract the characters corresponding to the vertices in \(V\) from \(S(C(1, N))\) to form a string \(S'\).
It can be shown that \(S'\) matches the string expansion of the Cartesian Tree of \(A'\). If \(V\) corresponds to an interval in the original sequence \(A\), the condition “\(x, y \in V \implies \operatorname{LCA}(x, y) \in V\)” is satisfied. Thus:

• When \(l'\) decreases, the change in the Cartesian Tree corresponds to “adding three characters.”
• The interval in the segment tree corresponding to a subtree is the interval from { to } among the three characters corresponding to the root of the subtree.

Summary

In summary, the problem can be solved as follows:

1. Compute \(S(C(1, N))\) and create a table mapping each vertex to its corresponding three characters.
2. Manage the rolling hash with a segment tree of length \(3N\), initially filled with the hash of empty strings.
3. For \(l' = N, N - 1, \dots, 1\):
   1. Add the three characters corresponding to vertex \(l'\) to the segment tree.
   2. For each query where \(l = l'\), compute the hash of \(S(C(l, m - 1))\).
4. Prepare another segment tree of length \(3N\).
5. For \(r' = 1, 2, \dots, N\):
   1. Add the three characters corresponding to vertex \(r'\) to the segment tree.
   2. For each query where \(r = r'\), compute the hash of \(S(C(m + 1, r))\).
6. Count the number of unique hash pairs.

The time complexity is \(O((N + Q) \log (N + Q))\).

Implementation Example (C++)