Для установки нажмите кнопочку Установить расширение. И это всё.

Исходный код расширения WIKI 2 регулярно проверяется специалистами Mozilla Foundation, Google и Apple. Вы также можете это сделать в любой момент.

4,5
Келли Слэйтон
Мои поздравления с отличным проектом... что за великолепная идея!
Александр Григорьевский
Я использую WIKI 2 каждый день
и почти забыл как выглядит оригинальная Википедия.
Статистика
На русском, статей
Улучшено за 24 ч.
Добавлено за 24 ч.
Что мы делаем. Каждая страница проходит через несколько сотен совершенствующих техник. Совершенно та же Википедия. Только лучше.
.
Лео
Ньютон
Яркие
Мягкие

Из Википедии — свободной энциклопедии

Дерево Фенвика (двоичное индексированное дерево, англ. Fenwick tree, binary indexed tree, BIT) — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Рябко Б.Я. в 1989 году. [1] Полная версия опубликована им на английском в 1992 г. [2]

Через два года (в 1994 г.) появилась статья П. Фенвика [3], где была описана та же структура, впоследствии получившая название "дерево Фенвика".

Дерево Фенвика для суммы

Будем обозначать для натурального числа максимальный делитель , являющийся степенью двойки (единицу мы также считаем степенью двойки). Нетрудно убедиться, что F(n)=n−(n & (n−1)), где & — побитовое «И» двух целых чисел. Пусть наш массив имеет элементов: . Выберем , при котором . Тогда для хранения дерева Фенвика понадобится массив из элементов. Будем нумеровать их от 1 до . В ячейке будет храниться сумма в ячейках массива с по .

Дерево Фенвика для суммы поддерживает 2 операции:

1) modify с аргументами и  — изменить значение -й ячейки массива на число ( может быть как положительно, так и отрицательно).

2) count с аргументом  — найти сумму чисел в ячейках массива с 1-й по -ю.

Обе операции могут быть легко реализованы одним циклом.

modify (N,X)

1) i=N
2) Пока i≤
2.1)    Увеличиваем b[i] на X
2.2)    Увеличиваем i на F(i)


count (N)

1)   res=0

2)   i=N

3)   Пока

3.1)   Увеличиваем res на b[i]

3.2)   Уменьшаем i на F(i)

4)   Ответ = res

Сложность обеих операций составляет O(k) = O(log n). Стоит отметить, что с помощью операции count(N) мы, вообще говоря, можем найти сумму на любом отрезке за ту же сложность, поскольку при ≠1 она в точности равняется .

Дерево Фенвика для максимума

Дерево Фенвика для максимума поддерживает следующие операции:

1) modify с аргументами и  — если значение в -й ячейке массива меньше , то записать в неё число . В противном случае оставить значение старым.

2) count с аргументами и  — найти максимум чисел в ячейках массива с -й по -ю.

Для хранения дерева, кроме массива , будем использовать массивы и . В -й ячейке массива будем хранить максимум на отрезке ; в -й ячейке массива  — максимум на отрезке при и на отрезке при .

Ниже приведена реализация операций.

modify (N,X)

1)a[N]=max(a[N],X)

2)i=N

3)Пока

3.1)left[i]=max(left[i],X)

3.2)Увеличиваем i на F(i)

4)j=N

5)Пока

5.1)right[j]=max(right[j],X)

5.2)Уменьшаем j на F(j)

count (L,R)

1)res=0

2)i=L

3)Пока

3.1)res=max(res,right[i])

3.2)Увеличиваем i на F(i)

4)res=max(res,a[i])

5)j=R

6)Пока

6.1)res=max(res,left[j])

6.2)Уменьшаем j на F(j)

7)Ответ = res

Сложность операций = .

Заметим, что с помощью дерева Фенвика для максимума нельзя уменьшить значение, записанное в ячейке. Если требуется, чтобы структура данных имела такую возможность, следует использовать дерево отрезков для максимума.

Операции могут быть легко модифицированы, чтобы дерево Фенвика находило не только значение максимума, но и ячейку, в которой этот максимум достигается.

Примечания

  1. Boris Ryabko. Быстрый последовательный код. // Доклады АН СССР : журнал. — 1989. — Т. 306, № 3. — С. 548—552.
  2. Boris Ryabko. A fast on-line adaptive code (англ.) // IEEE Trans.on Inform.Theory. — 1992. — Vol. 28, no. 1. — P. 1400—1404.
  3. Peter M. Fenwick. A new data structure for cumulative frequency tables (англ.) // Software: Practice and Experience : journal. — 1994. — Vol. 24, no. 3. — P. 327—336. — doi:10.1002/spe.4380240306.

Ссылки

Эта страница в последний раз была отредактирована 6 июля 2020 в 20:24.
Как только страница обновилась в Википедии она обновляется в Вики 2.
Обычно почти сразу, изредка в течении часа.
Основа этой страницы находится в Википедии. Текст доступен по лицензии CC BY-SA 3.0 Unported License. Нетекстовые медиаданные доступны под собственными лицензиями. Wikipedia® — зарегистрированный товарный знак организации Wikimedia Foundation, Inc. WIKI 2 является независимой компанией и не аффилирована с Фондом Викимедиа (Wikimedia Foundation).