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

struct node
{
    uint8_t color     = NULL;
    int value_node    = NULL;
    int size          = NULL;
    int sum           = NULL;
    int average_color = NULL;
    int add           = NULL;
    int add_color     = NULL;
    node* left = nullptr;
    node* right = nullptr;

    node(int new_value)
    {
        value_node = new_value;
        size = 1;
    }
    node(uint8_t new_color)
    {
        color = new_color;
        average_color = color;
    }
};



void  update(node* A)
{
    A->size  = 1 + A->left->size + A->right->size;
    A->sum   = A->value_node + A->left->sum + A->right->sum;
    A->average_color = (A->color + A->left->average_color + A->right->average_color) / 3;
}

int average_color(node * A, int left_face, int right_face)
{
    push_down(A);
    color_push_down(A);
    Pair left = split(A, left_face);
    Pair right = split(left.second, right_face);

    int output = right.first->average_color;

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