Errata

Serious ones

1. 361 In the middle of the page, it says "As the k^2 children distribute across k contiguous segments in the LOUDS layout, the cost that is charged to v decreases to O(k)". This argument is correct when reused for the nodes of type (2), but for nodes of type (1) all the children are contained in the query, and then all the children are interesting, and contiguous in the LOUDS layout. Therefore, the correct cost charged to v is O(1). This allows us remove the factor k that accompanies occ in the displayed formula of the final cost. Thanks to Ariel Cáceres for noting this. Further, there is an extra closing parenthesis at the end of this formula.
2. 371 Near the bottom of the page, by the same argument of the correction in page 361, the factor k^(d-1) multiplying occ can be removed. Instead, q^(d-1) should rather be d * q^(d-1) , which is the surface of the query.
3. 374 The method for finding the m closest points via successively enlarging the area until at least m points are found is not complete. Once those points are found, we must take the distance to the mth closest one, and perform a final query with this distance. Then we capture at least m points again and then take the m closest ones. This is because a box around the query may capture points that, with Manhattan distance, are farther than some points not included in the box. Thanks to Patricio Huepe for pointing this out.
4. 475 In line 9 of Algorithm 12.13, open(B,v-1) must be replaced by parent(T,v), as the former leaves us in the middle of the signature of the parent. Thanks to Kunihiko Sadakane for noting this.

Medium ones

1. 22 Example 2.10 is not totally consistent with Example 2.8, because here we are considering the terminator $ for the string S, and in Example 2.8 we are not. As a consequence, it could have been that the high-order entropy was larger than the zero-order entropy. Thanks to Sebastian Maneth for noting this.
2. 68 In line -3, "= 5" should be "= C[5]". Thanks to José Fuentes for noting this.
3. 79 In Figure 4.4, the value "10" in the array R (on top) should not be grayed. Thanks to Kajetan Johannes Hammerle for noting this.
4. 80 In line 7 of Algorithm 4.6, the condition should be "<" instead of "≤". Thanks to Kajetan Johannes Hammerle for noting this.
5. 83 In the displayed formula, select_1(S,j) should be select_1(B,j). Thanks to Rolando Kindelan for noting this.
6. 88 In the middle of the page it says "If A contains zeros, we can instead encode the values A[i]+i...". That "A[i]" should rather be "sum(A,i)". Thanks to Yusaku Kaneta for spotting this.
7. 124 In line -3, access(S_2) should be access(S_2,3). Noted by Kunihiko Sadakane.
8. 154 In line 2, it should have said n o(H_0(S)) bits, not o(n H_0(S)) bits. Further, this can then be expressed as o(n H_0(S)) + O(n) bits, which then matches correctly with the rest of the analysis (see the small errata in page 127).
9. 169 Right before Example 7.4, bwdsearch(B,i,-d-1) should be bwdsearch(B,i,-d-1)+1, as implied by the formula of enclose(B,i) in the previous page. Thanks to Ariel Cáceres for noting this.
10. 186 Before Example 7.10, we say we use fwdsearch(i-1,m). However, we have described this algorithm only for the case m < 0, whereas it could be that the minimum excess in the range is m=1. This exception can be easily handled by noting that, in this case, fwdsearch(i-1,1) is always i. The same holds a few lines later for fwdsearch(i-1,M) when M = -1; the answer is i. Thanks to Ariel Cáceres for noting this.
11. 193 In line 15, B should be V. Noted by Ariel Cáceres.
12. 195 In line -10, V[i][j]+1 should be m[V[i][j]]+1. Communicated by Kunihiko Sadakane.
13. 240 In Section 8.3.1, we store the signature of sigma bits for every tree node, including leaves, whose signature is known to be formed by sigma zeros. We can gain a lot of space by storing signatures of internal nodes only in array S. To address it from the tree, we must count the number of internal nodes up to the current one, with nodemap(T,v) - leafrank(T,v) + 1. Noted by Asunción Gómez.
14. 284 The code for adj(G,v,u) is much more complicated than necessary. One can remove lines 6-9 and add a line "if v < u then exchange u and v" between lines 2 and 3. Also, in line 18, b+j should be b-v+j.
15. 305 In line 5, v'_s should be u'_s. Noted by Kunihiko Sadakane.
16. 316 The definition of L, "Every run of k (equal) brackets in B_s...", could be clearer: "Every run of brackets belonging to the same node in B_s (note that those brackets must be equal)...". Thanks to Simon Gog for noting this.
17. 334 Algorithm 9.19 claims to correspond to the algorithm "Face-2" referenced in page 342, but they have some subtle differences, since our algorithm never uses an edge that crosses the imaginary line and sometimes this is necessary. In fact, one must remember the point (not necessarily node) p where the edge would cross the line (initially p is the source), and allow following edges if the cross the line exactly at point p. This fixes some special cases where the general algorithm would fail.
18. 363 Line 18 in Algorithm 10.6 may try to compute an rMq on the final wavelet matrix level, where rMq structures are not built because the y ranges are of length 1. To fix this we must build that final rMq level, so we can find maximum priorities among points with the same y values. Noted by Robert Koguciuk, Lublin, Poland.
19. 458 In lines 17-18 of Algorithm 12.4 (procedure insw), the algorithm needs to decrease i to account for the bits skipped in the left child, that is, insert the instruction i = i - v.num. Thanks to Jan-Philipp Tarnowski for noting this.
20. 518 The space given for Gagie et al. 2012, under "Kernelization", is in addition to a context-free grammar for the text, not standalone.
21. 520 In Example 13.14, the penultimate block of S should look "ade ae" rather than "adeae". The string is the same, but the logic of its generation is apparent when properly segmented. Similarly, there should be a space after the underlined "b" in the last string.
22. 536 On the right of Figure 13.7, the trie node reached by "a" should have 5 inside, not a 4.

