Augmented map

The augmented map can be supported efficiently by augmented trees, where each tree node is augmented by the augmented value of all entries in its subtree. Because of the associativity of the combine function ${\displaystyle f}$, the augmented value of a certain tree is fixed, and is independent of the shape of the tree, regardless of rotations. In this case, by combining the partial sums in the tree nodes, any range sum can be returned in ${\displaystyle O(\log n)}$ time on an augmented map of size ${\displaystyle n}$, assuming both ${\displaystyle f}$ and ${\displaystyle g}$ have constant cost. For aug_filter, the tree structure takes the advantage that if the augmented value of a subtree does not satisfy the indicator ${\displaystyle h}$, the whole tree gets discarded. In this case, the cost of aug_filter is ${\displaystyle O(k\log(1+{\frac {n}{k}})}$ where ${\displaystyle k}$ is the output size. For aug_project, whenever a whole subtree falls in the range ${\displaystyle [k_{1},k_{2}]}$, its augmented value can be directly combined to the result, instead of requiring traversing the tree.

Another implementation is to use prefix structures,[2] which stores the augmented value of all prefixes of the map. For the above-defined augmented map ${\displaystyle M_{1}}$, the prefix structure is an array stored the prefix sum of the values, sorted by their keys. Prefix structures are particularly useful for aug_left, but can be inefficient to implement other functions on the augmented map interface. It can be useful in some geometric algorithms.

A 1D stabbing query takes as input a set of intervals on 1D number line. The query asks for if a given point is covered by any input interval, or all intervals covering this point. An augmented map can be defined for this problem, where the keys are the left endpoints of all intervals, values are the corresponding right endpoints, and the augmented value is the maximum value of all right endpoints in the map. More formally:

${\displaystyle M_{interval}=(\mathbb {R} ,<_{\mathbb {R} },\mathbb {R} ,\mathbb {R} ,(k,v)\mapsto v,{\text{max}}_{\mathbb {R} },-\infty )}$

To report if any interval covers a given point ${\displaystyle p}$, the query algorithm simply determines if aug_left${\displaystyle (p)>p}$. This is because aug_left looks at all intervals that start before ${\displaystyle p}$, and if the maximum right endpoint among them exceeds ${\displaystyle p}$, then ${\displaystyle p}$ must be covered. When implemented with augmented trees, the augmented map ${\displaystyle M_{\text{interval}}}$ is exactly an interval tree. Constructing such an augmented tree structure costs work ${\displaystyle O(n\log n)}$, ${\displaystyle O(\log n)}$ parallel depth and ${\displaystyle O(n)}$ space. Each stabbing query can be done in time ${\displaystyle O(\log n)}$.

A 2D range query takes as input a set of points on 2 dimensions. The query asks for all points (or the number) in a certain rectangle, whose edges are parallel to the axis. An augmented map can be defined for this problem, which is a two-level nested map structure. The outer map stores all points and sort them by their x-coordinates. The augmented value of the outer map is an inner augmented map structure, which stores the same set of points as the outer map, but sorts them by their y-coordinates. The augmentation of the inner trees accumulate the count of points, i.e., the augmented value of an inner map is its size. Accordingly, the combine function of the outer map is to take a union of the two inner augmented maps. More formally:

${\displaystyle M_{inner}=(Y,<_{Y},X,\mathbb {Z} ,(k,v)\mapsto 1,+_{\mathbb {Z} },0)}$
${\displaystyle M_{outer}=(X,<_{X},Y,M_{\text{inner}},(k,v)\mapsto M_{\text{inner}}.singleton(v,k),M_{\text{inner}}.{\text{union}},M_{\text{inner}}.{\text{empty}})}$

Here for simplicity, assume all coordinates are unique. ${\displaystyle X}$ and ${\displaystyle Y}$ are the types of the x- and y-coordinates. To answer the range query in rectangle ${\displaystyle (x_{1},x_{2},y_{1},y_{2})}$, the query algorithm extracts the augmented value of the outer map in the key range ${\displaystyle [x_{1},x_{2}]}$, which is an inner map of all desired points sorted by y-coordinates. Therefore, the algorithm takes another aug_range on this inner map and gets the result. For counting queries, the algorithm can make use of the aug_project function.

${\displaystyle query(m,x_{1},x_{2},y_{1},y_{2})=M_{\text{outer}}.{\text{aug}}\_{\text{project}}(g',+_{\mathbb {Z} },m,x_{1},x_{2})}$
${\displaystyle {\text{where }}g':M_{\text{inner}}\mapsto \mathbb {Z} ,g'(m')=M_{\text{inner}}.{\text{aug}}\_{\text{range}}(m,y_{1},y_{2})}$

If both the inner and the outer maps are implemented by augmented trees, then the whole two-level map structure becomes a range tree structure. If the inner map is supported by the augmented tree structure, and the outer tree is supported as the prefix structure, then the algorithm becomes a sweepline algorithm.

Other examples[1][2] include segment queries, inverted index searching, rectangle queries, etc.