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

Дерево Фенвика (двоичное индексированное дерево, Fenwick tree, binary indexed tree, BIT) - структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Питером Фенвиком в 1994 году. Дерево Фенвика напоминает дерево отрезков, однако проще в реализации.

Реализация на Python

# Дерево Фенвика: прибавление к элементу и префиксная сумма за O(log n), память O(n).
def fenwick_add(tree, index, delta):
    # index от 1 до n: прибавляем delta к элементу a[index]
    while index < len(tree):
        tree[index] += delta
        index += index & -index  # переход к следующему узлу, который покрывает index


def prefix_sum(tree, index):
    # Сумма a[1] + ... + a[index]
    total = 0
    while index > 0:
        total += tree[index]
        index -= index & -index  # убираем младший единичный бит
    return total


def main():
    values = [3, 1, 4, 1, 5, 9]
    tree = [0] * (len(values) + 1)
    for index, value in enumerate(values, start=1):
        fenwick_add(tree, index, value)
    print(prefix_sum(tree, 3))  # 3 + 1 + 4 = 8
    fenwick_add(tree, 2, 10)  # a[2] += 10
    print(prefix_sum(tree, 6) - prefix_sum(tree, 2))  # 4 + 1 + 5 + 9 = 19


if __name__ == "__main__":
    main()

Реализация на Rust

// Дерево Фенвика: прибавление к элементу и префиксная сумма за O(log n), память O(n).
// Массив tree имеет длину n + 1, элементы нумеруются с 1.

// Прибавляет delta к элементу a[index], index от 1 до n.
pub fn fenwick_add(tree: &mut [i64], mut index: usize, delta: i64) {
    while index < tree.len() {
        tree[index] += delta;
        index += index & index.wrapping_neg(); // следующий узел, который покрывает index
    }
}

// Сумма a[1] + ... + a[index].
pub fn prefix_sum(tree: &[i64], mut index: usize) -> i64 {
    let mut total = 0;
    while index > 0 {
        total += tree[index];
        index -= index & index.wrapping_neg(); // убираем младший единичный бит
    }
    total
}

fn main() {
    let values: [i64; 6] = [3, 1, 4, 1, 5, 9];
    let mut tree: Vec<i64> = vec![0; values.len() + 1];
    for (i, &value) in values.iter().enumerate() {
        fenwick_add(&mut tree, i + 1, value);
    }
    println!("{}", prefix_sum(&tree, 3)); // 3 + 1 + 4 = 8
    fenwick_add(&mut tree, 2, 10); // a[2] += 10
    println!("{}", prefix_sum(&tree, 6) - prefix_sum(&tree, 2)); // 4 + 1 + 5 + 9 = 19
}

Реализация на C++

// Дерево Фенвика: прибавление к элементу и префиксная сумма за O(log n), память O(n).
#include <cstddef>
#include <iostream>
#include <vector>

// Прибавляет delta к элементу a[index], index от 1 до n (размер tree равен n + 1).
void fenwick_add(std::vector<long long>& tree, std::size_t index, long long delta) {
    while (index < tree.size()) {
        tree[index] += delta;
        index += index & -index;  // следующий узел, который покрывает index
    }
}

// Сумма a[1] + ... + a[index].
long long prefix_sum(const std::vector<long long>& tree, std::size_t index) {
    long long total = 0;
    while (index > 0) {
        total += tree[index];
        index -= index & -index;  // убираем младший единичный бит
    }
    return total;
}

int main() {
    const std::vector<long long> values = {3, 1, 4, 1, 5, 9};
    std::vector<long long> tree(values.size() + 1, 0);
    for (std::size_t i = 0; i < values.size(); ++i) {
        fenwick_add(tree, i + 1, values[i]);
    }
    std::cout << prefix_sum(tree, 3) << '\n';  // 3 + 1 + 4 = 8
    fenwick_add(tree, 2, 10);                  // a[2] += 10
    std::cout << prefix_sum(tree, 6) - prefix_sum(tree, 2) << '\n';  // 4 + 1 + 5 + 9 = 19
    return 0;
}