| dbo:abstract
|
- In computer science, the augmented map is an abstract data type (ADT) based on ordered maps, which associates each ordered map an augmented value. For an ordered map with key type , comparison function on and value type , the augmented value is defined based on two functions: a base function and a combine function , where is the type of the augmented value. The base function converts a single entry in to an augmented value, and the combine function combines multiple augmented values. The combine function is required to be associative and have an identity (i.e., forms a monoid). We extend the definition of the associative function as follows: Then the augmented value of an ordered map is defined as follows: Accordingly, an augmented map can be formally defined as a seven-tuple . For example, an augmented map with integral keys and values, on which the augmented value is defined as the sum of all values in the map, is defined as: As an abstract data type, the augmented map is often used to model problems and serves as an abstraction with a useful interface. It is designed for supporting fast range sums, which means to quickly return the augmented value of all entries in a certain key range. (en)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10040 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- In computer science, the augmented map is an abstract data type (ADT) based on ordered maps, which associates each ordered map an augmented value. For an ordered map with key type , comparison function on and value type , the augmented value is defined based on two functions: a base function and a combine function , where is the type of the augmented value. The base function converts a single entry in to an augmented value, and the combine function combines multiple augmented values. The combine function is required to be associative and have an identity (i.e., forms a monoid). We extend the definition of the associative function as follows: (en)
|
| rdfs:label
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
