A C implementation of Fenwick Trees.
C
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
README.md
fenwick.c

README.md

fenwick-tree

A C implementation of Fenwick trees. The Fenwick tree is a great data structure for handling operations on prefixes of sequences. This particular version implements prefix sums ans updates. Both operations take O(lg N) time in the worst case where N is the length of the sequence.

API

  • inc(pos, delta): increment prefix [1..pos] of sequence by delta
  • get(pos): get sum of prefix [1..pos] of sequence