Рубрики

Двоичное индексированное дерево или дерево Фенвика

Давайте рассмотрим следующую проблему, чтобы понять двоичное индексированное дерево.

У нас есть массив arr [0. , , н-1]. Мы хотели бы
1 Вычислите сумму первых элементов i.
2 Измените значение указанного элемента массива arr [i] = x, где 0 <= i <= n-1.

Простое решение — запустить цикл от 0 до i-1 и вычислить сумму элементов. Чтобы обновить значение, просто сделайте arr [i] = x. Первая операция занимает время O (n), а вторая операция занимает время O (1). Другое простое решение — создать дополнительный массив и сохранить сумму первых i-тых элементов по i-му индексу в этом новом массиве. Сумма заданного диапазона теперь может быть вычислена за время O (1), но операция обновления теперь занимает время O (n). Это хорошо работает, если имеется большое количество операций запроса, но очень мало операций обновления.

Можем ли мы выполнить операции запроса и обновления за O (log n)?
Одним из эффективных решений является использование дерева сегментов, которое выполняет обе операции за время O (Logn).

Альтернативным решением является двоичное индексированное дерево, которое также обеспечивает временную сложность O (Logn) для обеих операций. По сравнению с сегментным деревом, двоичное индексированное дерево требует меньше места и его легче реализовать. ,

Представление
Двоичное индексированное дерево представляется в виде массива. Пусть массив будет BITree []. Каждый узел двоичного индексированного дерева хранит сумму некоторых элементов входного массива. Размер двоичного индексированного дерева равен размеру входного массива, обозначенного как n. В приведенном ниже коде мы используем размер n + 1 для простоты реализации.

строительство
Мы инициализируем все значения в BITree [] как 0. Затем мы вызываем update () для всех индексов, операция update () обсуждается ниже.

операции

getSum(x): Returns the sum of the sub-array arr[0,...,x]
// Returns the sum of the sub-array arr[0,...,x] using BITree[0..n], which is constructed from arr[0..n-1]
1) Initialize the output sum as 0, the current index as x+1.
2) Do following while the current index is greater than 0.
...a) Add BITree[index] to sum
...b) Go to the parent of BITree[index].  The parent can be obtained by removing
     the last set bit from the current index, i.e., index = index - (index & (-index))
3) Return sum.

Диаграмма выше предоставляет пример того, как работает getSum (). Вот несколько важных замечаний.

BITree [0] является фиктивным узлом.

BITree [y] является родителем BITree [x], если и только если y можно получить, удалив последний установленный бит из двоичного представления x, то есть y = x — (x & (-x)).

Дочерний узел BITree [x] узла BITree [y] хранит сумму элементов от y (включительно) до x (исключая): arr [y,…, x).


update(x, val): Updates the Binary Indexed Tree (BIT) by performing arr[index] += val
// Note that the update(x, val) operation will not change arr[].  It only makes changes to BITree[]
1) Initialize the current index as x+1.
2) Do the following while the current index is smaller than or equal to n.
...a) Add the val to BITree[index]
...b) Go to parent of BITree[index].  The parent can be obtained by incrementing
     the last set bit of the current index, i.e., index = index + (index & (-index))

Функция обновления должна убедиться, что все узлы BITree, которые содержат arr [i] в своих диапазонах, обновляются. Мы перебираем такие узлы в BITree, многократно добавляя десятичное число, соответствующее последнему установленному биту текущего индекса.

Как работает двоичное индексированное дерево?
Идея основана на том факте, что все положительные целые числа могут быть представлены как сумма степеней 2. Например, 19 может быть представлен как 16 + 2 + 1. Каждый узел BITree хранит сумму из n элементов, где n является степень 2. Например, в первой диаграмме выше (диаграмма для getSum ()), сумма первых 12 элементов может быть получена суммой последних 4 элементов (от 9 до 12) плюс сумма 8 элементы (от 1 до 8). Количество установленных битов в двоичном представлении числа n равно O (Logn). Поэтому мы пересекаем не более O (Logn) узлов в операциях getSum () и update (). Временная сложность конструкции равна O (nLogn), так как она вызывает update () для всех n элементов.

