Реализуйте структуру данных (BST), которая позволяет выполнять некоторые операции

Question

Реализация структуры данных, которая позволяет выполнять следующие операции:

add (i) - добавить число i к множеству S (если оно там уже существует, множество не изменяется);

sum (l, r) - вывести сумму всех элементов x из S, которые удовлетворяют неравенству l ≤ x ≤ r.

Первоначально набор S пуст. Первая строка входного файла содержит n - количество операций (1 ≤ n ≤ 300 000). Следующие n строк содержат операции. Каждая операция имеет вид «+ i» или «? Lr» . Операция «? Lr » устанавливает запрос сумма (л, r)

Пример: ввод

6

+ 1

+ 3

+ 3

? 2 4

+ 1

? 2 4

вывод:

3

7

У меня есть свой код, но он не работает, хотя мои собственные тесты он проходит. Может кто-нибудь помочь с решением или дать мне тесты, которые мои решения не проходят?

#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

const long long MIN = -1e9 - 100;
const long long MAX = 1e9 + 100;

struct node {
    long long key;
    struct node* left, * right;
};

struct node* newNode(long long item) {
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

void inorderLeft(struct node* root, long long a, long long& min) {
    if (root != NULL && min == MAX) {
        inorderLeft(root->left, a, min);
        if (root->key > a && root->key < min)
            min = root->key;
        inorderLeft(root->right, a, min);
    }
}

void inorderRight(struct node* root, long long a, long long& max) {
    if (root != NULL && max == MIN) {
        inorderRight(root->right, a, max);
        if (root->key < a && root->key > max)
            max = root->key;
        inorderRight(root->left, a, max);
    }
}

struct node* search(struct node* root, long long key) {
    if (root == NULL || root->key == key)
        return root;
    if (root->key < key)
        return search(root->right, key);
    return search(root->left, key);
}

struct node* insert(struct node* node, long long key) {
    if (node == NULL) return newNode(key);
    if (key < node->key)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);
    return node;
}

struct node* minValueNode(struct node* node) {
    struct node* current = node;
    while (current && current->left != NULL)
        current = current->left;
    return current;
}

struct node* deleteNode(struct node* root, long long key) {
    if (root == NULL) return root;
    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    else {
        if (root->left == NULL) {
            struct node* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            struct node* temp = root->left;
            free(root);
            return temp;
        }
        struct node* temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}

int getCount(node* root, int low, int high) {
    if (!root) return 0;
    if (root->key == high && root->key == low)
        return root->key;
    if (root->key <= high && root->key >= low)
        return root->key + getCount(root->left, low, high) + getCount(root->right, low, high);
    else if (root->key < low) 
        return getCount(root->right, low, high);
    else return getCount(root->left, low, high);
}

int main() {
    int n;
    cin >> n;
    cout << boolalpha;
    struct node* root = NULL;
    bool b = 0;
    int prev = 0;
    string str = "";
    for (int i = 0; i < n; i++) {
        cin >> str;
        long long r, l;
        if (str == "+") {
            cin >> r;
            if (b == 0) {
                if ((search(root, r) != 0) == false)
                    root = insert(root, r);
            }
            else {
                int y = (r + prev) % 1000000000;
                if ((search(root, y) != 0) == false)
                    root = insert(root, y);
            }
            b = 0;
        }
        else if (str == "?") {
            cin >> l >> r;
            prev = getCount(root, l, r);
            cout << prev << "\n";
            b = 1;
        }
    }
    return 0;
}

введите код