### 7 releases (3 stable)

2.0.1 | Sep 15, 2022 |
---|---|

2.0.0 | Sep 14, 2022 |

1.0.0 | Feb 23, 2020 |

0.2.0 | Apr 7, 2018 |

0.1.2 | Apr 6, 2018 |

#**494** in Algorithms

**373** downloads per month

Used in **6** crates
(3 directly)

**MIT**license

15KB

173 lines

A **Fenwick tree** or **binary indexed tree**/**bit indexed tree** is a data structure
that supports the following two operations efficiently over an array of numbers

:`a [0..n]`

- Calculate a prefix sum:
`a``[``0``]``+`a`[``1``]``+``...``+`a`[`i`]` - Update one element:
`a``[`i`]``+=`delta

With a naïve implementation, only one of the operations can be made to have constant time
complexity while the other one has to be linear. With Fenwick tree, both take only

.`O (log(N))`

This crate is

and has no (non-dev) dependencies.`no_std`

# Examples

Use the

module for operations on a 1D Fenwick tree:`array`

`use` `fenwick``::``array``::``{`update`,` prefix_sum`}``;`
`let` fw `=` `&``mut` `[``0``i32``;` `10``]``;` `//` backing array of Fenwick tree (NOT original array!)
`assert_eq!``(``prefix_sum``(`fw`,` `0``)``,` `0``)``;`
`assert_eq!``(``prefix_sum``(`fw`,` `9``)``,` `0``)``;`
`update``(`fw`,` `0``,` `3``)``;` `//` original array: [3, 0, 0, 0, 0, 0, 0, 0, 0, 0]
`assert_eq!``(``prefix_sum``(`fw`,` `0``)``,` `3``)``;`
`assert_eq!``(``prefix_sum``(`fw`,` `9``)``,` `3``)``;`
`update``(`fw`,` `5``,` `9``)``;` `//` original array: [3, 0, 0, 0, 0, 9, 0, 0, 0, 0]
`assert_eq!``(``prefix_sum``(`fw`,` `4``)``,` `3``)``;`
`assert_eq!``(``prefix_sum``(`fw`,` `5``)``,` `12``)``;`
`assert_eq!``(``prefix_sum``(`fw`,` `6``)``,` `12``)``;`
`update``(`fw`,` `4``,` `-``5``)``;` `//` original array: [3, 0, 0, 0, -5, 9, 0, 0, 0, 0]
`assert_eq!``(``prefix_sum``(`fw`,` `4``)``,` `-``2``)``;`
`assert_eq!``(``prefix_sum``(`fw`,` `5``)``,` `7``)``;`
`update``(`fw`,` `0``,` `-``2``)``;` `//` original array: [1, 0, 0, 0, -5, 9, 0, 0, 0, 0]
`assert_eq!``(``prefix_sum``(`fw`,` `4``)``,` `-``4``)``;`
`assert_eq!``(``prefix_sum``(`fw`,` `5``)``,` `5``)``;`

Use the

module to implement multidimensional Fenwick trees:`index`

`use` `fenwick``::``index``::``zero_based``::``{`down`,` up`}``;`
`const` `MAX``:` `usize` `=` `1000``;`
`fn` `update``(``i``:` `usize`, `j``:` `usize`, `k``:` `usize`, `delta``:` `i32``)`` ``{`
`for` ii `in` `up``(`i`,` `MAX``)` `{`
`for` jj `in` `up``(`j`,` `MAX``)` `{`
`for` kk `in` `up``(`k`,` `MAX``)` `{`
`/*` increment 3D array at [ii, jj, kk] by delta `*/`
`}`
`}`
`}`
`}`
`fn` `prefix_sum``(``i``:` `usize`, `j``:` `usize`, `k``:` `usize``)`` ``->` `i32` `{`
`let` `mut` sum `=` `0``i32``;`
`for` ii `in` `down``(`i`)` `{`
`for` jj `in` `down``(`j`)` `{`
`for` kk `in` `down``(`k`)` `{`
`/*` increment sum by 3D array at [ii, jj, kk] `*/`
`}`
`}`
`}`
sum
`}`