Реализация:
Ниже приведены реализации двоичного индексированного дерева.

C ++

// C ++ код для демонстрации операций дерева двоичных индексов
#include <iostream>

  

using namespace std;

  
/ * n -> Количество элементов, присутствующих во входном массиве.

    BITree [0..n] -> Массив, представляющий двоичное индексированное дерево.

    arr [0..n-1] -> входной массив, для которого вычисляется сумма префикса. * /

  
// Возвращает сумму arr [0..index]. Эта функция предполагает
// что массив предварительно обработан и частичные суммы
// элементы массива хранятся в BITree [].

int getSum(int BITree[], int index)

{

    int sum = 0; // Инициализируем результат

  

    // индекс в BITree [] на 1 больше, чем индекс в arr []

    index = index + 1;

  

    // Пройдемся по предкам BITree [index]

    while (index>0)

    {

        // Добавить текущий элемент BITree к сумме

        sum += BITree[index];

  

        // Переместить индекс на родительский узел в представлении getSum

        index -= index & (-index);

    }

    return sum;

}

  
// Обновляет узел в дереве двоичных индексов (BITree) по указанному индексу
// в BITree. Заданное значение 'val' добавляется в BITree [i] и
// все его предки в дереве.

void updateBIT(int BITree[], int n, int index, int val)

{

    // индекс в BITree [] на 1 больше, чем индекс в arr []

    index = index + 1;

  

    // Обходим всех предков и добавляем 'val'

    while (index <= n)

    {

    // Добавить 'val' к текущему узлу дерева BI

    BITree[index] += val;

  

    // Обновить индекс до родительского в обновлении View

    index += index & (-index);

    }

}

  
// Создает и возвращает двоичное индексированное дерево для заданного
// массив размером n.

int *constructBITree(int arr[], int n)

{

    // Создать и инициализировать BITree [] как 0

    int *BITree = new int[n+1];

    for (int i=1; i<=n; i++)

        BITree[i] = 0;

  

    // Сохраняем фактические значения в BITree [] используя update ()

    for (int i=0; i<n; i++)

        updateBIT(BITree, n, i, arr[i]);

  

    // Раскомментируем строки ниже, чтобы увидеть содержимое BITree []

    // for (int i = 1; i <= n; i ++)

    // cout << BITree [i] << "";

  

    return BITree;

}

  

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int freq[] = {2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9};

    int n = sizeof(freq)/sizeof(freq[0]);

    int *BITree = constructBITree(freq, n);

    cout << "Sum of elements in arr[0..5] is "

        << getSum(BITree, 5);

  

    // Позвольте использовать тестирование операции обновления

    freq[3] += 6;

    updateBIT(BITree, n, 3, 6); // Обновить BIT для указанного выше изменения в arr []

  

    cout << "\nSum of elements in arr[0..5] after update is "

        << getSum(BITree, 5);

  

    return 0;

}

Джава

// Java-программа для демонстрации ленивых
// распространение в дереве сегментов

import java.util.*;

import java.lang.*;

import java.io.*;

  

class BinaryIndexedTree

    // Максимальный размер дерева

    final static int MAX = 1000;     

  

    static int BITree[] = new int[MAX];

      

    / * n -> Количество элементов, присутствующих во входном массиве.

    BITree [0..n] -> Массив, представляющий двоичный файл

                    Индексированное дерево.

    arr [0..n-1] -> входной массив, для которого сумма префикса

                    оценивается. * /

  

    // Возвращает сумму arr [0..index]. Эта функция

    // предполагается, что массив предварительно обработан и

    // сохранены частичные суммы элементов массива

    // в BITree [].

    int getSum(int index)

    {

        int sum = 0; // Инициализируем результат

      

        // индекс в BITree [] на 1 больше

        // индекс в arr []

        index = index + 1;

      

        // Пройдемся по предкам BITree [index]

        while(index>0)

        {

            // Добавить текущий элемент BITree

            // подвести

            sum += BITree[index];

      

            // Переместить индекс в родительский узел в

            // getSum View

            index -= index & (-index);

        }

        return sum;

    }

  

    // Обновляет узел в дереве двоичных индексов (BITree)

    // по заданному индексу в BITree. Данное значение

    // 'val' добавляется в BITree [i] и все

    // его предки в дереве.

    public static void updateBIT(int n, int index, 

                                        int val)

    {

        // индекс в BITree [] на 1 больше

        // индекс в arr []

        index = index + 1;

      

        // Обходим всех предков и добавляем 'val'

        while(index <= n)

        {

        // Добавить 'val' к текущему узлу дерева BIT

        BITree[index] += val;

      

        // Обновить индекс до родительского

        // в обновлении View

        index += index & (-index);

        }

    }

  

    / * Функция для построения дерева фенвиков

    из данного массива. * /

    void constructBITree(int arr[], int n)

    {

        // Инициализируем BITree [] как 0

        for(int i=1; i<=n; i++)

            BITree[i] = 0;

      

        // Сохраняем фактические значения в BITree []

        // используя update ()

        for(int i = 0; i < n; i++)

            updateBIT(n, i, arr[i]);

    }

  

    // Основная функция

    public static void main(String args[])

    {

        int freq[] = {2, 1, 1, 3, 2, 3

                    4, 5, 6, 7, 8, 9};

        int n = freq.length;

        BinaryIndexedTree tree = new BinaryIndexedTree();

  

        // Построить дерево Фенвика из заданного массива

        tree.constructBITree(freq, n);

  

        System.out.println("Sum of elements in arr[0..5]"+

                        " is "+ tree.getSum(5));

          

        // Позвольте использовать тестирование операции обновления

        freq[3] += 6;

          

        // Обновить BIT для указанного выше изменения в arr []

        updateBIT(n, 3, 6); 

  

        // Находим сумму после обновления значения

        System.out.println("Sum of elements in arr[0..5]"+

                    " after update is " + tree.getSum(5));

    }

}

  
// Этот код предоставлен Ранджаном Бинвани

питон

# Реализация двоичного индексированного дерева на Python

  
# Возвращает сумму arr [0..index]. Эта функция предполагает
# что массив предварительно обработан и частичные суммы
# элементы массива хранятся в BITree [].

def getsum(BITTree,i):

    s = 0 #initialize result

  

    # index в BITree [] на 1 больше, чем индекс в arr []

    i = i+1

  

    # Траверс предков BITree [index]

    while i > 0:

  

        # Добавить текущий элемент BITree к сумме

        s += BITTree[i]

  

        # Переместить индекс на родительский узел в представлении getSum

        i -= i & (-i)

    return s

  
# Обновляет узел в дереве двоичных индексов (BITree) по указанному индексу
# в BITree. Заданное значение 'val' добавляется в BITree [i] и
# все его предки в дереве.

def updatebit(BITTree , n , i ,v):

  

    # index в BITree [] на 1 больше, чем индекс в arr []

    i += 1

  

    # Пройдите через всех предков и добавьте 'val'

    while i <= n:

  

        # Добавить 'val' в текущий узел дерева BI

        BITTree[i] += v

  

        # Обновить индекс до родительского в обновлении View

        i += i & (-i)

  

  
# Создает и возвращает двоичное индексированное дерево для заданного
# массив размером n.

def construct(arr, n):

  

    # Создайте и инициализируйте BITree [] как 0

    BITTree = [0]*(n+1)

  

    # Сохранять фактические значения в BITree [], используя update ()

    for i in range(n):

        updatebit(BITTree, n, i, arr[i])

  

    # Раскомментируйте ниже строки, чтобы увидеть содержимое BITree []

    # для i в диапазоне (1, n + 1):

    # print BITTree [i],

    return BITTree

  

  
# Код драйвера для тестирования вышеуказанных методов

freq = [2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9]

BITTree = construct(freq,len(freq))

print("Sum of elements in arr[0..5] is " + str(getsum(BITTree,5)))

freq[3] += 6

updatebit(BITTree, len(freq), 3, 6)

print("Sum of elements in arr[0..5]"+

                    " after update is " + str(getsum(BITTree,5)))

  
