3 ms·
So this method works for max and sum. What else? Is it any sort-of "associative function" - ie, f st. f(x, f(y,z)) = f(f(x,y), z)? Are there other useful funct
by joe_the_user 7y ago
So this method works for max and sum. What else? Is it any sort-of "associative function" - ie, f st. f(x, f(y,z)) = f(f(x,y), z)?
Are there other useful functions satisfying these conditions?
- chaoxu 7y agoThe one that works for sum works for all associative functions. One can do a bit better using the same amount of space, but with query time O(α(n)), where α is the inverse Ackermann function. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.79.1554 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.79.1...