# Complexity of Rearranging a Prefix Tree/Alternative Data Structures

Let $$S$$ be a subset of $$[0,1]^l$$. Is there some data structure that can represent $$S$$ and can perform the following operations/queries efficiently*?

1. $$ADD(s \in [0,1]^l)$$ - operation which updates $$S$$ to become $$S\cup \{s\}$$
2. $$REMOVE(s \in [0,1]^l)$$ - operation which updates $$S$$ to become $$S \setminus \{s\}$$
3. $$PERMUTE(\sigma)$$ - operation which updates $$S$$ to become $$\{\sigma(s) : s \in S\}$$, where sigma is a permutation of $$s$$, which rearranged its indices/letters according to a bijection
4. $$START(t \in [0,1]^k)$$ - query which returns whether or not there is a string $$s \in S$$ whose first $$k$$ letters are the same as $$t$$

*By efficiently, I mean that it can perform each of the above with worst case complexity $$c^{o(l)}$$. In other words, I am fine with complexity that is exponential, but I want the exponent to be sublinear in $$l$$.

A simple prefix tree can do 1, 2, and 4 all linear in $$l$$, but I can't fathom that it can efficiently do 3. However, if you needed to only support 4 for substrings up to length $$k$$, we could keep track of how are indices have been permuted since the beginning, and just have $$k!\binom{l}{k}$$ prefix-trees for each way that could start, which would make 3 and 4 linear, and 1 and 2 $$O(l^k)$$.

• You don’t actually permute the array. You just store and update the permutation, and only access the array through it. – Yuval Filmus Aug 30 '19 at 18:58
• @Yuval Filmus if all my arrays end in "0", and we swap the first and last indices, I'd have to explore every leaf before I got my answer to $START(1)$ – Zachary Hunter Aug 30 '19 at 19:11
• What class of maps $\sigma$ do you want to support? How is $\sigma$ represented? – D.W. Aug 30 '19 at 19:24
• A map $\sigma$ will be a bijection on the indices $1,2 \dots l \to 1,2 \dots l$. I wish to support all such maps/permutations $\sigma$. You can choose to use whichever representation of $\sigma$ you desire. – Zachary Hunter Aug 30 '19 at 19:33
• Have you tried to apply range trees? – Dmitri Urbanowicz Sep 3 '19 at 7:32