Re: a logarithmic-time alternative to summed-area tables for reducing arbitrary semigroup operations over arbitrary ranges (a generalization of RMQ segment trees)

> There's an alternative to summed-area tables with a small, linear
> space cost and linear construction time and space, providing worst- 
> case
> logarithmic-time reduction over arbitrary intervals under arbitrary
> semigroup operations, and which supports updates efficiently, unlike
> summed-area tables.  The algorithm is like twenty fricking lines of  
> code
> if you leave out the "update" and "small" parts.


cf fenwick trees (which could be useful for your rice-coded spelling  
correction, if one wished to check single words instead of entire  
documents)
also blelloch's parallel prefix sum, which uses straight (non-heap  
indexed) array storage
also xanalogical dspative properties are summed leaf-to-root and  
widative properties are summed "left"-to-"right"
the former suggests we may apply stokes' theorem to arbitrary graphs  
(and also, eg for finite state machines, in higher dimensions)
that is to say: we arrive at the same answer
whether we integrate an operation over the boundary of a given volume
or we integrate the differential of the operation over the volume itself
we often use this equivalence in one direction, eg to break up a  
large operation over external storage into a series of small  
operations in internal
we also use this equivalence in the opposite direction, eg to perform  
a single major update when iterating and updating for each minor  
modification would lag

-Dave

-- 
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss