C# (C Sharp) programming: “Fenwick Tree на C#: всё держится на одном битовом трюке Fenwick Tree,…”

Fenwick Tree на C#: всё держится на одном битовом трюке

Fenwick Tree, или Binary Indexed Tree, считает prefix sums за O(log n).

Главная операция:


i & -i

Она находит младший установленный бит числа.

Именно это значение говорит структуре, на сколько нужно прыгнуть по индексам.

Пример:


i = 12        // 1100
i & -i = 4    // 0100

Реализация на C#:


public sealed class FenwickTree
{
    private readonly int[] _tree;

    public FenwickTree(int size)
    {
        _tree = new int[size + 1];
    }

    public void Update(int index, int delta)
    {
        while (index < _tree.Length)
        {
            _tree[index] += delta;
            index += index & -index;
        }
    }

    public int Query(int index)
    {
        var sum = 0;

        while (index > 0)
        {
            sum += _tree[index];
            index -= index & -index;
        }

        return sum;
    }
}

Как это работает:

* Update идёт вверх по структуре и обновляет все узлы, которые отвечают за индекс
* Query идёт вниз и собирает блоки, из которых состоит prefix sum
* index & -index каждый раз выбирает размер текущего блока

Главный нюанс: Fenwick Tree обычно использует 1-based indexing.

То есть первый элемент имеет индекс 1, а не 0.

Пример использования:


var tree = new FenwickTree(5);

tree.Update(1, 10);
tree.Update(2, 20);
tree.Update(3, 30);

Console.WriteLine(tree.Query(3)); // 60

Красота Fenwick Tree в том, что дерево не хранится явно.

• Нет узлов.
• Нет ссылок.
• Нет рекурсии.

Только массив и один битовый трюк.

Дерево спрятано прямо внутри двоичного представления индексов.