CavityTools
This small package contains:

cavity!
andcavity
: Functions to compute theN
allbutone operations betweenN
elements in timeO(N)
. The operation is arbitrary and needs only to be associative. This is equivalent to computing[reduce(op, (source[j] for j in eachindex(source) if i != j); init) for i in eachindex(source)]
which however would needN*(N1)
evaluations ofop
. Ifop
is commutative with exact inverseinvop
, you could obtain the same result ofcavity(source, op, init)
, also in timeO(N)
, withfull=reduce(op, source; init); [op(invop(x), full) for x in source]
. 
Accumulator
: A data structure keeping a liveupdatablecumsum
. Updating or retrieving one element costsO(log(N))
, computing the total sum costsO(1)
.searchsortedfirst(a::Accumulator, v)
is also implemented, taking alsoO(log(N))
time. 
ExponentialQueue
:Accumulator
plus index tracking, intended for sampling in a Gillespielike scheme. Indices are in1:N
.