Случайная выборка с изъятием по весам из бесконечной последовательности. Как такое сделать?

Если для каждого отрезка хранить не начало+конец, а только его длину, то при удалении отрезка, предается перестраивать только те отрезки, в которые входит удаляемый (т.е. логарифмическая сложность сложность удаления). При доступе к элементу, двигаясь по дереву от корня к листьям, уменьшаем счетчик на размер пройденного элемента:

#include <variant>
#include <memory>
#include <array>
#include <stdexcept>
#include <variant>
#include <algorithm>

template<typename Key, typename Data, size_t ChildsCount=4>
class key_summ_tree
{
    struct empty_node
    {};
    struct data_node
    {
        Key key;
        Data data;
    };
    struct childs_node;
    typedef std::variant< empty_node, data_node, std::unique_ptr<childs_node> > any_node;
    struct childs_node
    {
        Key key_summ;
        size_t size;
        std::array< any_node, ChildsCount > childs;
    };

    any_node root = empty_node{};


    static size_t _size(const empty_node& ) { return 0;}
    static size_t _size(const data_node& ) { return 1;}
    static size_t _size(const std::unique_ptr<childs_node>& i) { return i ? i->size : 0; }
    static size_t size(const any_node& i) { return std::visit( [](auto& ii)->size_t {return _size(ii); }, i); }

    static Key _key_summ(const empty_node& ) { return Key{0};}
    static Key _key_summ(const data_node& i) { return i.key;}
    static Key _key_summ(const std::unique_ptr<childs_node>& i) { return i ? i->key_summ : Key{0}; }
    static Key key_summ(const any_node& i) { return std::visit( [](auto& ii)->Key {return _key_summ(ii); }, i); }

    static Data& _at(empty_node& , Key) { throw std::out_of_range("Key out of range."); }
    static Data& _at(data_node& i, Key) { return i.data; }
    static Data& _at(std::unique_ptr<childs_node>& i, Key k)
    {
        for( any_node& j : i->childs )
        {
            Key j_key = key_summ(j);
            if(k<j_key)
                return std::visit( [k](auto&jj)->Data& { return _at(jj,k); },  j);
            k -= j_key;
        }
            // Сюда можем попасть, если произошла потеря точности 
            // при операциях с ключем с плавоющей точкой.
            // Взятие последнего элемента, предлагаю дописать самостоятельно.     
        throw std::out_of_range("Key out of range.");
    }
    static Data& at(any_node& i, Key k)
    {
        return std::visit( [k](auto& ii)->Data& {return _at(ii,k); }, i);
    }


    static void insert( any_node& i,  data_node&& d )
    {   // не использую std::visit, поскольку  в некоторых ветках меняется 
        // хранимый в variant тип.
        if(std::holds_alternative<empty_node>(i)) 
        {
            i=std::move(d);
        }
        else
        {
            if(std::holds_alternative<data_node>(i))
            {
                data_node tmp = std::get<data_node>( std::move(i) );
                auto new_i = std::make_unique<childs_node>();
                i = std::make_unique<childs_node>( childs_node{ tmp.key, 1, { std::move(tmp) } });
            }

            childs_node& childs = * std::get<std::unique_ptr<childs_node>>(i);
            childs.size += 1;
            childs.key_summ += d.key;
            auto& add_to=* std::min_element( childs.childs.begin(), childs.childs.end(),
                                             [](auto& l, auto& r){ return size(l)<size(r); } );
            insert( add_to, std::move(d) );
        }
    }

    static Key remove( any_node& i,  Key k )
    {
        if(std::holds_alternative<empty_node>(i))
            throw std::out_of_range("Key out of range.");

        else if(std::holds_alternative<data_node>(i))
        {
            Key ret = std::get<data_node>(i).key;
            i = empty_node{};
            return ret;
        }
        else
        {
            childs_node& childs = * std::get<std::unique_ptr<childs_node>>(i);
            if(childs.size==0)
                throw std::out_of_range("Key out of range.");
            for( auto& j : childs.childs )
            {
                Key j_key = key_summ(j);
                if(k<j_key)
                {
                    Key ret = remove(j,k);
                    childs.size -= 1;
                    childs.key_summ -= ret;

                    if(childs.size==0)
                    {
                        i = empty_node{};
                    }
                    else if(childs.size==1)
                    {
                        i = data_node{ key_summ(i), at(i, Key{0} ) };
                    }
                    return ret;
                }
            }
            // Сюда можем попасть, если произошла потеря точности 
            // при операциях с ключем с плавоющей точкой.
            // Взятие последнего элемента, предлагаю дописать самостоятельно.     
            throw std::out_of_range("Key out of range.");
        }
    }


public:
    key_summ_tree() = default;
    key_summ_tree(const key_summ_tree&)=default;
    key_summ_tree(key_summ_tree&&)=default;
    key_summ_tree( std::initializer_list< data_node > list  )
    {
        for( auto&& i : list)
            insert( i.key, i.data );
    }

    size_t size() const { return size(root); }
    Key    key_summ() const { return key_summ(root); }

    Data& at(Key key_summ)
    {
        return at(root, key_summ);
    }
    const Data& at(Key key_summ) const
    {
        return at( static_cast<any_node&>(root), key_summ);
    }
    void insert( Key k, Data&& d )
    {
        insert( root, data_node{ k, std::move(d) } );
    }
    void remove( Key k )
    {
        remove(root, k);
    }
};