prefix_sum

Prefix sum algorithm library.

Usage

import 'package:prefix_sum/prefix_sum.dart';

void main(){
  final list = SparsePrefixSumList(/*defaultValue*/ 2, /* length */ 10);
  // use list like an ordinary list
  list.getPrefixSum(3); // 8
  list.findPrefixSumBefore(8); // 2
}

Unlike most List implementation, SparsePrefixSumList stores values in Map, so index access would have O(logN) complexity instead of O(1).

Plans

  • support dense list

Libraries

prefix_sum