Re: [boost] [countertree] Formal Review Request

Subject: Re: [boost] [countertree] Formal Review Request
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2012-10-05 07:30:26

On Thu, Oct 4, 2012 at 6:23 AM, Francisco José Tapia <fjtapia_at_[hidden]>wrote
>
>
> *COUNTERTREE*
>
> This library is an implementation of a binary red-black counter tree. This
> tree have an additional counter in each leaf. This permit the access to the
> elements by the position, like in a vector. It is a random access container
> with random access iterators . Based on this tree we have :
>
> Hi Francisco,

The method that you are using is called "augmenting data structures".
I suggest you to add reference to this book, which gives detailed
description of this method in chapter 14:

T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein.
*Introduction to Algorithms*. 2nd Edition, MIT Press and McGraw-Hill, 2001.

Figure 14.1 is very similar to the figure in your documentation.

Did you try double augmenting that supports algorithm accumulate() with
logarithmic running time?

Regards,
Vadim Stadnik