| dbo:abstract
|
- En ciencias de la computación, un árbol de segmento (en inglés: Segment tree) es una estructura de datos en forma de árbol para guardar intervalos o segmentos. Permite consultar cuál de los segmentos guardados contiene un punto. Este es, en principio, una estructura estática; es decir, su contenido no puede ser modificado una vez que su estructura es construida. Una estructura de datos similar es el árbol de intervalo. Un árbol de segmento para un conjunto I de n intervalos usa O(n log n) de memoria de almacenamiento y puede construirse en un tiempo O(n log n). Los árboles de segmento soportan búsqueda para todos los intervalos que contienen un punto de consulta en O(log n + k), k el número de intervalos o segmentos recuperados. Algunas aplicaciones del árbol de segmento son vistas en las áreas de la geometría computacional y en los sistemas de información geográfica. El árbol de segmentos puede generalizarse para espacios multidimensionales. (es)
- In computer science, a segment tree, also known as a statistic tree, is a tree data structure used for storing information about intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, it's a structure that cannot be modified once it's built. A similar data structure is the interval tree. A segment tree for a set I of n intervals uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in time O(log n + k), k being the number of retrieved intervals or segments. Applications of the segment tree are in the areas of computational geometry, geographic information systems and machine learning. The segment tree can be generalized to higher dimension spaces. (en)
- En informatique, un arbre segment (en anglais segment tree), est un arbre enraciné pour stocker des intervalles ou des segments. Il permet des requêtes afin de savoir quels segments contiennent un certain point. C'est, en principe, une structure statique ; c'est une structure qui ne peut plus être modifiée une fois qu'elle est créée. Une structure de données similaire est l'arbre intervalle. Un arbre segment pour un ensemble I de n intervalles utilise un stockage de (n log n) et peut être construit en un temps de O(n log n). Dans un arbre segment on peut rechercher tous les intervalles qui contiennent un certain point (la requête) en O(log n + k), où k est le nombre d'intervalles ou segments extraits. Les applications de l'arbre segment sont dans les domaines de la géométrie algorithmique et du système d'information géographique. L'arbre segment peut aussi être généralisé à des espaces avec des plus grandes dimensions. (fr)
- Дерево отрезков — структура данных, позволяющая находить значение некоторой ассоциативной функции на произвольном отрезке массива за асимптотику . Наиболее часто в качестве берутся функции суммы, произведения, максимум и минимум. (ru)
- У інформатиці, дерево відрізків це деревоподібна структура даних яка застосовується для зберігання даних у відрізках, згрупованих так, що відомо, які з них містять дану точку. Дерево відрізків для множини з відрізків використовує пам'яті і його можна побудувати за часу. Дерево забезпечує виконання операції зі знаходження усіх відрізків, що містять задану точку за час де — кількість отриманих відрізків. Звернімо увагу, що для відповіді на запит про належність точки інтервалам із використанням потрібно так само часу за умови лінійної кількості пам'яті, отже для цього завдання краще обирати дерево інтервалів. Коли ж ми бажаємо отримати відповідь на складніші запитання як-от вікнування відрізків тоді дерево відрізків потужніша структура. Причиною цього є те, що множина інтервалів, що включають запитану точку, є саме об'єднанням канонічних підмножин які ми вибираємо під час пошуку у дереві. У дереві інтервалів ми повинні додатково пройти декілька елементів з початку відсортованих списків, що зберігаються у вузлах дерева. Отже, для дерева відрізків, ми маємо можливість збереження канонічних підмножин у асоціативній структурі, що дає можливість виконання додаткових запитів уже у цій структурі. (uk)
- 線段樹（英語：Segment tree）是一種二元樹形資料結構，1977年由Jon Louis Bentley發明，用以儲存區間或線段，並且允許快速查詢結構內包含某一點的所有區間。 一個包含個區間的線段樹，空間複雜度為，查詢的時間複雜度則為，其中是符合條件的區間數量。 此資料結構亦可推廣到高維度。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13259 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Дерево отрезков — структура данных, позволяющая находить значение некоторой ассоциативной функции на произвольном отрезке массива за асимптотику . Наиболее часто в качестве берутся функции суммы, произведения, максимум и минимум. (ru)
- 線段樹（英語：Segment tree）是一種二元樹形資料結構，1977年由Jon Louis Bentley發明，用以儲存區間或線段，並且允許快速查詢結構內包含某一點的所有區間。 一個包含個區間的線段樹，空間複雜度為，查詢的時間複雜度則為，其中是符合條件的區間數量。 此資料結構亦可推廣到高維度。 (zh)
- En ciencias de la computación, un árbol de segmento (en inglés: Segment tree) es una estructura de datos en forma de árbol para guardar intervalos o segmentos. Permite consultar cuál de los segmentos guardados contiene un punto. Este es, en principio, una estructura estática; es decir, su contenido no puede ser modificado una vez que su estructura es construida. Una estructura de datos similar es el árbol de intervalo. Algunas aplicaciones del árbol de segmento son vistas en las áreas de la geometría computacional y en los sistemas de información geográfica. (es)
- In computer science, a segment tree, also known as a statistic tree, is a tree data structure used for storing information about intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, it's a structure that cannot be modified once it's built. A similar data structure is the interval tree. Applications of the segment tree are in the areas of computational geometry, geographic information systems and machine learning. The segment tree can be generalized to higher dimension spaces. (en)
- En informatique, un arbre segment (en anglais segment tree), est un arbre enraciné pour stocker des intervalles ou des segments. Il permet des requêtes afin de savoir quels segments contiennent un certain point. C'est, en principe, une structure statique ; c'est une structure qui ne peut plus être modifiée une fois qu'elle est créée. Une structure de données similaire est l'arbre intervalle. Les applications de l'arbre segment sont dans les domaines de la géométrie algorithmique et du système d'information géographique. (fr)
- У інформатиці, дерево відрізків це деревоподібна структура даних яка застосовується для зберігання даних у відрізках, згрупованих так, що відомо, які з них містять дану точку. Дерево відрізків для множини з відрізків використовує пам'яті і його можна побудувати за часу. Дерево забезпечує виконання операції зі знаходження усіх відрізків, що містять задану точку за час де — кількість отриманих відрізків. (uk)
|
| rdfs:label
|
- Árbol de segmento (es)
- Arbre de segments (fr)
- Segment tree (en)
- Дерево отрезков (ru)
- Дерево відрізків (uk)
- 線段樹 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
