# 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
}
``````

## 1.0.0 #

• clean up, CI, examples and documentation added

## 0.1.0+1 #

• Initial release

example/main.dart

``````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
}

void example2() {
print("\t\t\tInit");
const size = 10000000;

final list = List.generate(size, (a) => a.toDouble());
final tree = FenwickTree(group: const DoubleSumGroup(), size: size);

list.asMap().entries.forEach((i) => tree.update(i.key, i.value));
print("\t\t\tTree Updated");

print("\t\t\tList.reduce");
for (int i = 0; i <= 10; i++) {
print(list.reduce((a, b) => a + b));
}

print("\t\t\tFenwickTree.sum");
for (int i = 0; i <= 10; i++) {
print(tree.sum(list.length - 1));
}

print("\t\t\tEnd");
}

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

## Use this package as a library

### 1. Depend on it

``````
dependencies:
fenwick_tree: ^1.0.0

``````

### 2. Install it

You can install packages from the command line:

with pub:

``````
\$ pub get

``````

with Flutter:

``````
\$ flutter pub get

``````

Alternatively, your editor might support `pub get` or `flutter pub get`. Check the docs for your editor to learn more.

### 3. Import it

Now in your Dart code, you can use:

``````
import 'package:fenwick_tree/fenwick_tree.dart';
``````
 Popularity: Describes how popular the package is relative to other packages. [more] 15 Health: Code health derived from static analysis. [more] 100 Maintenance: Reflects how tidy and up-to-date the package is. [more] 100 Overall: Weighted score of the above. [more] 58

We analyzed this package on Jan 19, 2020, and provided a score, details, and suggestions below. Analysis was completed with status completed using:

• Dart: 2.7.0
• pana: 0.13.4

#### Dependencies

Package Constraint Resolved Available
Direct dependencies
Dart SDK >=2.2.2 <3.0.0
abstract_dart ^1.0.1 1.0.2
meta ^1.0.0 1.1.8
Transitive dependencies
decimal 0.3.5
rational 0.3.7
Dev dependencies
extra_pedantic ^1.1.1
test ^1.5.0
test_coverage ^0.2.0