fenwick_tree 2.0.0

A lightweight Fenwick Tree (also known as Binary Indexed Tree or BIT).

example/main.dart

import 'package:fenwick_tree/fenwick_tree.dart';

void main() {
  example();
  example2();
}

/// A basic hello world example.
void example() {
  final tree = GroupalFenwickTreeImpl(
    algebra: const SumGroupImpl(),
    size: 5,
  );
  tree.increase(index: 0, value: 1.0);
  tree.increase(index: 1, value: 2.0);
  tree.increase(index: 2, value: 3.0);
  tree.increase(index: 3, value: 4.0);
  tree.increase(index: 4, value: 5.0);
  print("${tree.sum(index_to: 4)} == ${1 + 2 + 3 + 4 + 5}");
  tree.increase(index: 2, value: 1);
  print("${tree.sum(index_to: 4)} == ${1 + 2 + 4 + 4 + 5}");
}

void example2() {
  print("\t\t\tInit");
  const size = 100000000;
  print("Building the list.");
  final list = List.filled(
    size,
    0.0,
  );
  print("Building the fenwick tree.");
  final tree = GroupalFenwickTreeImpl(
    algebra: const SumGroupImpl(),
    size: size,
  );
  print("Filling the list.");
  for (int i = 0; i < size; i++) {
    list[i] = i.toDouble();
  }
  print("Filling the fenwick tree.");
  for (int i = 0; i < size; i++) {
    tree.increase(
      index: i,
      value: i.toDouble(),
    );
  }
  print("List");
  for (int i = 0; i <= 10; i++) {
    print(
      "  " +
          list
              .reduce(
                (final a, final b) => a + b,
              )
              .toString(),
    );
    list[100 + i] = 1000;
  }
  print("Tree");
  for (int i = 0; i <= 10; i++) {
    print(
      "  " +
          tree
              .sum(
                index_to: list.length - 1,
              )
              .toString(),
    );
    tree.update(index: 100 + i, value: 1000);
  }
}

class SumGroupImpl implements FenwickTreeGroup<double> {
  const SumGroupImpl();

  @override
  double identity() => 0.0;

  @override
  double inverse(
    final double left,
    final double right,
  ) =>
      left - right;

  @override
  double operate(
    final double left,
    final double right,
  ) =>
      left + right;
}