Small ones

1. 3 In line 3 of Section 1.2, "fluorished" should be "flourished". Thanks to Kunihiko Sadakane for noting this.
2. 42 In the caption of Figure 3.2, it should say B[j',j], not B[j',j']. Thanks to Kunihiko Sadakane for noting this.
3. 90 The last parenthesis in the "return" line of the pseudocode is spurious and should be removed. Thanks to Kunihiko Sadakane for noting this.
4. 118 In the bibliographic discussion on compressible permutations, we found that an old paper [T. Takaoka, A New Measure of Disorder in Sorting, Proc. CATS, pp. 77-86, 1998] had already given the idea of merging in the order induced by the Huffman tree to perform MergeSort. Followups were pubished much later in a conference [T. Takaoka, Partial solution and entropy, Proc. 34th MFCS, pp. 700-711, 2009] and then in a journal [T. Takaoka, Entropy as computational complexity, Journal of Information Processing 18:227-241, 2010]. Thanks to Jérémy Barbay for this pointer.
5. 127 In Footnote 1, it would be good to mention that a common way to express the formula is o(n log sigma) + O(n).
6. 128 In line 23, "charge it" could be "charge x" for maximum clarity in a difficult paragraph. Thanks to Kunihiko Sadakane.
7. 188 In Secion 7.1.4, "deepest segments" should actually be "segments with no children". Noted by Ariel Cáceres.
8. 190 In line -12, "if have" should be "if we have". Further, we might note that the access to C[.][l'] requires first shifting the bits of the last block covering B[i,j].
9. 201 In lines 13 and 14 we could have used i-1 instead of i and the method would also work when t is of the same type of P[i].
10. 209 In line 10, we should use the term "compact", not "succinct". Technically, succinct solutions must use 2n+o(n) bits. Noted by Kunihiko Sadakane.
11. 209 We cite Sadakane (2007), but not the correct one: Succinct data structures for flexible text retrieval systems. Journal of Discrete Algorithms, 5, 12-22. In this paper, he actually gives a general rmq_A solution using 4n+o(n) bits by adding n-1 leaves to the Cartesian tree. Noted by Kunihiko Sadakane.
12. 216 In line 9 of Algorithm 8.1, the last closing parenthesis is spurious and should be removed. Thanks to Kunihiko Sadakane.
13. 232 In line 5, it would be better to exchange u and v in this comment, because we have just discussed how to compute the area below v. Noted by Kunihiko Sadakane.
14. 249 In line 11, the construction of RePair is linear expected time, as they use hashing. Noted by Kunihiko Sadakane.
15. 252 There are only 19 names, not 20, in the trie of Figure 8.19. Noted by Kunihiko Sadakane.
16. 275 The link to www.registrocivil.cl is not anymore available. Noted by Kunihiko Sadakane.
17. 276 The bibliographic entry of Belazzougui et al. is missing its second author, P. H. Cording.
18. 308 Instead of "The exact entropy of planar graphs (without defining their mapping to the plane) is unknown, but it must be less than 3.58e.", the following would have been more accurate: "Planar graphs (without defining their mapping to the plane) must have a lower entropy, but that value is unknown."
19. 330 In line 5, "Carol" should be "Alice", because Carol already lives in NY like Emma. Thanks to Kunihiko Sadakane for noting this.
20. 330 In line 14, "brand" should be "branch". Thanks to Kunihiko Sadakane for this.
21. 361 There is a spurious closing parenthesis at the end of the second formula, which should be deleted. Thanks to Kunihiko Sadakane for noting this.
22. 542 The second bibliographic entry of Belazzougui et al. (the last in the page) is missing its second author, P. H. Cording.