| dbo:abstract |
Range Minimum Queries (RMQs) adressieren innerhalb der Informatik das Problem, eine Anfrage nach dem kleinsten Element innerhalb eines spezifizierten Bereichs eines Arrays zu beantworten. Eine effiziente Beantwortung hat Relevanz für weitere Probleme der Informatik, wie z. B. für die Textindizierung und -kompression, Flussgraphen etc. (de) In computer science, a range minimum query (RMQ) solves the problem of finding the minimal value in a sub-array of an array of comparable objects. Range minimum queries have several use cases in computer science, such as the lowest common ancestor problem and the longest common prefix problem (LCP). (en) 范围最值查询（英語：Range Minimum Query），是针对数据集的一种条件查询。若给定一个数组，范围最值查询指定一个范围条件到，要求取出中最大／小的元素。 若，条件为的范围最值查询返回1，它是子数组中最小的元素。 通常情况下，数组A是静态的，即元素不会变化，例如插入、删除和修改等，而所有的查询是以在线的方式给出的，即预先并不知道所有查询的参数。 RMQ问题有预处理之后每次查询的算法。 范围最值查询问题（RMQ）与最近公共祖先（LCA）问题有直接联系，它们可以互相转化。RMQ的算法常常应用在严格或者近似子串匹配等问题的处理中。 (zh) |
| dbo:thumbnail |
wiki-commons:Special:FilePath/LowesCommon-fixed.png?width=300 |
| dbo:wikiPageExternalLink |
http://www.dtic.mil/get-tr-doc/pdf%3FAD=ADA227803%7C https://web.archive.org/web/20170923151711/http:/www.dtic.mil/get-tr-doc/pdf%3FAD=ADA227803%7C http://wcipeg.com/wiki/RMQ http://www.topcoder.com/tc%3Fmodule=Static&d1=tutorials&d2=lowestCommonAncestor%23Range_Minimum_Query_%28RMQ%29 https://web.stanford.edu/class/archive/cs/cs166/cs166.1146/lectures/00/Small00.pdf |
| dbo:wikiPageID |
21332467 (xsd:integer) |
| dbo:wikiPageLength |
13729 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1111750296 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbc:Search_algorithms dbr:Range_query_(data_structures) dbr:Lowest_common_ancestor dbr:Total_order dbr:Tree_traversal dbr:Dynamic_programming dbr:Graph_isomorphism dbr:LCP_array dbr:Cartesian_tree dbr:Catalan_number dbr:String_matching dbr:File:Example_of_Cartesian_Trees.png dbr:File:LowesCommon-fixed.png |
| dbp:wikiPageUsesTemplate |
dbt:= dbt:Cite_journal dbt:Cite_report dbt:Math dbt:Mvar dbt:R dbt:Reflist dbt:Rp dbt:Sdash dbt:Sfrac dbt:Short_description dbt:Sub dbt:Sup dbt:Val dbt:Mathcal |
| dct:subject |
dbc:Search_algorithms |
| rdf:type |
yago:WikicatSearchAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms |
| rdfs:comment |
Range Minimum Queries (RMQs) adressieren innerhalb der Informatik das Problem, eine Anfrage nach dem kleinsten Element innerhalb eines spezifizierten Bereichs eines Arrays zu beantworten. Eine effiziente Beantwortung hat Relevanz für weitere Probleme der Informatik, wie z. B. für die Textindizierung und -kompression, Flussgraphen etc. (de) In computer science, a range minimum query (RMQ) solves the problem of finding the minimal value in a sub-array of an array of comparable objects. Range minimum queries have several use cases in computer science, such as the lowest common ancestor problem and the longest common prefix problem (LCP). (en) 范围最值查询（英語：Range Minimum Query），是针对数据集的一种条件查询。若给定一个数组，范围最值查询指定一个范围条件到，要求取出中最大／小的元素。 若，条件为的范围最值查询返回1，它是子数组中最小的元素。 通常情况下，数组A是静态的，即元素不会变化，例如插入、删除和修改等，而所有的查询是以在线的方式给出的，即预先并不知道所有查询的参数。 RMQ问题有预处理之后每次查询的算法。 范围最值查询问题（RMQ）与最近公共祖先（LCA）问题有直接联系，它们可以互相转化。RMQ的算法常常应用在严格或者近似子串匹配等问题的处理中。 (zh) |
| rdfs:label |
Range Minimum Query (de) Range minimum query (en) 范围最值查询 (zh) |
| owl:sameAs |
freebase:Range minimum query yago-res:Range minimum query wikidata:Range minimum query dbpedia-de:Range minimum query dbpedia-fa:Range minimum query dbpedia-zh:Range minimum query https://global.dbpedia.org/id/22awK |
| prov:wasDerivedFrom |
wikipedia-en:Range_minimum_query?oldid=1111750296&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/Example_of_Cartesian_Trees.png wiki-commons:Special:FilePath/LowesCommon-fixed.png |
| foaf:isPrimaryTopicOf |
wikipedia-en:Range_minimum_query |
| is dbo:wikiPageDisambiguates of |
dbr:RMQ |
| is dbo:wikiPageRedirects of |
dbr:Range_Minimum_Query dbr:Range_min_query |
| is dbo:wikiPageWikiLink of |
dbr:Lowest_common_ancestor dbr:RMQ dbr:Range_Minimum_Query dbr:Range_min_query |
| is foaf:primaryTopic of |
wikipedia-en:Range_minimum_query |
