State of the art time complexity for getting (tree) descendants by type/attribute Let's say I have a tree comprised of nodes where each node is of some type (T), where there is a known/fixed number of types (i.e. similar to attributes in an xml document), and where a node can only have one type. Let's also assume that our tree is somewhat balanced, and that there are far more nodes in the tree than there are unique types. Assuming I have already created some sort of index on the tree, I need to know the state of the art time complexity for the following types of queries (using whatever type of index / data structure you like):

Where A is some arbitrary node in the tree and T is some arbitrary type:


find all descendants of node A that are of type T
find the number of descendants of node A that are of type T


If the tree is static and no updates to the index are required, I have a data structure that will do 1 and 2 in $O(1)$. If the tree can have nodes added/removed, I also have a data structure that will do 1 and 2 in $O(\log m)$ where m is the total number of nodes of type T in the tree ($m &lt;&lt; n$), and that can update the index when changes are made to the tree in $O(k\log m)$ where k is the number of nodes affected.

Are my data structures state of the art for these types of queries, or on par with state of the art? What existing work is out there that can match or beat this performance, if any?

(assume that any indexing structure we use must take less than $O(n^2)$ time and memory to construct)

(assume that any indexing structure we use for the case where the tree/index can be modified, that modifications can be handled in better than $O(n)$)

My understanding is that XML indexing generally has the state-of-the-art indexing schemes for dealing with trees where there are typed nodes, so I assume something with XML indexing will crop up here. I've tried looking through a number of papers myself but it's very difficult to get actual time complexities out of people in that field for some reason.
For the static case, if you have a solution with $O(1)$ running time, I can't see any opportunity for improvement in the running time, as you can't do better than $O(1)$.  So I'll focus on the dynamic case, i.e., where we want to support insertions and deletions.

One strategy is to augment the tree, so that for each type $T$ each node $x$ contains:


A count of the number of descendants of type $T$
A pointer to each immediate type-$T$ descendant of $x$ (i.e., a link to each $z$ such that $z$ has type $T$, $z$ is a descendant of $x$, and there is no descendant $y$ of $x$ such that $y$ has type $T$ and $z$ is a descendant of $y$)
A pointer to the immediate type-$T$ parent of $x$ (i.e., the lowest ancestor of $x$ that has type $T$)


This allows 'count' queries to run in essentially $O(1)$ time: given a node $x$, you can count the number of type-$T$ descendants of $x$ in $O(1)$ time.  (Simply find $x$'s immediate type-$T$ parent, then use the field in the parent that stores the count of number of type-$T$ descendants.)

Also, 'enumerate' queries run in $O(k)$ time: given a node $x$, you can enumerate all type-$T$ descendants of $x$ in $O(k)$ time, where $k$ is the number of type-$T$ descendants of $x$.  (Simply find $x$'s immediate type-$T$ parent, then traverse the fields that list the immediate type-$T$ descendants, recursively.)

The running time to insert a new leaf at depth $d$ in $O(d)$ time, since you only need to update the fields in the nodes along the path from that leaf to the root.  If the tree is balanced, this is $O(\log n)$ time.

The running time to delete a leaf at depth $d$ is the same, for the same reasons.

This is the best I know how to do.  I don't know if it is possible to do better.