In the interface section we have already seen how to implement an augmented map that can quickly answer the sum of values in any key range efficiently. Next let's look at two more examples about using the augmented map interface.

1D Stabbing Query Using the Interval Tree

Given a set of intervals on number line, the stabbing query asks about if a certain point p is covered by any intervals in the input set.

The intervals can be effectively organized in an augmented map interface. This augmented map stores all intervals as entries, using the left endpoints as keys, and the right endpoints as values. The augmented value is defined as the maximum value (right endpoint) in the map.

Then a stabbing query on p is equivalent to ask: for all intervals with left enpoint smaller than p, is the maximum right endpoint larger than p? If so, then at least one interval covers p. Otherwise, no intervals get across p.

We then need to report the maximum right endpoint for all input intervals with left endpoint smaller than p. Since the augmented values maintain the maximum right endpoint in a map, this can be done directly by functions on the augmented map interface - The aug_left(k) function returns the augmented value of all entries smaller than a key k. We use this function to answer stabbing queries.

#include "pam.h"
using point = uint;

struct interval_map {  
  using interval = pair;

  struct entry {
    using key_t = point;
    using val_t = point;
    using aug_t = point;
    static inline bool comp(key_t a, key_t b) { return a < b;}
    static aug_t get_empty() { return 0;}
    static aug_t from_entry(key_t k, val_t v) { return v;}
    static aug_t combine(aug_t a, aug_t b) {
      return (a > b) ? a : b;}
  };

  using amap = aug_map;
  amap m;

  interval_map(interval* A, size_t n) {
    m = amap(A,A+n); }

  bool stab(point p) {
    return (m.aug_left(p) > p);}

  void insert(interval i) {m.insert(i);}
}

PAM uses augmented trees to support augmented maps, and thus this implementation inherently leads to an interval tree structure (as introduced in the textbook Introduction to Algorithms).

The complexity of this implementation is as follows:

Space: O(n)

2D Range Query Using the Range Trees

Next we look at a more involved example, the 2D range query, which uses a nested augmented map structure. The range query problem is to maintain a set of points, and to answer the number of points contained in a query rectangle.

The 2D range query can be answered using a two-level map structure RangeMap, each level corresponding to one dimension of the coordinates. For simplicity we assume there is no duplicates in coordinates. The key of the outer map is the x-coordinate of each point and the value is the y-coordinate. The augmented value of such an outer map, which is the inner map, contains the same set of points, but are sorted by y-coordinates, and augmented my the size of the map. Therefore, the base function of the outer map is just a singleton on the point and the combine function is a map_union.

To answer queries, we use two nested range searches (xL; xR) on the outer map and (yL; yR) on the corresponding inner map. We assume the outer map is defined as OM, and the inner map is defined as IM, then the counting query can be represented using the augmented map interface as:

RANGEQUERY(M; xL; xR; yL; yR) = MI::aug_range( MO::aug_range(M, xL, xR), yL, yR)

In practice, since the augmented map is maintained by tree structures. we do not need to explicitely genterate the augmetned value of the outer map. We can just add all augmented values of related inner maps on the way. In the outer range of x-coordinates, there are at most O(log n) such related inner trees. This can also be done by the function aug_project on the augmented map interface.

The construction code for such tree structure is as follows:

#include "pam.h"

template
struct RangeQuery {
  using point_type = Point;
  
  struct inner_map_t {
    using key_t = y_type
    using val_t = x_type;
    static bool comp(key_t a, key_t b) { return a < b;}
    using aug_t = int;
    inline static aug_t from_entry(key_t k, val_t v) { return 1; }
    inline static aug_t combine(aug_t a, aug_t b) { return a+b; }
    static aug_t get_empty() { return 0;}
  };
  using inner_map = aug_map;

  struct outer_map_t {
    using key_t = x_type;
    using val_t = y_type;
    static bool comp(key_t a, key_t b) { return a < b;}
    using aug_t = inner_map;
    inline static aug_t from_entry(key_t k, val_t v) {
      return aug_t(make_pair(v, k));
    }
    inline static aug_t combine(aug_t a, aug_t b) {
      return aug_t::map_union(a, b);
    }
    static aug_t get_empty() { return aug_t();}
  };
  using outer_map = aug_map;

  RangeQuery(vector& points) {
    const size_t n = points.size();
    range_tree = outer_map(points.begin(), points.end());    
  }

  ~RangeQuery() {
    outer_map::finish();
    inner_map::finish();
  }
  outer_map range_tree;
};

Here we only show the code for construction. The complete version of code is also provided in the library.

The complexity of this implementation is as follows:

Space: O(nlog(n))