Двоичное индексное дерево или дерево Фенвика — это мощная структура данных для решения проблем, связанных с обновлением диапазона/запросом диапазонаили точечным обновлением/запросом диапазонаили обновлением диапазона/запросом точки . Здесь мы обсудим это самым простым способом: P.

Сегодня мы обсудим самую простую форму точечного обновления/запроса диапазона двоичного индексного дерева.

Предположим, у вас есть проблема, когда вам дан массив, и над массивом будут выполняться два типа операций.

  1. Обновить значение @Array[index] = значение.
  2. Сумма всех элементов до index.

Предположим, что изначально все элементы входного массива A равны 0 (нулю). И индексирование массивов основано 1, т. е. индекс первого элемента равен 1, а не 0.

Итак, начнем …

  • Инициализация: создайте массив BIT[] размером, равным чуть большей степени числа 2, чем размер массива A, заполненный нулями.

Eg. A=[10,20,30,40,50] so size of BIT should be 8.

BIT = [0, 0, 0, 0, 0, 0, 0, 0]

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

Eg. suppose we are at index 5, so we will try to reach index 8 (Next power of 2), Using [2^0, 2^1, 2^2, 2^3, ...]

So, To reach 8 from 5, We'll use 2^0 and 2^1.

i.e 5(+2^0)->6(+2^1)->8

So update the new value at indices 5,6 and 8.

  • Сумма: Исходя из нашего алгоритма обновления, мы можем сказать, что BIT[2^n]=Sum of all elements of input array A till index=2^n.

Таким образом, этот процесс является обратным обновлению.

Здесь мы пытаемся уменьшить индекс, чтобы достичь меньшей степени двойки, используя степени двойки.

Eg. suppose we want get sum till index 7. So our target will be to reach 4, using [2^0,2^1,2^2,2^3,...].

7(-2^0)->6(-2^1)->4

So, our answer for the query will be BIT[7]+BIT[6]+BIT[4].

Я надеюсь, что теперь BIT немного понятнее :P. Чтобы красиво написать код для вышеуказанных операций, ждите следующего поста.