Декартовое дерево по неявному ключу 2

struct node //добавлено ячейка sum
{
    int value_node = NULL;
    int size       = NULL;
    int sum;
    node* left = nullptr;
    node* right = nullptr;

    node(int new_value)
    {
        value_node = new_value;
        size = 1;
    }
};

typedef pair<node*, node*> Pair;

void  update(node* A) // добавлено подсчет ячейки sum
{
    A->size  = 1 + A->left->size + A->right->size;
    A->sum   = A->value_node + A->left->sum + A->right->sum;
}

int sum(node* A,const int& left_face,const int& right_face)
{
    Pair left  =  split(A, left_face);
    Pair right = split(left.second, right_face);

    int output = right.first->sum;

    left.second =merge(right.first, right.second);
    merge(left.first, left.second);
    return output;
}