# fenwick_tree 2.0.0 fenwick_tree: ^2.0.0 copied to clipboard

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;
}
``````
1
likes
120
pub points
0%
popularity

### Publisher

modulovalue.com

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