Одномерное дерево Фенвика — различия между версиями

Материал из Public ATP Wiki
Перейти к: навигация, поиск
(Новая страница: «''Задача:'' Есть массив a<sub>0</sub> ... a<sub>n-1</sub>, хотим поддерживать операции: # '''upd''' (update) в одно…»)
 
 
(не показана 1 промежуточная версия этого же участника)
Строка 12: Строка 12:
  
 
* использует ''O(n)'' дополнительной памяти
 
* использует ''O(n)'' дополнительной памяти
 
  
 
* легко обобщается на случай многомерных массивов.
 
* легко обобщается на случай многомерных массивов.
 
  
 
=== Описание ===
 
=== Описание ===

Текущая версия на 13:32, 4 апреля 2020

Задача: Есть массив a0 ... an-1, хотим поддерживать операции:

  1. upd (update) в одной точке
    apos += val
  2. сумма на отрезке
al + ... + ar – ?

Дерево Фенвика

Дерево Фенвика (англ. Binary Indexed Tree, BIT) – это структура данных, дерево на массиве, обладающее следующими свойствами:

  • позволяет вычислять сумму на отрезке [l; r] за время O(log n)
  • позволяет изменять значение любого элемента за O(log n)
  • использует O(n) дополнительной памяти
  • легко обобщается на случай многомерных массивов.

Описание