fenwick_tree 1.0.0

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

fenwick_tree

A simple Fenwick Tree (also known as Binary Indexed Tree and BIT) in Dart.

Based on Princeton, FenwickTree.java

import 'package:abstract_dart/abstract_dart.dart';
import 'package:fenwick_tree/fenwick_tree.dart';

void example() {
  // A Fenwick Tree needs addition, subtraction and identity which are provided
  // in form of a Group. See https://pub.dev/packages/abstract_dart
  final tree = FenwickTree(group: const DoubleSumGroup(), size: 5);
  // or
  final tree2 = FenwickTree<double>.create(
    identity: () => 0.0,
    addition: (a, b) => a + b,
    subtraction: (a, b) => a - b,
    size: 5,
  );

  tree.update(0, 1.0);
  tree.update(1, 2.0);
  tree.update(2, 3.0);
  tree.update(3, 4.0);
  tree.update(4, 5.0);

  print(tree.sum(4)); // 15 (1+2+3+4+5)
  print(tree.rangeSum(3, 5)); // 9 (4+5)
  print(tree.length()); // 5
}