Boost logo

Boost :

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
> 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?

Vadim Stadnik

Boost list run by bdawes at, gregod at, cpdaniel at, john at