56ms BST C++ solution


  • 0

    Everyone is sharing Segment Tree or BIT solutions.
    BST is just another way to solve it.

    struct MyTreeNode {
        int index;
        int val;
        int less;
        MyTreeNode* left;
        MyTreeNode* right;
    };
    
    class NumArray {
    public:
        NumArray(vector<int> &nums) {
            int sum = 0;
            tree = buildTree(nums, 0, nums.size(), sum);
        }
    
        void update(int i, int val) {
            int oldValue = addValue(i, val);
            addValue(i, -oldValue);
        }
    
        int sumRange(int i, int j) {
            return getLessThanIndex(j + 1) - getLessThanIndex(i);
        }
    private:
        MyTreeNode* tree;
        MyTreeNode* buildTree(vector<int>& nums, int begin, int end, int& sum) {
            if (begin == end) return nullptr;
    
            int mid = begin + (end - begin) / 2;
            auto root = new MyTreeNode();
            int leftSum = 0, rightSum = 0;
            root->left = buildTree(nums, begin, mid, leftSum);
            root->right = buildTree(nums, mid + 1, end, rightSum);
            root->index = mid;
            root->less = leftSum;
            root->val = nums[mid];
            sum = leftSum + rightSum + root->val;
            return root;
        }
    
        int addValue(int i, int val) {
            int oldValue = 0;
            auto p = tree;
            while (p) {
                if (p->index == i) {
                    oldValue = p->val;
                    p->val += val;
                    break;
                } else if (p->index > i) {
                    p->less += val;
                    p = p->left;
                } else {
                    p = p->right;
                }
            }
            return oldValue;
        }
    
        int getLessThanIndex(int i) {
            int sum = 0;
            auto p = tree;
            while (p) {
                if (p->index == i) {
                    sum += p->less;
                    break;
                } else if (p->index > i) {
                    p = p->left;
                } else {
                    sum += p->less + p->val;
                    p = p->right;
                }
            }
            return sum;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.