The Augmented Map

The augmented map is developed for fast calculating the range sum in an ordered map. We define the augmented value AV(M) of a map M={m1, m2, ..., mn} as:

AV(M) = f(g(m1), g(m2), ..., g(mn))

where the binary function f is extended to zero, one, or multiple operants by:

f(∅) = I
f(a) = a
f(a1, a2, ..., an) = f(f(a1, ..., an-1), an)

Then the map can be used to quickly answer queries related to the abstract "sum" (augmented value) for all entries within a key range.

Declare a Data Type in PAM

To use PAM, users should include the header file:

#include "pam.h"

In PAM, users can use C++ templates to define a sequence, / ordered set / ordered map / augmented map. For example, defining an augmented map with integer keys and values, and augmented values taking the sum of all values can be done as follows:

struct entry {
    using key_t = int; // K (key type)
    using val_t = int; // V (value type)
    using aug_t = int; // A (augmented value)
    static inline bool comp(key_t a, key_t b) { return a < b;} // < (comparison function on K)
    static aug_t get_empty() { return 0;} // I(identity of f)
    static aug_t from_entry(key_t k, val_t v) { return v;} // g (base function)
    static aug_t combine(aug_t a, aug_t b) { return a+b;} // f (combine function)
};
aug_map<entry> a;

To declare other data types, just use a subset of parameters in an augmented map.

The default balancing scheme is the weight-balanced tree. Users can change to other balancing schemes by:

aug_map<entry, avl_tree>
aug_map<entry, red_black_tree>
aug_map<entry, treap>
      

Here is an example of some operations on two augmented maps:

#include <pam.h>

struct entry { 
    using key_t = int; // K (key type)
    using val_t = int; // V (value type)
    using aug_t = int; // A (augmented value)
    static inline bool comp(key_t a, key_t b) { return a < b;} // < (comparison function on K)
    static aug_t get_empty() { return 0;} // I(identity of f)
    static aug_t from_entry(key_t k, val_t v) { return v;} // g (base function)
    static aug_t combine(aug_t a, aug_t b) { return a+b;} // f (combine function)
};
using mtype = aug_map<entry>;
using ptype = std::pair<int, int>;

int main() {
    int[] a = {ptype(7, 12), ptype(30, 6), ptype(8, 1)};
    m_type m1(a1, a1+3);
    m_type m2;
    m2.insert(ptype(12, 4));
    m2.insert(ptype(2, 9));
    m_type m3 = mtype::map_union(m1, m2);
    std::cout << mtype::aug_range(m3, 5, 20) << endl;
}

The aug_range will output the sum of values in key range from 5 to 20, which will be 17.

Using the same augmented map type (mtype), we can maintain a collection of key-value pairs, and answer any query about the sum in a certain key range efficiently. In PAM, augmented maps are supported by augmented trees, and thus such query can be reported in O(log n) time for n entries in the augmented map.