> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-v-advanced-data-structures/17.-augmenting-data-structures.md). # 17. Augmenting Data Structures ## Exercises ### 17.1-1 **Available in the latest revision of the IM.** ### 17.1-2 **Available in the latest revision of the IM.** ### 17.1-3 **Available in the latest revision of the IM.** {% hint style="danger" %} The code in the IM is broken. Here is the fixed version (line 8 were missing): ``` OS-Select(x, i) 1 r = x.left.size + 1 2 while i != r 3 if i < r 4 x = x.left 5 else 6 x = x.right 7 i = i - r 8 r = x.left.size + 1 9 return x ``` {% endhint %} ### 17.1-4 **Available in the latest revision of the IM.** ### 17.1-5 **Available in the latest revision of the IM.** ### 17.1-6 **Available in the latest revision of the IM.** {% hint style="warning" %} To text in the IM contains a completely redundant sentence *"Similarly when deleting, subtract 1 from x:rank whenever the spliced-out node had been in x’s left subtree."* Because it starts with *"Similarly..."*, it reads as if it is introducing a new rule or handling an edge case. In reality, it is just repeating the exact logic that the previous paragraphs already covered. {% endhint %} ### 17.1-7 **Available in the latest revision of the IM.** ### ★ 17.1-8 **Available in the latest revision of the IM.** ### 17.2-1 🌟 {% hint style="success" %} Demonstrates an interesting approach of creating a hybrid data structure consisted of a doubly linked list and an augmented order-statistic tree, which nicely interplay to support all operations efficiently. For example, a tree may help quickly locate the corresponding node based on a key value, while a linked list may provide additional information (like, successor) in $$O(1)$$ time. {% endhint %} **Available in the latest revision of the IM.** ### 17.2-2 **Available in the latest revision of the IM.** ### 17.2-3 **Available in the latest revision of the IM.** ### 17.3-1 **Available in the latest revision of the IM.** ### 17.3-2 **Available in the latest revision of the IM.** {% hint style="warning" %} The function `Min-Interval-Search-From` unconditionally branches to `x.right` in the last line even if it is `T.nil`. Furthermore, it assumes that `x` is not `T.nil`. An easy fix is to simply insert a test in line 1 whether `x` is `T.nil` and return `T.nil` if positive. {% endhint %} ### 17.3-3 The non-modifying version of the pseudocode follows the structure of the solution from the previous exercise. An ordinary inorder traversal of a tree would entail a $$\Theta(n)$$ runtime. Leveraging additional information stored in nodes we can make informed decisions whether to descend into branches. This reduces the running time as given in the book. There is only one caveat, that an unsuccessful search also consumes time, so for $$k=0$$ we don't have a zero time. ``` All-Interval-Search(T, i) 1 out = a new empty linked list 2 All-Interval-Search-From(T, T.root, i, out) 3 return out All-Interval-Search-From(T, x, i, out) 1 if x != T.nil 2 // Search the left subtree if it can possibly contain overlaps. 3 if x.left != T.nil and x.left.max >= i.low 4 All-Interval-Search-From(T, x.left, i, out) 5 6 // Check if the current node's interval overlaps i. 7 if x.int.low <= i.high and x.int.high >= i.low 8 List-Insert(out, x.int) 9 10 // Search the right subtree if it can possibly contain overlaps. 11 // We only go right if x.int.low <= i.high (since right children 12 // have even greater low endpoints) and the right subtree's max >= i.low. 13 if x.right != T.nil and x.int.low <= i.high and x.right.max >= i.low 14 All-Interval-Search-From(T, x.right, i, out) ``` ### 17.3-4 First, we must modify the tree's insertion procedure to use i`nt.high` as a secondary key. * If `i.low < x.int.low`, go left. * If `i.low > x.int.low`, go right. * If `i.low == x.int.low`, compare `i.high` and `x.int.high` to decide whether to go left or right (see below). {% hint style="info" %} Leaving the `max` attribute and the standard overlap logic completely untouched means all our existing operations—like regular interval search—work as before. {% endhint %} With the above modification, an interval tree can be regarded as an ordinary BST for exact search. ``` Interval-Search-Exactly(T, i) 1 x = T.root 2 while x != T.nil 3 if i.low == x.int.low and i.high == x.int.high 4 return x 5 if i.low < x.int.low or (i.low == x.int.low and i.high <= x.int.high) 6 x = x.left 7 else 8 x = x.right 9 return T.nil ``` ### 17.3-5 **Available in the latest revision of the IM.** ### ★ 17.3-6 **Available in the latest revision of the IM.** ## Problems ### 17-1 Point of maximum overlap **Available in the latest revision of the IM.** ### 17-2 Josephus permutation **Available in the latest revision of the IM.** {% hint style="info" %} The modular arithmetic to compute the next rank $$j$$ is as follows:\ `j = (j + m - 1) mod k`\ `if j == 0`\ `j = k`\ \ The IM employs a neat trick to condense all this into a one-liner: `j = ((j + m - 2) mod k) + 1`. The idea is to first shift the whole domain down by subtracting -1. The modulo operator safely wraps the value within the range $$\[0, k-1]$$. Adding 1 shifts the result back to the desired $$\[1, k]$$ range. {% endhint %}