| dbo:abstract
|
- شجرة فنويك أو الشجرة الثنائية المفهرسة هي بنية معطيات يمكن فيها القيام بتعديل عنصر وحساب مجاميع البوادئ في جدول من القيم الحسابية بطريقة فعالة. اقترح بوريس ريابكو عام 1989 بنية المعطيات هذه، ثم أضاف إليها مجموعة من التنقيحات عام 1992، ولكنها حظيت بشهرة واسعة تحت اسم شجرة فنويك بعدما نشر بيتر فنويك شرحاً مفصلاً عنها في ورقة بحثية عام 1994. بالمقارنة مع مصفوفة أحادية البعد تستطيع شجرة فنويك الموازنة بين عملية تعديل العنصر وحساب مجاميع البودائ بطريقة أفضل. في مصفوفة أحادية البعد مكونة من عنصر يمكن تخزين العناصر أو مجاميع البوادئ وليس كلا القيمتين. في الحالة الأولى (تخزين العناصر) يستهلك حساب مجاميع البوادئ وقتاً خطياً ، وفي الحالة الثانية (تخزين مجاميع البوادئ) يستهلك تخزين عنصر ما في المصفوفة وقتاً خطياً، أي أنه في كلا الحالتين تستهلك إحدى العمليتين وقتاً خطياً. تسمح شجرة فنويك بالقيام بكلا العمليتين خلال وقت لوغارتمي . يتم ذلك من خلال تمثيل عناصر المصفوفة كبنية شجرية، في هذه البنية الشجرية تُخزن في كل عقدة مجموع عناصر عقد الشجرة المتفرعة منها. تسمح هذه البنية الشجرية بتنفيذ العمليات المذكورة أعلاه عن طريق زيارة عدد من العقد مقداره . (ar)
- A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. This structure was proposed by Boris Ryabko in 1989with a further modification published in 1992.It has subsequently become known under the name Fenwick tree after , who described this structure in his 1994 article. When compared with a flat array of numbers, the Fenwick tree achieves a much better balance between two operations: element update and prefix sum calculation. A flat array of numbers can either store the elements or the prefix sums. In the first case, computing prefix sums requires linear time; in the second case, updating the array elements requires linear time (in both cases, the other operation can be performed in constant time). Fenwick trees allow both operations to be performed in time. This is achieved by representing the numbers as a tree, where the value of each node in the tree is the prefix sum of the array from the index of the parent (inclusive) up to the index of the node (exclusive). The tree must therefore have one more node than the number of elements in the flat array representation. The tree structure allows the operations of element retrieval, element update, prefix sum, and range sum to be performed using only node accesses. (en)
- Un árbol binario indexado o árbol de Fenwick es una estructura de datos que proporciona métodos eficientes para el cálculo y la manipulación de las cantidades de prefijos de una array de valores.Fue propuesto por Boris Ryabko en 1989 con una modificación posterior publicada por el mismo autor en 1992.Luego volvió a ser conocida como árbol de Fenwik tras la publicación del artículo de en 1994. El Fenwick Tree principalmente resuelve el problema de equilibrar la eficiencia de la suma del prefijo con la eficiencia de modificar un elemento. La eficacia de estas operaciones se presenta como una solución de compromiso, (dado que una mayor eficiencia en el cálculo de la suma del prefijo se consigue precalculando los valores, pero una vez que los valores son precalculados, debe volverse a calcular cada vez que ocurra una modificación). Esto haría O(1) las consultas pero las modificaciones serían O(n). El Fenwick Tree hace ambas operaciones en O(log n), donde n es el tamaño del array. (es)
- フェニック木 または Binary Indexed Tree (BIT) とは、部分和の計算と要素の更新の両方を効率的に行える木構造である。1994年に算術符号化を用いた圧縮アルゴリズムの計算を効率化するためにピーター・フェニックにより提案された木構造である。 単なる数列として保存する場合と比較して、フェニック木は要素の更新と部分和の計算の両方をバランスよく行える。数列としてデータを保存する場合、 n 要素の数列には、要素そのものか、区間和を格納する手法が考えられる。要素そのものを格納した場合には、区間和を計算するために区間の長さに比例した時間がかかり、区間和を格納した場合には要素の更新に数列の長さに比例した時間がかかる（要素そのものを格納した場合には要素の更新は定数時間で可能であり、区間和を格納すれば区間和の計算は定数時間で可能である）。フェニック木は要素の更新と区間和の計算の両方を で可能とする構造である。具体的には、木構造のそれぞれのノードが持つ値を、そのノードの部分木の要素の和とすることで実現している。 (ja)
- 树状数组或二元索引树（英語：Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩裡的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和， 区间和。它可以以的时间得到任意前缀和，并同时支持在时间内支持动态单点值的修改。空间复杂度。 (zh)
- Дерево Фенвика (двоичное индексированное дерево, англ. Fenwick tree, binary indexed tree, BIT) — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Рябко Б.Я. в 1989 году. Полная версия опубликована им на английском в 1992 г. Через два года (в 1994 г.) появилась статья П. Фенвика , где была описана та же структура, впоследствии получившая название "дерево Фенвика". (ru)
- Дерево Фенвіка — це структура даних, дерево неявно втілене на масиві, що має такі властивості: 1.
* Дозволяє обчислювати значення деякої оборотної операції G на будь-якому відрізку [L; R] за час O(log N); 2.
* Дозволяє змінювати значення будь-якого елемента за O(log N); 3.
* Вимагає O(N) пам'яті, а точніше, рівно стільки ж, скільки і масив з N елементів; 4.
* Легко узагальнюється на випадок багатовимірних масивів. Структура даних нагадує дерево відрізків, однак простіша в реалізації. Найпоширеніше застосування дерева Фенвіка — обчислення суми на відрізку, тобто функція G (X1, …, Xk) = X1 + … + Xk. Дерево Фенвіка було вперше описано в статті «A new data structure for cumulative frequency tables» (Peter M. Fenwick, 1994). (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 14437 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:caption
|
- Creation of a binary indexed tree for the array [1, 2, 3, 4, 5] by elementwise insertion (en)
|
| dbp:inventedBy
| |
| dbp:inventedYear
| |
| dbp:name
|
- Binary indexed tree (en)
- Fenwick tree (en)
|
| dbp:type
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- フェニック木 または Binary Indexed Tree (BIT) とは、部分和の計算と要素の更新の両方を効率的に行える木構造である。1994年に算術符号化を用いた圧縮アルゴリズムの計算を効率化するためにピーター・フェニックにより提案された木構造である。 単なる数列として保存する場合と比較して、フェニック木は要素の更新と部分和の計算の両方をバランスよく行える。数列としてデータを保存する場合、 n 要素の数列には、要素そのものか、区間和を格納する手法が考えられる。要素そのものを格納した場合には、区間和を計算するために区間の長さに比例した時間がかかり、区間和を格納した場合には要素の更新に数列の長さに比例した時間がかかる（要素そのものを格納した場合には要素の更新は定数時間で可能であり、区間和を格納すれば区間和の計算は定数時間で可能である）。フェニック木は要素の更新と区間和の計算の両方を で可能とする構造である。具体的には、木構造のそれぞれのノードが持つ値を、そのノードの部分木の要素の和とすることで実現している。 (ja)
- 树状数组或二元索引树（英語：Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩裡的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和， 区间和。它可以以的时间得到任意前缀和，并同时支持在时间内支持动态单点值的修改。空间复杂度。 (zh)
- Дерево Фенвика (двоичное индексированное дерево, англ. Fenwick tree, binary indexed tree, BIT) — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Рябко Б.Я. в 1989 году. Полная версия опубликована им на английском в 1992 г. Через два года (в 1994 г.) появилась статья П. Фенвика , где была описана та же структура, впоследствии получившая название "дерево Фенвика". (ru)
- شجرة فنويك أو الشجرة الثنائية المفهرسة هي بنية معطيات يمكن فيها القيام بتعديل عنصر وحساب مجاميع البوادئ في جدول من القيم الحسابية بطريقة فعالة. اقترح بوريس ريابكو عام 1989 بنية المعطيات هذه، ثم أضاف إليها مجموعة من التنقيحات عام 1992، ولكنها حظيت بشهرة واسعة تحت اسم شجرة فنويك بعدما نشر بيتر فنويك شرحاً مفصلاً عنها في ورقة بحثية عام 1994. (ar)
- Un árbol binario indexado o árbol de Fenwick es una estructura de datos que proporciona métodos eficientes para el cálculo y la manipulación de las cantidades de prefijos de una array de valores.Fue propuesto por Boris Ryabko en 1989 con una modificación posterior publicada por el mismo autor en 1992.Luego volvió a ser conocida como árbol de Fenwik tras la publicación del artículo de en 1994. El Fenwick Tree principalmente resuelve el problema de equilibrar la eficiencia de la suma del prefijo con la eficiencia de modificar un elemento. La eficacia de estas operaciones se presenta como una solución de compromiso, (dado que una mayor eficiencia en el cálculo de la suma del prefijo se consigue precalculando los valores, pero una vez que los valores son precalculados, debe volverse a cal (es)
- A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. This structure was proposed by Boris Ryabko in 1989with a further modification published in 1992.It has subsequently become known under the name Fenwick tree after , who described this structure in his 1994 article. (en)
- Дерево Фенвіка — це структура даних, дерево неявно втілене на масиві, що має такі властивості: 1.
* Дозволяє обчислювати значення деякої оборотної операції G на будь-якому відрізку [L; R] за час O(log N); 2.
* Дозволяє змінювати значення будь-якого елемента за O(log N); 3.
* Вимагає O(N) пам'яті, а точніше, рівно стільки ж, скільки і масив з N елементів; 4.
* Легко узагальнюється на випадок багатовимірних масивів. Структура даних нагадує дерево відрізків, однак простіша в реалізації. (uk)
|
| rdfs:label
|
- شجرة فنويك (ar)
- Fenwick tree (en)
- Árbol binario indexado (es)
- フェニック木 (ja)
- Дерево Фенвика (ru)
- 树状数组 (zh)
- Дерево Фенвіка (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