# Этот код предоставлен Раджу Варшней

C #

// C # программа для демонстрации ленивых
// распространение в дереве сегментов

using System;

  

public class BinaryIndexedTree 

    // Максимальный размер дерева

    readonly static int MAX = 1000; 

  

    static int []BITree = new int[MAX]; 

      

    / * n -> Количество элементов, присутствующих во входном массиве.

    BITree [0..n] -> Массив, представляющий двоичный файл

                    Индексированное дерево.

    arr [0..n-1] -> входной массив, для которого сумма префикса

                    оценивается. * /

  

    // Возвращает сумму arr [0..index]. Эта функция

    // предполагается, что массив предварительно обработан и

    // сохранены частичные суммы элементов массива

    // в BITree [].

    int getSum(int index) 

    

        int sum = 0; // Инициализируем результат

      

        // индекс в BITree [] на 1 больше

        // индекс в arr []

        index = index + 1; 

      

        // Пройдемся по предкам BITree [index]

        while(index>0) 

        

            // Добавить текущий элемент BITree

            // подвести

            sum += BITree[index]; 

      

            // Переместить индекс в родительский узел в

            // getSum View

            index -= index & (-index); 

        

        return sum; 

    

  

    // Обновляет узел в дереве двоичных индексов (BITree)

    // по заданному индексу в BITree. Данное значение

    // 'val' добавляется в BITree [i] и все

    // его предки в дереве.

    public static void updateBIT(int n, int index, 

                                        int val) 

    

        // индекс в BITree [] на 1 больше

        // индекс в arr []

        index = index + 1; 

      

        // Обходим всех предков и добавляем 'val'

        while(index <= n) 

        

              

            // Добавить 'val' к текущему узлу дерева BIT

            BITree[index] += val; 

      

            // Обновить индекс до родительского

            // в обновлении View

            index += index & (-index); 

        

    

  

    / * Функция для построения дерева фенвиков

    из данного массива. * /

    void constructBITree(int []arr, int n) 

    

        // Инициализируем BITree [] как 0

        for(int i = 1; i <= n; i++) 

            BITree[i] = 0; 

      

        // Сохраняем фактические значения в BITree []

        // используя update ()

        for(int i = 0; i < n; i++) 

            updateBIT(n, i, arr[i]); 

    

  

    // Код драйвера

    public static void Main(String []args) 

    

        int []freq = {2, 1, 1, 3, 2, 3, 

                    4, 5, 6, 7, 8, 9}; 

        int n = freq.Length; 

        BinaryIndexedTree tree = new BinaryIndexedTree(); 

  

        // Построить дерево Фенвика из заданного массива

        tree.constructBITree(freq, n); 

  

        Console.WriteLine("Sum of elements in arr[0..5]"

                        " is "+ tree.getSum(5)); 

          

        // Позвольте использовать тестирование операции обновления

        freq[3] += 6; 

          

        // Обновить BIT для указанного выше изменения в arr []

        updateBIT(n, 3, 6); 

  

        // Находим сумму после обновления значения

        Console.WriteLine("Sum of elements in arr[0..5]"

                    " after update is " + tree.getSum(5)); 

    

  
// Этот код предоставлен PrinciRaj1992


Выход:

Sum of elements in arr[0..5] is 12
Sum of elements in arr[0..5] after update is 18

Можем ли мы расширить двоичное индексированное дерево для вычисления суммы диапазона за O (Logn) времени?
Да. rangeSum (l, r) = getSum (r) — getSum (l-1).

Приложения:
Реализация алгоритма арифметического кодирования. Разработка двоичного индексированного дерева была в первую очередь мотивирована его применением в этом случае. Смотрите это для более подробной информации.

Примеры задач:
Граф инверсий в массиве | Набор 3 (с использованием BIT)
Двумерное двоичное индексируемое дерево или дерево Фенвика
Подсчет треугольников в прямоугольном пространстве с использованием BIT

Ссылки:
http://en.wikipedia.org/wiki/Fenwick_tree
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Двоичное индексированное дерево или дерево Фенвика

0.00 (0%) 0 votes