"Drzewo przedzia\u0142owe (ang. interval tree, range tree, drzewo zakresowe) \u2013 struktura danych przechowuj\u0105ca punkty, oraz zwi\u0105zane z tymi punktami wszystkie mo\u017Cliwe przedzia\u0142y. Drzewo przedzia\u0142owe, je\u015Bli jest skonstruowane tak, aby by\u0142o zr\u00F3wnowa\u017Cone, pozwala odpowiada\u0107 na zapytania o dowolny przedzia\u0142 w czasie logarytmicznym. Przyk\u0142adami zapyta\u0144 dla drzew przedzia\u0142owych mo\u017Ce by\u0107: Drzewo przedzia\u0142owe w celu odpowiedzi na takie pytania w czasie logarytmicznym, poza tym \u017Ce musi by\u0107 zr\u00F3wnowa\u017Cone, przechowuje dodatkowe informacje (tzw. informacje agreguj\u0105ce) w ka\u017Cdym w\u0119\u017Ale, opisuj\u0105ce ca\u0142e poddrzewo."@pl . . . . . "En ciencia de la computaci\u00F3n, un \u00E1rbol de intervalo es una para mantener intervalos. En concreto, permite encontrar de manera eficiente todos los intervalos que se solapan con cualquier otro intervalo o punto dado. A menudo se utiliza para las consultas de ventanas, por ejemplo, para encontrar todos los caminos en un mapa computarizado dentro de una ventana rectangular, o para encontrar todos los elementos visibles dentro de una escena tridimensional. Una estructura de datos similar es el \u00E1rbol de segmento."@es . . . "\u533A\u9593\u6728"@ja . "Interval tree"@en . . "1122891003"^^ . . "En ciencia de la computaci\u00F3n, un \u00E1rbol de intervalo es una para mantener intervalos. En concreto, permite encontrar de manera eficiente todos los intervalos que se solapan con cualquier otro intervalo o punto dado. A menudo se utiliza para las consultas de ventanas, por ejemplo, para encontrar todos los caminos en un mapa computarizado dentro de una ventana rectangular, o para encontrar todos los elementos visibles dentro de una escena tridimensional. Una estructura de datos similar es el \u00E1rbol de segmento. La soluci\u00F3n trivial es visitar cada intervalo y probar si se cruza el punto o intervalo dado, que requiere \u0398(n) tiempo, donde n es el n\u00FAmero de intervalos en la colecci\u00F3n. Dado que una consulta puede devolver todos los intervalos, por ejemplo, si la consulta es un gran intervalo de intersecci\u00F3n de todos los intervalos de la colecci\u00F3n, esto es ; Sin embargo, podemos mejorarlo al considerar , donde el tiempo de ejecuci\u00F3n se expresa en t\u00E9rminos de m, el n\u00FAmero de intervalos producidos por la consulta. Los \u00C1rboles de intervalo son din\u00E1micos, es decir, que permiten la inserci\u00F3n y la supresi\u00F3n de intervalos. Obtienen un tiempo de consulta de O(log n), mientras que el tiempo de preprocesamiento para construir la estructura de datos es O(n log n) (pero el consumo de espacio es O(n)). Si los puntos extremos de los intervalos est\u00E1n dentro de un rango entero peque\u00F1o (por ejemplo, en el intervalo [1, ..., O (n)]), las estructuras de datos m\u00E1s r\u00E1pidas existen con el tiempo de preprocesamiento O (n) y el tiempo de consulta O(1+m) para informar m intervalos que contienen un punto de consulta dada."@es . . "In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the segment tree."@en . . "Drzewo przedzia\u0142owe"@pl . "En informatique, un arbre intervalle (en anglais interval tree), est un arbre enracin\u00E9 pour stocker des intervalles. Particuli\u00E8rement, il permet de retrouver efficacement tous les intervalles qui chevauchent un certain intervalle ou point. Cette structure de donn\u00E9es est souvent[citation n\u00E9cessaire] utilis\u00E9e pour les requ\u00EAtes dites de fen\u00EAtres, par exemple, pour trouver toutes les routes dans un espace rectangulaire sur une carte num\u00E9rique, ou pour trouver tous les \u00E9l\u00E9ments visibles dans un espace \u00E0 3 dimensions. Une structure de donn\u00E9es similaire est l'arbre segment."@fr . . . . . . . . . . . . "1533767"^^ . . . . . . . . . . . . . . . . . . . "23942"^^ . "\u533A\u9593\u6728\u307E\u305F\u306F\u30A4\u30F3\u30BF\u30FC\u30D0\u30EB\u6728\uFF08\u82F1: Interval tree\uFF09\u306F\u3001\u533A\u9593\u3092\u4FDD\u6301\u3059\u308B\u305F\u3081\u306E\u6728\u69CB\u9020\u306E\u30C7\u30FC\u30BF\u69CB\u9020\u306E\u4E00\u7A2E\u3002\u8A08\u7B97\u5E7E\u4F55\u5B66\u306E\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u3002\u7279\u306B\u3001\u6307\u5B9A\u3055\u308C\u305F\u533A\u9593\u3084\u70B9\u306B\u30AA\u30FC\u30D0\u30FC\u30E9\u30C3\u30D7\u3059\u308B\u5168\u3066\u306E\u533A\u9593\u3092\u63A2\u3059\u3068\u3044\u3046\u554F\u984C\u3092\u52B9\u7387\u7684\u306B\u89E3\u304F\u3053\u3068\u304C\u3067\u304D\u308B\u3002\u4F8B\u3048\u3070\u3001\u8868\u793A\u3055\u308C\u3066\u3044\u308B\u5730\u56F3\u5185\u306B\u898B\u3048\u3066\u3044\u308B\u5168\u3066\u306E\u9053\u8DEF\u3092\u6C42\u3081\u308B\u3068\u304B\u30013\u6B21\u5143\u306E\u30B7\u30FC\u30F3\u3067\u898B\u3048\u3066\u3044\u308B\u5168\u3066\u306E\u30AA\u30D6\u30B8\u30A7\u30AF\u30C8\u3092\u6C42\u3081\u308B\u3068\u3044\u3063\u305F\u7528\u9014\u306B\u4F7F\u308F\u308C\u308B\u3002\u4F3C\u305F\u3082\u306E\u306B\u533A\u5206\u6728\uFF08\u82F1: Segment tree, segtree\uFF09\u304C\u3042\u308B\u304C\u5225\u7269\u3067\u3042\u308B\u3002"@ja . . "\u00C1rbol de intervalo"@es . "\u533A\u9593\u6728\u307E\u305F\u306F\u30A4\u30F3\u30BF\u30FC\u30D0\u30EB\u6728\uFF08\u82F1: Interval tree\uFF09\u306F\u3001\u533A\u9593\u3092\u4FDD\u6301\u3059\u308B\u305F\u3081\u306E\u6728\u69CB\u9020\u306E\u30C7\u30FC\u30BF\u69CB\u9020\u306E\u4E00\u7A2E\u3002\u8A08\u7B97\u5E7E\u4F55\u5B66\u306E\u30A2\u30EB\u30B4\u30EA\u30BA\u30E0\u3002\u7279\u306B\u3001\u6307\u5B9A\u3055\u308C\u305F\u533A\u9593\u3084\u70B9\u306B\u30AA\u30FC\u30D0\u30FC\u30E9\u30C3\u30D7\u3059\u308B\u5168\u3066\u306E\u533A\u9593\u3092\u63A2\u3059\u3068\u3044\u3046\u554F\u984C\u3092\u52B9\u7387\u7684\u306B\u89E3\u304F\u3053\u3068\u304C\u3067\u304D\u308B\u3002\u4F8B\u3048\u3070\u3001\u8868\u793A\u3055\u308C\u3066\u3044\u308B\u5730\u56F3\u5185\u306B\u898B\u3048\u3066\u3044\u308B\u5168\u3066\u306E\u9053\u8DEF\u3092\u6C42\u3081\u308B\u3068\u304B\u30013\u6B21\u5143\u306E\u30B7\u30FC\u30F3\u3067\u898B\u3048\u3066\u3044\u308B\u5168\u3066\u306E\u30AA\u30D6\u30B8\u30A7\u30AF\u30C8\u3092\u6C42\u3081\u308B\u3068\u3044\u3063\u305F\u7528\u9014\u306B\u4F7F\u308F\u308C\u308B\u3002\u4F3C\u305F\u3082\u306E\u306B\u533A\u5206\u6728\uFF08\u82F1: Segment tree, segtree\uFF09\u304C\u3042\u308B\u304C\u5225\u7269\u3067\u3042\u308B\u3002"@ja . . "Arbre d'intervalles"@fr . . . . . . "In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the segment tree. The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires time, where is the number of intervals in the collection. Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is asymptotically optimal; however, we can do better by considering output-sensitive algorithms, where the runtime is expressed in terms of , the number of intervals produced by the query. Interval trees have a query time of and an initial creation time of , while limiting memory consumption to . After creation, interval trees may be dynamic, allowing efficient insertion and deletion of an interval in time. If the endpoints of intervals are within a small integer range (e.g., in the range ), faster and in fact optimal data structures exist with preprocessing time and query time for reporting intervals containing a given query point (see for a very simple one)."@en . "En informatique, un arbre intervalle (en anglais interval tree), est un arbre enracin\u00E9 pour stocker des intervalles. Particuli\u00E8rement, il permet de retrouver efficacement tous les intervalles qui chevauchent un certain intervalle ou point. Cette structure de donn\u00E9es est souvent[citation n\u00E9cessaire] utilis\u00E9e pour les requ\u00EAtes dites de fen\u00EAtres, par exemple, pour trouver toutes les routes dans un espace rectangulaire sur une carte num\u00E9rique, ou pour trouver tous les \u00E9l\u00E9ments visibles dans un espace \u00E0 3 dimensions. Une structure de donn\u00E9es similaire est l'arbre segment. Une solution triviale est de visiter chaque intervalle et de tester s'il intersecte le point ou intervalle donn\u00E9, cela requiert un temps O(n), o\u00F9 n est le nombre d'intervalles dans l'ensemble. Etant donn\u00E9 qu'une requ\u00EAte doit retourner tous les intervalles, par exemple si la requ\u00EAte est un large intervalle intersectant tous les intervalles de l'ensemble, cela est asymptotiquement optimal. Cependant on peut faire mieux en consid\u00E9rant les algorithmes qui d\u00E9pendent de la taille de l'entr\u00E9e, o\u00F9 le temps d\u2019ex\u00E9cution est exprim\u00E9 en fonction de m, le nombre d'intervalles produits par la requ\u00EAte. Les arbres intervalle ont un temps de requ\u00EAte en O(log n + m) et un temps initial de cr\u00E9ation en O(n log n), en limitant la consommation de la m\u00E9moire \u00E0 O(n). Apr\u00E8s la cr\u00E9ation, les arbres intervalle peuvent \u00EAtre dynamiques, permettant une efficace insertion et suppression d'un intervalle en O(log n). Si les points d'extr\u00E9mit\u00E9s sont dans une petite plage d'entiers (e.g., dans la plage [1,...,O(n)]), des structures de donn\u00E9es plus rapides existent avec un temps de pr\u00E9traitement de O(n) et un temps de requ\u00EAte de O(1+m) pour signaler m intervalles contenant a un certain point d'une requ\u00EAte[r\u00E9f. n\u00E9cessaire]."@fr . . . . . . . "Drzewo przedzia\u0142owe (ang. interval tree, range tree, drzewo zakresowe) \u2013 struktura danych przechowuj\u0105ca punkty, oraz zwi\u0105zane z tymi punktami wszystkie mo\u017Cliwe przedzia\u0142y. Drzewo przedzia\u0142owe, je\u015Bli jest skonstruowane tak, aby by\u0142o zr\u00F3wnowa\u017Cone, pozwala odpowiada\u0107 na zapytania o dowolny przedzia\u0142 w czasie logarytmicznym. Przyk\u0142adami zapyta\u0144 dla drzew przedzia\u0142owych mo\u017Ce by\u0107: \n* ile jest kluczy w zbiorze wi\u0119kszych ni\u017C \"Cava\" i przy tym mniejszych ni\u017C \"Kofa\"? \n* jaka jest najwi\u0119ksza warto\u015B\u0107 pomi\u0119dzy 400 a 500 pozycj\u0105? \n* jakie jest odchylenie standardowe warto\u015Bci kt\u00F3re odpowiadaj\u0105 kluczom z zakresu od \"F2a\" do \"I3\"? \n* czy r\u00F3\u017Cnica liczby element\u00F3w parzystych i nieparzystych pomi\u0119dzy pozycj\u0105 214314 a 219131 jest parzysta? Drzewo przedzia\u0142owe w celu odpowiedzi na takie pytania w czasie logarytmicznym, poza tym \u017Ce musi by\u0107 zr\u00F3wnowa\u017Cone, przechowuje dodatkowe informacje (tzw. informacje agreguj\u0105ce) w ka\u017Cdym w\u0119\u017Ale, opisuj\u0105ce ca\u0142e poddrzewo. \n* W pierwszym przypadku jest to liczba kluczy w poddrzewie, \n* w drugim jest to warto\u015B\u0107 maksymalna w poddrzewie, \n* w trzecim mog\u0105 to by\u0107 3 pierwsze momenty (na podstawie kt\u00F3rych da si\u0119 wyliczy\u0107 odchylenie standardowe) lub ilo\u015B\u0107, \u015Brednia oraz odchylenie standardowe w danym poddrzewie, \n* w czwartym przypadku odpowied\u017A na pytanie dla ka\u017Cdego poddrzewa. W najcz\u0119stszym przypadku binarnych drzew przedzia\u0142owych, dane przechowywane w ka\u017Cdym w\u0119\u017Ale powinny by\u0107 mo\u017Cliwe do obliczenia tylko na podstawie analogicznych danych dla lewego i prawego poddrzewa, poprzez redukcj\u0119, bez potrzeby rekursji w g\u0142\u0105b drzewa. \n* W pierwszym przypadku liczba kluczy w poddrzewie, to liczba kluczy w lewym poddrzewie + liczba kluczy w prawym poddrzewie, \n* w drugim przypadku maksimum w poddrzewie to maksimum z maksimum w lewym i prawym poddrzewie, \n* w trzecim przypadku momenty to sumy moment\u00F3w z lewego i prawego poddrzewa, \n* w czwartym przypadku, wystarczy dokona\u0107 operacji alternatywy wykluczaj\u0105cej. Drzewa przedzia\u0142owe mog\u0105 zosta\u0107 uog\u00F3lnione na przestrzenie wielowymiarowe, i np. odpowiada\u0107 szybko na pytania typu \"Ile jest dom\u00F3w w prostok\u0105cie o wierzcho\u0142kach odpowiednio w Gda\u0144sku i Krakowie?\" Drzewa przedzia\u0142owe mog\u0105 r\u00F3wnie\u017C by\u0107 oparte na strukturach innych ni\u017C drzewa binarne. W systemach bazodanowych stosuje zwykle si\u0119 B-drzewa. W przypadku usuni\u0119cia, dodania, lub zmiany w\u0119z\u0142a w drzewie przedzia\u0142owym, nale\u017Cy przeprowadzi\u0107 aktualizacje danych dodatkowych na \u015Bcie\u017Cce do tego w\u0119z\u0142a. Analogiczn\u0105 procedur\u0119 trzeba zastosowa\u0107 w przypadku wywa\u017Cania, poniewa\u017C struktura drzewa, jak i to na co wskazuj\u0105 dane dodatkowe mo\u017Ce si\u0119 zmieni\u0107 (np. w przypadku rotacji). Binarne drzewa przedzia\u0142owe, s\u0105 binarnym drzewami poszukiwa\u0144 rozszerzonymi o dodatkow\u0105 funkcjonalno\u015B\u0107. W wielu zastosowaniach, w drzewach przedzia\u0142owych warto\u015Bci przechowuje si\u0119 tylko w li\u015Bciach, natomiast w w\u0119z\u0142ach wewn\u0119trznych (nie li\u015Bciach), przechowuje si\u0119 tylko informacje agreguj\u0105ce."@pl . . .