Fenwick Tree
The FenwickTree
type is data structures which is used for handling increment and decrement to prefix-sums of an array efficiently.
Usage:
FenwickTree{T}(n) # Constructs a Fenwick Tree of length `n`
FenwickTree{T}(counts) # Constructs a Fenwick Tree from an array of `counts`
inc!(ft, ind, val) # Increases the value of the FenwickTree `ft` by `val` from the index `ind` upto the length of `ft`
dec!(ft, ind, val) # Decreases the value of the FenwickTree `ft` by `val` from the index `ind` upto the length of `ft`
incdec!(ft, left, right, val) # Increases the value of the FenwickTree `ft` by `val` from the indices from `left` and decreases it from the `right`
prefixsum(ft, ind) # Return the cumulative sum from index 1 upto `ind` of the FenwickTree `ft`
Examples:
julia> f = FenwickTree{Int}(6)
julia> inc!(f, 2, 5)
julia> prefixsum(f, 1)
0
julia> prefixsum(f, 3)
5