In the example they sort the data array. Does that mean this works just on sorted arrays? Insert and delete performance would be horrible I guess.
Yep, the example of Figure 2 shows only a static PGM-index on a sorted array.
Insertion and deletions are discussed in Section 3 "Dynamic PGM-index" and experimented in Section 7.3.
The Dynamic PGM-index is open-source too: you can find the implementation at https://github.com/gvinciguerra/PGM-index/blob/master/includ... and the documentation at https://pgm.di.unipi.it/docs/cpp-reference/#classpgm_1_1_dyn...
I agree the example would be more eye-catching without that sort.
A very abridged explanation of how they handle inserts: you split the collection in a list of collections where position k contains either nothing or a collection size 2^k. When you want to add a new value you find the first empty spot and fill it by building a set of your new value together with the collections of all the preceding spots (because the sizes are all sequential powers of two this will fit exactly). Provided that merging the collections takes linear time this takes an amortized O(log(n)) per inserted item.
Of course once you have this you can use it for any learned index that can be learned in linear time.
[1]: M. H. Overmars. The Design of Dynamic Data Structures, volume 156 of Lecture Notes in Computer Science. Springer, 1983.
There are many indexing schemes for data with these properties. They focus on topological relationships rather than order relationships.