实施允许您执行某些操作的数据结构（BST）

Question

实现一个允许您执行以下操作的数据结构：

add（i）-将数字i添加到集合S中（如果已经存在，则该集合不变）；

sum（l，r）-打印满足不等式l≤x≤r的S中所有元素x的总和。

最初，集合S为空。输入文件的第一行包含n-操作数（1≤n≤300 000）。接下来的n行包含运算。每个操作的格式为“ + i”或“？l r”。操作“ ？l r”设置请求sum（l，r）] >>

Ex：输入

] >>

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;
}
在此处输入代码

实现一个允许您执行以下操作的数据结构：加（i）-将数字i添加到集合S中（如果那里已经存在，则该集合不变）； sum（l，r）-打印...

Answer 1

看来您的树不平衡。我认为您应该使用分段树来完成此任务。（只是因为这是我最喜欢的结构，而且并不难）））

设置v [i] = i以插入元素